A Question on rec.gambling.poker

[irchans]

Harry026 posted the following question to rec.gambling.poker

>Suppose you decide to make a list of all 1326 starting hands. Starting with your next hand, you intend to mark a hand as "gotten" whenever it is dealt to you. What is the number of hands that you must be dealt for the probability to be at least 50% that all 1326 hands on your list have been marked "gotten"?

Brian Alspach got the exact solution using advanced mathematics.

David Sklansky gave a nearly exact approximate solution that was correct if you rounded off to the nearest integer.

Any comments?

I'll take a stab at this one:

10300 hands.

Here's my thought process...

1) The problem is asking for 'the number of hands that you must be dealt for the probability to be at least 50% that all 1326 hands on your list have been marked'. This seems to be the same as asking: 'On average, how many hands will it take for you to mark off all of the hands?'.

2) The average number of hands you need dealt to go from zero marked off to 1326 marked off is the same as adding the average number of hands dealt to go from 0 to 1, from 1 to 2, from 2 to 3, ..., from 1324 to 1325, and from 1325 to 1326.

3) Assume you've just marked your xth hand off the list. The number of subsequent hands it'll take you to mark off the (x+1)th hand is governed by a geometric distribution with probability of success

p = (N - x) / N,

where N is the total number of hands, x is the number of hands you already have marked, and (N - x) is the number of hands you haven't yet marked.

Asking for the average number of hands it'll take you to mark off the (x+1)th hand is the same as asking for the mean of the geometric distribution with this p. As the mean of the geometric distribution is

mu = 1 / p,

the average number of hands it'll take to mark off the (x+1)th hand is N / (N - x).

4) So, the average number of hands needed to mark off half of the list is the summation of N/(N-x), as x runs from 0 to 1325, where N = 1326.

This works out to 10299.72 or so, so you need 10300 hands on average.

Is this anywhere close? What's the real answer? Tell me, I want to know.

PP

[BruceZ]

I didn't see Sklansky's solution on RGP; is it there? I did see where he blasted Alspach for insisting on using advanced math where an approximate solution would do. The problem in question was similar to one solved here, where the exact solution requires inclusion-exclusion, but where the assumption of independence is very accurate.

Here's a way to to this problem using the assumption of independence. I assume this is probably how Sklanksy did it too. We assume the probability of any hand occuring is independent of the probability of any other hand occuring.

In order to have 50% probability of every hand occuring, we must have each hand occuring with probability p where p^1326 = .5. So p = .5^(1/1326) = .9994774. The probability of any hand not occuring is
1 - .9994774 = .0005226. But the probability of a hand not occuring is also
(1325/1326)^n = .0005226. If you don't know about logarithms, you can solve this equation by trial and error. If you know about logarithms (and even if you don't) the solution is:
n = log(.0005226)/log(1325/1326) = 10,016 hands.

[BruceZ]

1) The problem is asking for 'the number of hands that you must be dealt for the probability to be at least 50% that all 1326 hands on your list have been marked'. This seems to be the same as asking: 'On average, how many hands will it take for you to mark off all of the hands?'.

This is absolutely not the same thing. The average value does not in general coincide with 50% probability. The issue is the difference between the mean and the median, the median being the value at which half will lie above and half will lie below. We want the median in this problem, and you have attempted (perhaps successfully) to calculate the mean.

There are some problems where the 50% probability is finite, and the expected value is infinite. An example is the time it takes to go broke playing an even money game against an infinitely wealthy opponent. The average time is infinite, but the time it takes to have a 50% probability of busting out is finite.

[irchans]

Pseudo,

That is the correct answer for the alternative question "What is the expected number of deals to get all 1326 hands?" As Bruce points out, that is not quite the same question, but I like your method for figuring it out and the exact solution to the alternative question is a good estimate for the original question.

[irchans]

BruceZ,

I think your method is the same a Sklanky's, but he got 10019.8 I think /forums/images/icons/confused.gif . Can you get the exact solution?

Alspach got 10,019 using a math package that computed Stirling numbers of the second kind. The Stirling numbers are the number of ways to partition a set of n elements into k disjoint subsets. Let me know if you figure out how this works, I'm still looking into it. I suspect you can use inclusion-exclusion for each value of n, where each term represents the number of ways to get at least k repeats. This would explain why you need software.

Are you sure Sklansky got this same number? If you don't carry all the significant digits in the approximation method your answer can be off considerably.

[BruceZ]

Not sure why it put in anonymous, maybe it logged me off.

-BruceZ