DorothyGale
Joined: Nov 23, 2009
• Posts: 639
October 15th, 2010 at 4:24:59 PM permalink
While I was milking the pigs today, I thought of a little problem. Nothing this simple is new, but it's got some twists to it.

Suppose you're playing American roulette ... 38 numbers. What is the expected number of spins until all the numbers 1..36, and 0 and 00 have each been hit at least one time?

In general, given numbers 1 .. N and a random number generator that generates values from 1 to N, what is the expected number of numbers the generator will have to turn out until it has hit each of 1, 2, 3, ... up to N?

For example, with N = 2, the answer is 2*(1/2) + 3*(1/4) + 4*(1/8) + 5*(1/16) + ... = 3. So, the expected number of flips of a coin to get both heads and tails to appear is 3.

It's kind of the opposite of the birthday problem. How many people do you need to have in a room so that you expect every birth date to be hit by one or more people?

Oh, well, this is probably well known ... and I think I know the answer for roulette ... just in case no one cares ...

--Ms. D.
"Who would have thought a good little girl like you could destroy my beautiful wickedness!"
FleaStiff
Joined: Oct 19, 2009
• Posts: 14484
October 15th, 2010 at 5:28:54 PM permalink
Quote: DorothyGale

While I was milking the pigs today,

I didn't know they even had pigs in Australia much less that pigs got milked!

>So, the expected number of flips of a coin to get both heads and tails to appear is 3.
I wish I understood that proof more clearly. Certainly 2 tosses are the minimum that is required and a certain probability exists for further tosses that both Heads and Tails will appear.

Are you thinking of establishing a FireBet for roulette?
DorothyGale
Joined: Nov 23, 2009
• Posts: 639
October 15th, 2010 at 5:34:13 PM permalink
Quote: FleaStiff

Are you thinking of establishing a FireBet for roulette?

No, I don't care about applications of this question. Though I do see the relationship ... maybe someone else who cares can make a side bet out of it and say it's the world's best new idea and make a ton of money, I don't care ...

Ms. D.
"Who would have thought a good little girl like you could destroy my beautiful wickedness!"
mkl654321
Joined: Aug 8, 2010
• Posts: 3412
October 15th, 2010 at 6:18:11 PM permalink
Well, we all know that the longer it has been since a roulette number has hit, the more it becomes "due".

Therefore, after one spin, there are 37 numbers that are due, and one that isn't. This continues until 37 numbers have come up, and there is one number left, which is so, like, totally due that it is certain to hit.

Therefore, I say the answer is 39 spins (not 38, because one has to take into account atmospheric and gravitational disturbances).

Before I read all the surefire roulette systems posted on this board, and absorbed their mighty wisdom, I might have resorted to silly old math to obtain my answer. This way is so much easier!
The fact that a believer is happier than a skeptic is no more to the point than the fact that a drunken man is happier than a sober one. The happiness of credulity is a cheap and dangerous quality.---George Bernard Shaw
Kelmo
Joined: Aug 15, 2010
• Posts: 85
October 15th, 2010 at 6:26:05 PM permalink
Quote: DorothyGale

While I was milking the pigs today, I thought of a little problem. Nothing this simple is new, but it's got some twists to it.

Suppose you're playing American roulette ... 38 numbers. What is the expected number of spins until all the numbers 1..36, and 0 and 00 have each been hit at least one time?

In general, given numbers 1 .. N and a random number generator that generates values from 1 to N, what is the expected number of numbers the generator will have to turn out until it has hit each of 1, 2, 3, ... up to N?

For example, with N = 2, the answer is 2*(1/2) + 3*(1/4) + 4*(1/8) + 5*(1/16) + ... = 3. So, the expected number of flips of a coin to get both heads and tails to appear is 3.

It's kind of the opposite of the birthday problem. How many people do you need to have in a room so that you expect every birth date to be hit by one or more people?

Oh, well, this is probably well known ... and I think I know the answer for roulette ... just in case no one cares ...

--Ms. D.

Just a guess, but would it be around 514 or so? Approximation using ln2?
Kelmo
Joined: Aug 15, 2010
• Posts: 85
October 15th, 2010 at 6:43:04 PM permalink
Quote: Kelmo

Just a guess, but would it be around 514 or so? Approximation using ln2?

A better guess, about 158-160?
miplet
Joined: Dec 1, 2009
• Posts: 1963
October 15th, 2010 at 6:54:23 PM permalink
160.66 according to the Wizard.
“Man Babes” #AxelFabulous
Wizard
Joined: Oct 14, 2009
• Posts: 23117
October 15th, 2010 at 7:34:33 PM permalink
160.6602765.

I'll refrain from giving a solution to let others enjoy the problem.
It's not whether you win or lose; it's whether or not you had a good bet.
Wizard
Joined: Oct 14, 2009
• Posts: 23117
October 15th, 2010 at 8:22:34 PM permalink
Quote: miplet

160.66 according to the Wizard.

I forgot I answered that. How did you dig that up?
It's not whether you win or lose; it's whether or not you had a good bet.
DorothyGale
Joined: Nov 23, 2009
• Posts: 639
October 15th, 2010 at 8:30:24 PM permalink
Mr. Wizard, sir ... reading this post here., you said:
Quote: Mr. W

Once you have hit n numbers the probability of getting a new number on the next spin is (38-n)/38. If the probability of an event is p then the expected number of trials before it happens is 1/p. Thus the expected number of spins to get a new number, given that you already have n, is 38/(38-n). For example once you have hit 20 numbers the expected number of spins to get the 21st is 38/18=2.11. So the answer is the product of the expected number of spins at each step: (38/38)*(38/37)*(38/36)*...*(38/1)=160.66. March 11, 2001

The answer 160.66 is right. That's what I got too. But, I think you want to "add" the numbers, not "multiply" them.

(38/38) + (38/37) + (38/36) + ... (38/2) + (38/1) = 160.66.

--Ms. D.
"Who would have thought a good little girl like you could destroy my beautiful wickedness!"