Hold\'em Probability Puzzler
 

How many two-card hands, on average, will it take for you to see every card in a standard deck? I'll post my answer in a couple of days in a separate post. I'm curious to see how people get there.

Huh?

Re: Hold\'em Probability Puzzler
 

Dear Huh,
You wrote:

"How many two-card hands, on average, will it take for you to see every card in a standard deck? I'll post my answer in a couple of days in a separate post. I'm curious to see how people get there.

Huh? "

I appreciate the challenge -- maybe I can solve it. Anyway -- I enjoy thinking about things like this -- maybe an excellent clue would be to solve it for a very small deck -- say 2 cards (too simple), 3 cards, 4 cards (etc.) and then proceed to 52 cards. Thanks again for the excellent post.

Most warm regards,
Carl William

PS: one could do a Bernoulli trial (binomial random variable) and determine the probability that 2 specific cards will or will not be dealt. But I think this is a counting technique problem not unlike the birthday classroom problem where the probability is determined (on average) that two or more people in a class were born on the same birthdate (i.e., month and day of month).

Possible Solution
 

I'll give it a shot...


Let's call N the number of cards you've already seen. Basically, we're looking for the average number of hands it takes to go from N=0 to N=52.

Call A(N) the average number of hands it takes to see a new card, given that you've already seen N cards.

Call P(N) the probability of having seen exactly N cards at some point during the game.

A(N)*P(N) is the expected number of hands you'll be dealt for each value of N.

If you sum A(N)*P(N) over N=0 to 51, you'll get the average number of hands it takes to see the entire deck.


Tackling A(N) first:

Given that you've seen N cards, the probability of being dealt two cards you've already seen is (N/52)*((N-1)/51). Thus, the probability on any one deal of seeing a new card is:

M(N) = 1 - (N/52)*((N-1)/51)).

We're looking for the average number of independent trials (hands) it takes for us to see our first success (our first hand with a new card). This is the geometric distribution. The mean of the geometric distribution with probability of success p is 1/p.

So, A(N) = 1/M(N)


Now for P(N):

You will NOT see exaclty N cards at some time during the game if and only if (a) you have seen exactly N-1 cards and (b) the next time you are dealt an unseen card, you are dealt two unseen cards instead of just one.

We've already defined the probability of (a) as P(N-1).

The probability of (b) is the fraction of times that you receive two unseen cards when you are dealt at least one unseen card, given that you've seen N-1 cards. We'll call this T(N-1).

Given that you've seen (x) cards, on any one deal the probability of being dealt two unseen cards is P2(x) = ((52-x)*(51-x))/(52*51). The probability of being dealt exactly one unseen card is P1(x) = 2x(52-x)/(52*51).

So, T(N-1) = P2(N-1) / (P1(N-1) + P2(N-1))

Thus, we can find the chance of skipping a value of N by P(N-1)*T(N-1). This gives us an iterative formula for the chance of seeing exactly N cards:

P(N) = 1 - P(N-1)*T(N-1)

Along with P(0) = 1 (since we have seen no cards before the first deal) and P(1) = 0 (since the first deal will always give us two unseen cards), this allows us to calculate P(N) for all values of N.


Using the above definitions, if you sum A(N)*P(N) from N=0 to 51, you get 117.09.


So, I'd have to say just over 117 hands or so...


Cya,
PP


P.S. A quickie computer sim of 20,000 games gave an average of 117.65 hands.

Re: Possible Solution
 

Dear Cya,
PP


So you solved the problem for a one card hand not a two card (holdem) hand....
You indicated about 117 hands and wrote,

"P.S. A quickie computer sim of 20,000 games gave an average of 117.65 hands."

Cya, of course if your solution is valid than you can use the same approach for holdem hands.
Unless I don't understand Huh's problem statement -- I thought Huh was talking about 2 card holdem hands. There are 1326 distinct holdem hands in a 52 card deck. Therefore it has to be 1326 or more "usually way more" deals to get dealt every holdem hand combination.

Most warm regards,

Carl William

Re: Hold\'em Probability Puzzler
 

Huh,

I don't know how to solve your problem definition yet -- at least in a closed analytical form. I do know how to solve the problem using brute force (Monte Carlo technique). Just randomly deal out integer numbers from 1 to 1326 until all 1326 numbers are in this sequence sample. Then count how many (deals) it took to get this sample. Repeat this sequence sample process over and over, each time recording how many deals were required. Keep a running average of the deals required for each sequence -- when the running average converges within say plus or minus one deal you will have a pretty accurate answer to your problem.

Regards
Carl William

Re: Possible Solution
 

Hey Carl,

1) I'm PP, not Cya...I was saying 'see you' [img]/forums/images/icons/wink.gif[/img]

2) I think he was asking how many hold'em hands it would take on average to see every card in the deck, not how many to see every possible hold'em hand. To quote:

"How many two-card hands, on average, will it take for you to see every card in a standard deck?"

But anyways, if that's not what he was asking, that's the problem I solved [img]/forums/images/icons/smile.gif[/img]


Take care,
PP

Re: Hold\'em Probability Puzzler
 

Heya Carl,

I'm in a bit of a rush, so I haven't thought about it very much, but why can't you can solve your interpretation of Huh's problem using the same method I did above?

PP

Re: Hold\'em Probability Puzzler
 

PP, you are correct -- I misread the problen definition. One of my faults. You wrote:

"I'm in a bit of a rush, so I haven't thought about it very much, but why can't you can solve your interpretation of Huh's problem using the same method I did above?"

I will think about the correct definition. You are probably right all the way. Thank you.

Carl

Re: Hold\'em Probability Puzzler
 

Hey Carl,

Okay, here's how I would figure out the average number deals it would take to be dealt every possible hold'em hand (1326 possible hands).

Call N the number of hands you haven't seen.

The probability of getting a hand you haven't seen is
P(N) = N / 1326

From the mean of the geometric distribution, the average number of deals it will take you to see a hand you haven't seen before is:
A(N) = 1326/N

The average to get from N=1326 (prior to the first deal) to N=0 (just after your dealt the final 1326th hand) is then
A = Sum [ 1326/N , N=1326 to 1]

This works out to, oh, quite a lot (just shy of 10300).

Cya,
Pseudo

I like your problem more lol.
 

The original post was about seeing every card..Not every hand...But i think that is more interesting anyhow.

I got 117 also, slightly different math methods, but similar, then I wrote a small c program to take two unique rand() % 52 numbers and check off a list(0-51) a million times to check my work.

I like to look at numbers like this to randomize my play a bit (translation : raise for no good reason). I usually use some obscure fact about my previous hand so I like to look at these stats.

When I have some time I am going to look at the every possible starting hand problem. I am kindof curious about the 169 hands (lumping suited similar cards together, moreso than the 1326 hands, but both are cool.)

huh?

Simple solution (both problems)
 

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.

Re: Possible Solution
 

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]

Re: I like your problem more lol.
 

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.

Re: I like your problem more lol.
 

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?

Re: Possible Solution
 

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

Re: I like your problem more lol.
 

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