TransWikia.com

probability that the number of roulette spins until the sum of the spins exceeds a given number

Mathematics Asked by AB Balbuena on February 18, 2021

A roulette wheel is labelled $1$ through $n$, with each number having
the same probability of being selected and each spin of the roulette is
independent of the other spins. We spin the roulette until the
sum of the numbers selected is strictly greater than $n$. Let $S$ be the number of spins it takes for the sum to be strictly greater than $n$. For an integer $m$
such that $0 leq m leq n$, find the probability that $operatorname{Pr}(S geq m+1)$?

I understand the continuous version (a sequence $x_j$ is sampled from a uniformly distribution on the interval $[0,1]$ and you continue until the sum is more than 1) has expected value $e$ for the number of samples to get to a sum that exceeds 1. That I understand but in this case, I’m lost on what is multiplied to $(1/n)^m$ (representing the first $m$ roulette spins) as my calculations don’t give $e$ as a limit.

How can one obtain an expression for the probability that $S$ is at least $m+1$? In particular, what is multiplied to $(1/n)^m$?

EDIT: Previous problem incorrectly stated $S$ to be the sum of the spins, when it should be the number of spins for the sum to exceed $n$

One Answer

We have : $$ P(S geq m+1) = P(X_1 + ... + X_m leq n) $$

where $X_i$ are iid uniformly distributed in ${1,2,...,n}$. Therefore, it is sufficient to find the RHS.

The answer is just $sum_{1 leq i_1,...,i_m leq n} 1_{i_1+...+i_m leq n} P(X_1 = i_1,X_2 = i_2,...,X_m = i_m)$, which just becomes $frac {K}{n^m}$, where : $$ K = |{(i_1,i_2,...,i_m) in {1,2,...,n}^m : i_1+i_2+...+i_m leq n}| $$


We claim that the set given in the definition of $K$ is in bijection with the set ${(i_1,i_2,...,i_m) in {0,1,...,m}^m : i_1+i_2+...+i_m leq n-m}$. The bijection is given by taking a tuple and subtracting $1$ from each entry. It is easy to see, as $n>m$ that the bijection holds.

Now, we adjoin an index $i_{m+1} = n-m - (i_1+...+i_m)$, so we get that the above set is in bijection with : $$ {(i_1,i_2,...,i_m,i_{m+1}) in {0,1,...,m}^{m+1} : i_1+i_2+...+i_m +i_{m+1} = n-m} $$

by projection onto the first $m$ coordinates.


This last set is calculated using stars and bars. Indeed, imagine a set of $n$ blanks, each filled with a $|$ or a $circ$ (ball), so that there are exactly $m$ of $|$ and $n-m$ of $circ$. $$ underbrace{|circ||circcirccirc|circ||...|circ| circ circ}_{text{$n$ blanks}} $$

The bars separate the circles into $m+1$ parts, each containing $i_1,...,i_{m+1}$ number of circles, which total to $n-m$ circles, and each of which is non-negative. In the example above, $i_1 = 0,i_2 = 1,i_3 =0 , i_4 = 3$ and so on.

It is easy to see that the number of ways of placing these bars and circles is the same as the number of elements in the set mentioned earlier. But we are basically placing $m$ bars into $n$ slots : the answer to this is just $binom{n}{m}$.


Thus, we basically have $K = binom{n}{m}$, with $Pr(S geq m+1) = frac{binom{n}{m}}{n^m}$.

The expectation of $S$ is equal to $sum_{i=0}^n binom ni n^{-i} = (1 + frac 1n)^n to e$ as $n to infty$ (i.e. as we approach the uniform distribution)

Correct answer by Teresa Lisbon on February 18, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP