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

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)