# Gambling Problem (part 2)

The last post concerned a game based on a slot machine that generates random numbers between 0 and 999. The player keeps pulling the handle to generate a sequence of these numbers, and the machine keeps track of them. The game ends when any number shows up a second time. That is, as long as all the numbers generated are unique, the player keeps pulling the handle. Simulation of the game showed that the expected number of pulls until the game ends is about 40.3. In this post I’ll develop an analytical solution.

Of course it’s not possible to win on the first pull, but what is the probability of winning on the second pull? The machine has already generated a number between 0 and 999. The probability of generating that same number again is $\frac{1}{1000}$, so $p_2 = \frac{1}{1000}$.

To win on the third pull, the numbers generated on the first two pulls must be different. After the first number is generated, the probability of generating a different number on the second pull is $\frac{999}{1000}$. The probability that the third number will be one of the two already generated is $\frac{2}{1000}$, so $p_3 = \frac{2 \times 999}{1000^2}$.

To win on the fourth pull, the numbers generated on the first three pulls must all be different. The probability of that happening is $\frac{999 \times 998}{1000^2}$. The probability that the fourth number is the same as one of the first three is $\frac{3}{1000}$. So $p_4 = \frac{3 \times 999 \times 998}{1000^3}$.

Now we can write the general expression for the probability of winning on the kth pull:

$p_k = \frac{(k - 1) P(1000,k-1)}{1000^k}$

where

$P(a,b) = \frac{a!}{(a-b)!}$

Finally, the expected number of pulls is given by:

$\sum\limits_{k=2}^{1000} \frac{k(k - 1) P(1000,k-1)}{1000^k}$

I don’t know if there’s a way to write that summation in closed form, but I wrote the following little program to evaluate it:

sum <- 0
p <- 1/1000
for(k in 2:1000) {
sum <- sum + k*(k-1)*p
p <- (1000-k+1)*p/1000
}
cat(sum,"\n")


This gives the expected number of pulls as 40.30321.

BONUS QUESTION: Consider another game played with the same type of machine. The player inserts a twenty dollar bill. As before, the player can pull the handle as many times as desired. The machine keeps track of the numbers generated and the number of times the handle has been pulled. At any point, the player can “cash out” and receive a payment equal to the number of times the handle has been pulled. The difference here is that if the player generates a number that has already turned up, the game ends and the player receives nothing. In the long run, how much can players expect to win from this machine per play?