Hold'em Probability Puzzler

[BruceZ]

The average number of hands to get all 1326 hands is the average number of hands to get the first hand plus the average number of hands to get the second unique hand, etc. The average number of hands to get a hand we haven't seen is always:

average = 1*P(1st not seen) + 2*P(1st seen)P(2nd not seen) + 3*P(1st seen)P(2nd seen)P(3rd not seen) + ...

If p is the probability of getting a hand we've already seen, then

average = 1*(1-p) + 2*p(1-p) + 3*p^2(1-p) + 4*p^3(1-p) + ...

= 1 + p + p^2 + p^3 + p^4 + ... = 1/(1-p)

Now if n is the number of hands we have seen, then p = n/1326. So the average hands needed to see all the hands is:

sum[n = 0 to 1325] 1/(1-n/1326) = <font color="red">10,300</font color>

I evaluated the above sum in excel.


For the original problem of how many 2 cards hands to see every card in the deck, we can use the same method by pretending that we are just are drawing 1 card at a time and replacing it, instead of 2 card hands, then divide the result by 2. This is a slight approximation since with actual 2 card hands you can't have 2 of the same card in your hand. Since drawing the same card twice in a row has low probability, the difference is small and we save alot of work. The above sum becomes:

sum[n = 0 to 51] 1/(1-n/52)/2 = <font color="red">118</font color>

Here's another approximation you can do to get a quick ballpark figure that doesn't require any sums. In order to have a 50% chance of getting all the cards, each card must have a .5^(1/52) chance of appearing if we treat them as independent. This is an approximation since if one card appears, it changes slightly the required chance of other cards appearing. The chance of any card not appearing in n cards is
(51/52)^n = 1 - .5^(1/52). So n = log[1 - .5^(1/52)]/log(51/52) = 222. This happens in 111 hands.


169 hands is more difficult because these hands don't all have the same probability. Pairs have a different probability than non-pairs. Doesn't look like much fun.

[BruceZ]

Note in my solution below I essentially only compute A(N) and set P(N) = 1. All the work you did of accounting for 2 card hands instead of 1 card hands only makes a difference of less than 1 hand in the final answer. Just thought I'd make you feel good [img]/forums/images/icons/grin.gif[/img]

[PseudoPserious]

Heya Huh,

I think I have a solution to the 169-hand problem. Let's see if I can explain it clearly [img]/forums/images/icons/wink.gif[/img]

When you're dealt a 2-card hand, it can either be a pair, an off-suit non-pair (NPo), or a suited non-pair (NPs).

There are 13 different pairs and 6 ways to deal each pair. As there are 1326 total ways to deal two cards, the odds of you getting a pair are thus Pp = 13*6/1326 = 78/1326.

There are 78 different NPo hands and 12 ways to deal each of them. Thus Pnpo = 78*12/1326 = 936/1326.

There are 78 different NPs hands and 4 ways to deal each of them. Thus Pnps = 78*4/1326 = 312/1326.

Consider only the times you are dealt a pair. Using the method outlined in the above posts, it will take you, on average, Sum[13/n, n=13 to 1] = 41.3 times being dealt a pair before you have seen all of the pairs.

Since you are dealt a pair on roughly 6% of all deals (78/1326), it will take you on average Sum[13/n, n=13 to 1]/Pp = 702.8 deals before you've seen all the pairs.

Likewise, it will take you Sum[78/n, n=78 to 1] = 385.3 times being dealt NPo before you've seen all of the NPo. You're dealt 385.3 NPo hands after 545.9 total deals.

Finally, it will take you Sum[78/n, n=78 to 1] = 385.3 times being dealt NPs before you've seen all of the NPs. You're dealt 385.3 NPs hands after 1637.7 total deals.

So, on average, it will take you 1637.7 hands to have seen the 78 NPs. Since by this time you've also seen all of the pairs and NPo, I'd say that the average number of deals to see all 169 is 1637.7 hands.

Does this make sense?
PP

P.S. Once I get back to my computer, I'll modify the little code I wrote to sim this problem a few times.

[Huh]

I like all of the logic, up until the end. Haven't really had the time to work it out, but I suspect the average would move out a little bit because of the NPo and PP. Sure...Most of the time you will see a NPs as the last hand, but some of the time it will be a PP or NPo, which should pull out the average a little bit. Once I have some time I will write a c program, or do the math(gasp).

-Huh?

[Carl_William]

Hi, (BruceZ, Huh, PseudoPserious)

Maybe some "FOOD for Thought"

I again want to thank you people for the posts. I am way behind in comprehending some or most of these posts (I will take my time trying to grasp them). Anyway – I wanted your opinions (I wonder) if any of these solutions are exact or are they all excellent approximations. Myself (initially), without any feedback from Huh, Bruce, or PP: I would have used brute force (Monte Carlo Techniques) to get an answer -- using hopefully an accurate algorithm for pseudo random numbers.

Food for thought:
So far I get the impression from the posts that the original Huh problem statement as an expanding tree type problem where the probabilities at each level are to be calculated and summed. An individual deal is a 2-tuple sample without replacement, and each deal is a sample with replacement. This generates a tree type sequence with an infinite series of terms. I don’t know how to handle this on an exact basis. Maybe I can eventually understand it better. I wanted to mention something to you guys and see if you considered it….

From the posts, the consensus is that on average 117 deals are required to complete the process. Also since the different (or slightly different) techniques used to come up with the answer all predict about 117, I feel that any errors introduced by the various techniques are relatively small. That said: I wanted to see if any of you guys considered working the problem (getting an answer) by starting at the end and working backwards (reverse the tree). I’m just curious if you have considered any merit to this thought – maybe it is trivial and doesn’t deserve considering. Anyway, as you know near the end of the process….

At the end of the process when only one card is missing, on average, 26 deals are required to complete the process. If two cards are missing, about 13.26 or so deals are required to get it down to one card or zero cards. Probably the sequence is about 9.02 deals req’d to get down to one, two, or remain at three cards; and about 6.9 deals req’s to get four cards down to two, three, or remain at four cards (and so on and on). The numbers of deals required at each level reduces eventually (as you know) to about 1.92307 to generate the tree at the initial level. My interest in this was that most of the deals are req’d near the end of the process which may give some additional incite to the nature of the problem.

Also I had a question. Can some this problem be considered a Markoff chain (process), that is does it have Markovian properties.

Most warm regards,

Carl

[PseudoPserious]

Huh,

Good point...my little sim got about 1644 hands and change. Hopefully this afternoon I'll have some downtime and can think about a way to do the math.

PP