Roulette Question

[LetYouDown]

From another site...just curious how anyone here would approach it.

Looking for a formula to determine how many different numbers you should expect to get when you spin the wheel N times.

How many spins are required to makes the odds worse than a million to 1 that all 37 numbers have appeared?

Obviously I'm talking about Single 0 Roulette.

[Siegmund]

Here is one way to approach it.

On the first spin, a number comes up, and you cross it off your list.

On the next spin, you have a 36/37 chance of getting a new number; spin again if you get a repeat. Cross off the new number. Start a new series of spins with a 35/37 chance of getting a new number. Continue until you're down to 1/37.

Each of these series is pretty easy to calculate on its own. Then we just add them up.

When your probability of success is p, your expected number of spins until you succeed is 1/p, with variance (1-p)/p^2.

So, for your answer, we just add it up:

Expected number of spins: 1 + 37/36 + 37/35 + ... 37/1 ~ 155.46.

Variance: 0 + 37/36^2 + 2*37/35^2 + 3*37/34^2 + ... 36*37/1^2 ~ 4383.


The exact shape of the distribution is complicated. But for a lower bound, the tail is thicker than a normal distribution's tail. So going 4.75 distributions to the right of the mean (470 spins) will not be enough to achieve the desired probability. In fact, the last series alone, just getting the 37th number, will take more than 504 spins 1/1000000 of the time.

I will think more about how to pin down the number of spins to reduce the probability to 1000000:1 and post again, unless someone beats me to it.

Edit: a brute force transition-matrix-multiplication in Mathematica says that the odds of missing a number are 999319:1 after 636 spins and 1027078:1 after 637. But I'd still love to see a nice pretty way to derive this number or a good approximation to it / a verification I didn't garble the matrix along the way.

[shday]

here's another answer (to the second part of your question).

37^x is the number of possible outcomes for x spins.

36^x is the number of possible outcomes for x spins discluding one number.

solving 37^x/36^x = 1000000 for x gives 504.2

This means that you would have to spin 505 times for the probability of failing to spin all the numbers to be less than 1 in a million.

[AaronBrown]

This is the number of spins required to reduce the probability of missing any specific number to 1 in a million. But with 37 numbers, the chance of some number missing is about 37 in a million.

(37/36)^636 is about 37 million. Since the probability of missing two numbers is negligible, this is pretty close to the correct answer.

[pzhon]

[ QUOTE ]
Looking for a formula to determine how many different numbers you should expect to get when you spin the wheel N times.

[/ QUOTE ]
The count of numbers hit C is X_0 + X_1 + ... + X_36, where X_i is 1 if the number i was hit, and 0 otherwise.

E(C)
= E(X_0 + X_1 + ... + X_36)
= E(X_0) + E(X_1) + ... + E(X_36)
= 37 E(X_0)
= 37 Probability(0 is hit)
= 37 (1-Probbaility(0 is not hit))
= 37 (1 - (36/37)^N))

Here are some examples:

N=0: 0
N=1: 1
N=2: 73/37 = 1+36/37
N=10: 8.86742
N=100: 34.61065
N=1000: 36.99999999995333638

[ QUOTE ]

How many spins are required to makes the odds worse than a million to 1 that all 37 numbers have appeared?


[/ QUOTE ]
I guess you mean you want the probability that not all have been covered to be less than about 1/(1 million). An easy estimate is that this is true when the expected count of numbers hit is at least 36.999999, which happens for N=637, E(C)=36.99999902.

To get a more exact answer, we can use the method of inclusion-exclusion. Let S_i be the event that the number i is missed. We want to compute P(S_0 or S_1 or ... S_36). By inclusion-exclusion, this is

Sum_i P(S_i) - Sum_i,j P(S_i and S_j) + Sum_i,j,k P(S_i and S_j and S_k) - ...

One nice thing about this sum is that each of the terms is easy to compute: P(S_1 and S_2 and ... S_k) is the probability the numbers 1-k have been missed, ((37-k)/37)^N, and the kth sum is over (37 choose k) equal terms.

Since we know 637 suffices, let's look at the results of adding the first k terms for 636:

k=1: .000001000681118823863989081782978042813484384335
k=2: .000001000680820660740502103320107245355764311196
k=3: .000001000680820660774756454911077612432679840001
k=4: .000001000680820660774756453257558571919729057132
k=5: .000001000680820660774756453257558606471760392939
k=6: .000001000680820660774756453257558606471760079522
k=37:.00000100068082066077475645325755860647176007 9522

You can see the rapid convergence of inclusion-exclusion, and the way the terms alternate signs. The sum of the first two terms is an underestimate, and is already greater than 10^-6, so the probability of missing at least number after 636 spins is greater than 10^-6.

If you meant that you want the probability of hitting all 37 numbers to be greater than about 1/(1 million), the same techniques work, though the convergence of inclusion-exclusion is not as rapid. The probability of covering all numbers by the 54th spin is about 1.38 x 10^-6, and the probability of covering all numbers by the 53rd spin is about 7.72 x 10^-7.


Mathematica code:<ul type="square">
f[n_] := 37(1 - (36/37)^n)

g[n_, t_] := Sum[Binomial[37, k]((-1)^(k + 1))((37 - k)/37)^n, {k, 1, t}]
[/list]

[shday]

Thanks, I missed that...

[BruceZ]

[ QUOTE ]
I will think more about how to pin down the number of spins to reduce the probability to 1000000:1 and post again, unless someone beats me to it.

Edit: a brute force transition-matrix-multiplication in Mathematica says that the odds of missing a number are 999319:1 after 636 spins and 1027078:1 after 637. But I'd still love to see a nice pretty way to derive this number or a good approximation to it / a verification I didn't garble the matrix along the way.

[/ QUOTE ]

Let p = the probability that a specific number fails to appear in N spins such that the odds against not hitting all 37 numbers is a million-to-1. We can bound p as:

1/37 * 1/1,000,001 &lt; p &lt; 1 - (1,000,000/1,000,001)^(1/37)

The left side of the inequality would be equal if the numbers were mutually exclusive, and the right side would be equal if the numbers were independent.

1/37,000,037 &lt; p &lt; 1/37,000,019

p = (36/37)^N

N = ln(p)/ln(36/37)

636.0248695 &lt; N &lt; 636.0248873

637 spins required to meet the objective.