If I spin the roulette (numbers from 0 to 36) N consecutive times, how many
different numbers should I expect to get?
(If N=1, your formula should give 1 as an answer, but for N=2, it should be a little under 2, and for all other N, the formula should be less than the minimum of N and 37.)
Another question: how many times should you spin the roulette, so chances are better than one in a million, that all 37 numbers will have appeared?
I did not understand the "exclusion principle" Charlie talks about, so I
investigated the second part of the problem further and came up with my
own solution.
Lets call N be the number of spins of the roulte, and n be how many different
numbers have been hit. For example, N = 5, n = 4 result from the
sequence of spins (17,0,3,35,3).
But, for a given n and N, how many different spin sequences exist?. I'll call this numer spin(n,N).
This number can be factorized into two multiplicative terms, spin(n,N)
= spin1(n)*spin2(n,N).
The first term is given by the different ways we
can get a subset of n different numbers from the bigger set of 37; it
is simply the familiar spin1(n) = comb(37,n) = 37!/((37n)!n!).
The second term corresponds to how many ways a particular set of n
distinct numbers can be arranged in a row N numbers long, where each
number appears AT LEAST once. For example, if n = 2 (i'll label the
numbers 1, 2), and N = 3, then checking for valid combinations gives,
111 > No (2 does not appear)
112 > Yes
121 > Yes
122 > Yes
211 > Yes
212 > Yes
222 > no (1 does not appear)
and therefore spin2(2,3) = 6.
It sounds simple enough, but I cannot find a general formula for
spin2(n,N) (is it possible?). In the two extreme cases it is simply
spin2(1,N) = 1, and spin2(N,N) = N!, but I can't do better than that.
To get the general spin2(n,N), I need to go through an iterative process,
1. Start with n = 1. It is obvious that,
spin2(1,N) = 1.
2. Next take n = 2. Think of all posible combinatinons (2^N) and take
away the combinations where only one item appears (there are two of
these),
spin2(2,N) = 2^N  2.
So far so good, because as we found prevously spin2(2,3) = 6,.
3. Next take n = 3. Think of all possible combinations (3^N) and take
away the conbinations where only two items appear (remember that there
are 3 ways to get the two items), and also the ones where only one item
appers (also remember that there are 3 ways to get the one item),
spin2(3,N) = 3^N  3*spin(2,N)  3*spin(1,N).
As a check we calculate spin2(3,3) = 6, which is consistant with the expected spin2(N,N) = N! property.
.....
k. Next take n = k. Think of all possible combinations (k^N) and take
away the combinations where only k1 items appear, and the ones where
k2 items apear, ..., and the ones where only one item appears.
Therefore,
spin2(k,N) = k^N  sum(i = 1, k1){comb(k,i)*spin2(i,N)}
This is a recursive formula for spin2(k,N). Combining the two terms,
spin(n,N) = comb(37,n)*[n^N  sum(i = 1, n1){comb(n,i)*spin2(i,N)}]
To turn the combinations into a probability, we simply divide by the
total number of combinations, 37^N. For computing purposes (to avoid
infinities) it is convinient to first divide by 37 and then
exponentiate. This gives the following recursive formula for the
probabilities of a particular (n,N) pair;
**********************************
prob2(1,N) = (1/37)^N
....
prob2(n,N) = [(n/37)^N  sum(i = 1, n 1) {comb(n,i)*prob2(i,N)}]
Finally,
prob(n,N) = comb(N,n)*prob2(n,N)
*******************
At this point we are in great shape. The solution to the first part is
known already, but now we know the entire probability distribution, so
it should be equal to,
<n> = sum(i = 1, 37){i*prob(i,N)}
And the solution to the second part is given simply by the smallest N
that satisfies the equation prob(37, N) > 999999/1000000.
At this point a computer is needed to carry out these calculations.
Once the iterative formula is coded here are the answers I get,
1st part) For example take N = 15, <n> = 12.47 in agreement with
Charlie's simple formula. Also, the most likely n is 13 with a
probability of 30% while n = 12 has a probability of 28% and n = 14 has
a probability of 17%.
2nd part) I agree with Charlie's answer (I'm surprised that our numbers
are so much in agreement b/c numerically I was expecting us to have
different rounding errors). To contribute something new I'll say that
the outcome of hitting all 37 numbers becomes the most likely one after
137 spins (with prob(37,137) = 39.90% and prob(36,137) = 38.95%).
This problem was lot's of fun. I don't think it deserves such a low dificulty rating. Thanks for posting it.

Posted by ajosin
on 20050324 23:15:32 