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!/((37-n)!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 k-1 items appear, and the ones where k-2 items apear, ..., and the ones where only one item appears. Therefore,

spin2(k,N) = k^N - sum(i = 1, k-1){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, n-1){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 2005-03-24 23:15:32