1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability and Mathematica

  1. Oct 1, 2016 #1
    1. The problem statement, all variables and given/known data
    The problem I'm having involves looking for a specific formula for the probability of matching a deck of playing cards via the result of a shuffle. I want to know how many times I must shuffle for the probability of the shuffle matching one of the past resulting decks to be at least 50%.

    2. Relevant equations
    At first, I considered the binomial equation, but because each shuffle introduces a new deck to compare subsequent shuffles to I found myself at a loss. So the equation I have examined is

    3. The attempt at a solution
    I thought about the probabilities step-wise looking for a pattern. For example, say I do the same with a 32 sided dice. At first, I choose any side to be the one I am looking for a match. So in one roll, the probability of rolling a match is 1/32. But in two rolls, it would be (1/32)+(31/32)(2/32), because it assumes 31 out of 32 times I need to reroll, but now I have two sides I will consider a success. For 3 rolls, it would be (1/32)+(31/32)(2/32)+(31/32)(31/32)(3/32)? Correct? I just don't know whether my take on probability is correct and would love any comment.
  2. jcsd
  3. Oct 1, 2016 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You are on the right track, but there is a mistake in the last term. What is the probability that none of the first three matched?
    But this sequential approach is tough. It is easier if you ask instead, given n trials, in how many ways can they all produce different results.
  4. Oct 1, 2016 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The problem statement is ambiguous.

    What I think you meant to ask is

    'How many shuffles must there be for there to be at least a 50% probability that at least two of the card orderings are identical?'

    This is the same as the birthday problem, but replacing 365 by 52. That link should tell you how to solve it. Post back here if you have trouble. A little care is needed, to notice that the number of different card orders is one more than the number of shuffles.

    The way you have written the problem is different though. You refer to the probability of 'the shuffle' matching a previous shuffle. That sounds like a reference to the latest shuffle. That is potentially a more complex question and needs more information in order to be well-posed. Depending on exactly what you mean it may involve stopping times and/or expected values. Just to give an idea of why it becomes more complex, note that the probability of the latest shuffle matching an earlier one depends not only on the number of shuffles so far, but also on how many of them were different. If we've done 100 shuffles and every time, by an amazing fluke, they came out the same, the probability of the next shuffle matching a previous order is 1/52!. On the other hand, if every one of the 101 orders is different, the probability is 101/52!.

    Let me know if you didn't mean the birthday problem, and we can explore what it is that you are after.
  5. Oct 1, 2016 #4
    I'm definitely going to give this a read. Thank you for your help.
    To clarify, I'm looking to find the number of shuffles (with the assumption no successful deck match has been found prior) necessary so that the probability of subsequent shuffles matching any one of the unique combinations found in prior reorders of the deck is 50%. I'm sorry my question is so ambiguous, but I thought of it initally as having a deck order, then comparing a single shuffle to the order and including all the deck orders in a group to be compared to all subsequent shuffles but then summing the probability of each occurring event.

    I used the dice example because I don't want to explicitly figure out the problem I am working on as it is entended to be homework, but I'm a bit more concerned about the way the odds add up.

    For example, the probability of matching after one shuffle is 1/52!. But then for two shuffles, it means we have two orders to compare it to, which I thought would mean the probability of finding a match in two shuffles would be (1/52!)+(52!-1)/(52!)(2/52!) because it factors in the 52!-1 results one doesn't find a match and the new probability of 2/52! . I don't know if this thinking is correct, but then next term or shuffle probability is what has me most confused.

    Would it be (1/52!)+(52!-1)/(52!)(2/52!)+(((52!-1)/(52!))^2)(3/52!) or (1/52!)+(52!-1)/(52!)(2/52!)+((52!-1)/(52!))((52!-2)/(52!))(3/52!) for three shuffles?

    I'm sorry for responding before I read about the birthday paradox, but I'm more concerned with rather my understanding of sequential probability is correct.

    All help is sincerely appreciated, and I will be posting back soon after I have read over than advice given before.
  6. Oct 1, 2016 #5
    Do you mean that it should be (1/32)+(31/32)(2/32)+(30/32)(31/32)(3/32) instead? I'm not quite sure I'm thinking properly about my probability.
  7. Oct 1, 2016 #6
    Also, the overall goal is to find an expression which I can give to Mathematica to determine the number of shuffles I need to meet this condition. Honestly, I don't know if I'll actually be able to considering the size of these numbers and Mathematica's number limit. But I'm also considering using approximation methods such as Stirling's Approximation once I understand the probability as a function of shuffles.

    Once again, I cannot thank you all enough.
  8. Oct 1, 2016 #7
    After looking into the birthday paradox, it appears to be the same problem but instead of 365 options, I have 52! options. So, I am a bit skeptical as to whether, approximations or not, I will be able to produce a number answer.
  9. Oct 1, 2016 #8

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Well, using Maple (instead of Mathematica, which I have no access to) I get an answer of about .1057430723e35 as the needed number of shuffles.

    You have the birthday problem, but with ##N = 52!## birthdays instead of 365. Assuming perfect shuffles, the probability that the second shuffles does not match the first is ##p_2 = (N-1)/N = 1 -1/N##. The probability that the third shuffles does not match either of the first two is ##p_3 = (N-1)(N-2)/N^2 = (1- 1/N)(1-2/N)##, etc. So, you want the smallest integer ##k > 1## giving
    $$ \left( 1 - \frac{1}{N} \right) \left( 1 - \frac{2}{N} \right) \cdots \left( 1 - \frac{k-1}{N} \right) \leq 1/2. $$
  10. Oct 1, 2016 #9


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    'subsequent shuffles' or 'the next shuffle'? It doesn't sound like the birthday problem, but perhaps a (IMHO) more interesting one.

    Perhaps what you are searching for is as follows.

    Consider an infinite sequence ##(M_j)_{j\in\mathbb N}##of random variables in ##S_{52}## (which is the names for the set of all 52! permutations of 52 numbers), and let ##A_n## denote the sequence ##\langle M_1,M_2,...,M_n\rangle##, ie the first ##n## orderings of the deck.

    (1) Find the smallest ##n## such that ##E[Prob(M_{n+1}\in A_n)]\geq 0.5##

    In words, find the smallest ##n## such that the expected probability of the ##n+1##th ordering matching one of the ##n## earlier ones is at least 50%.

    To contrast, the birthday problem, using 52! to replace 365, is

    (2) Find the smallest ##n## such that ##Prob(\exists j,k\leq n:\ M_j=M_k)\geq 0.5##

    In words, find the smallest ##n## such that there is at least a 50% probability that, amongst the first ##n## orderings, there exist at least two (numbered ##j## and ##k##) that are identical.

    Let us know if you want to do (1). The birthday one (2) has already been covered.

    EDIT: Ha! I just realised that ##n## will be enormous for problem (1). I suspect it will be more than 52!/2.
    Last edited: Oct 1, 2016
  11. Oct 2, 2016 #10
    I was expecting an answer around order 10^34, so that sounds spot on. Thank you for clarifying my issues with probability. That's actually what I wanted to check more than anything as I'd like to try the problem, the actual solving of it, on my own.
    May I ask how you ended up finding that in Maple? I'd like to see if I can find a similar notation to make a generic case in Mathematica for any N.

    Thank you once again.
    Also, the reason I was expecting that order of magnitude was when I first attempted a solution, I found a probability of about 0.50000001 was given around N=9.89873*10^33. I did this just by changing N until it got to about 0.5 then tweaked it. I probably sound like an idiot right now though so, eh.
  12. Oct 2, 2016 #11
    Oh, by subsequent shuffles I think I meant the next shuffle after N shuffles will have a probability of 0.5, and then shuffles further on would be greater than or equal to 0.5. So I guess subsequent was just referring to the shuffle at which the probability after N shuffles is at least 0.5, or as you put it the next shuffle. Sorry, I'm really bad with language and math. I sincerely appreciate the time you have put into helping me with this question.

    Looking at your cases, I believe I am looking to do case 2, but then again I don't quite understand case 1. If you have time to do so, would you mind giving me a more tangible example of what number 1 would be? It doesn't need to be with playing cards.

    Thank you so very much.
  13. Oct 2, 2016 #12
    EDIT: I also would like to take the time to figure out the actual answer to this question on my own, but what I'm really looking for guidance for is looking at the probability as a function of N so that I may be able to translate its expression into a way Mathematica or another computational tool could help me find a number value like the user using Maple had found. Thank you once again.
    Also, by N I mean it to be the variable that denotes the number of shuffles, I just recognized this inconsistency.
    Last edited: Oct 2, 2016
  14. Oct 2, 2016 #13


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You should not need to use Mathematica, etc.
    If you use the approach I suggested in post #2, you should get a simple equation involving factorials. With Stirling's formula, and a suitable approximation for num trials << N, leads to trials = constant times √N. I'll leave you to find the constant.
  15. Oct 2, 2016 #14
    Would that constant by any chance be (-2ln(1/2))^(1/2)?
  16. Oct 2, 2016 #15


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I got (-ln(1/2))^(1/2), i.e. √ ln(2)
  17. Oct 2, 2016 #16
    I found that p(no match)=e^(-(N^2/(2n)) where n is my number of combinations. Then 1-p(match)=p(no match) and taking the log I get ln(1-.5)=-(N^2/(2n) so N=(-2ln(1/2)*N)^(1/2).
  18. Oct 2, 2016 #17

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    That is essentially the "birthday problem" solution, but as Andrew Kirk pointed out in #9, that may not be the solution to your problem. In the birthday problem the complement of the event {no match in n shuffles} is not the same as the event {n th shuffle is the first match}.

    Formulas for the correct problem are not difficult to obtain. Let events be Dn ={first n shuffles are all different} and Mn= {shuffle n matches one of the other (n-1) shuffles}. The probability of a first match at shuffle n is ##P_n = P(D_{n-1}\: \& \:M_n)##, and you can get this from a simple conditional-probability argument.

    However, If you really want to find an ##n## giving ##P_n \geq 1/2## you are out of luck: you are being asked an ill-posed, impossible question. In fact, the largest single value of ##P_n## for any ##n =1, 2, \ldots, 52!## is about ##P_{\max} \doteq 1/\sqrt{e \, 52!} \doteq 0.675 \times 10^{-34}##.
    The probability mass-function ##P_n, n = 1,2, \ldots 52!## consists of a huge number of tiny numbers that do, however, sum to 1. The birthday problem solution essentially gives you the cumulative distribution of the ##\{P_n\}##, not the individual ##P_n## values.
    Last edited: Oct 2, 2016
  19. Oct 2, 2016 #18
    I'm sorry, but I don't quite understand why the question I asked isn't just the birthday paradox with 52! as the number of days. I may have said something earlier to convince you otherwise.

    So what exactly is the difference between the birthday problem and the other more complicated one? I am fairly new to understanding probability.
  20. Oct 2, 2016 #19

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    There are ##N = 52!## possible shuffles, so the number of the first matching shuffle can be any integer from 2 to 52! (not the 1 to 52! that I said above). So, if ##P_n## is the probability that the first match occurs at shuffle ##n## we have a probability distribution ##\{ P_n \}## on the sample space ##n = 2, 3, \ldots, 52!##. If ##D_k## is the event that the first ##k## shuffles contain no match, then ##1-P(D_k)## is the probability of at least one match among shuffles ##2, \ldots, k## and so is the probability that the first match occurred on or before shuffle ##k##. In other words, it is ##P_2 + P_3 + \cdots + P_k##. That is the cumulative distribution of ##\{ P_n \}## evaluated at ##n=k##, and is what you get from the "birthday" problem analysis.

    We can set
    $$P_k = P(D_{k-1}) P(\text{match at} \; k|D_{k-1}) = (k/N) e^{-k^2/2N}.$$
    This is an approximation, but will be good to more than 20-30 digits when ##N = 52!## and ## k << N##.

    If we set ##k = r \sqrt{N}## we get
    $$ P_k = \frac{r}{\sqrt{N}} e^{-r^2/2} $$.
    Since ##\max_{r > 0} r \exp(-r^2/2) = e^{-1/2} = 1 \sqrt{e}##, we have ##P_k \leq 1/\sqrt{N e}## for all ##k##.
  21. Oct 2, 2016 #20
    Maybe I'm not thinking about this problem correctly, but for the question I'm asking, I don't believe I need a match to be found. I'm just looking for how many shuffles it takes for the probability of shuffles after this number of shuffles matching prior deck arrangements to be 0.5.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted