Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A die (with six sides) is rolled repeatedly and summed. Show that the expected number of rolls until the sum is a multiple of $n$ is $n$.


In

http://www.madandmoonly.com/doctormatt/mathematics/dice1.pdf

problem 12 page 15 a proof is given, assuming that the distribution for the sum of dice values for n > 6 is uniform and equals $\frac{2}{7}$ which is a false assumption that should not be used in a rigorous proof.

share|improve this question
    
Please note that I explicitly say in that pdf that I am not presenting a rigorous proof. –  Matthew Conroy Mar 28 '12 at 0:51
add comment

1 Answer

If $X_m$ is the sum after $m$ rolls, then the process $Y_m=X_m\pmod n$ taking values in $\{0,1,\dots,n-1\}$ is a random walk, considering the state space as points on the circle. By symmetry, its unique invariant probability distribution $\pi$ is uniform over the $n$ states. Therefore the expected time to return to the starting point $0$ is $1/\pi(0)=n$. Since your sum began at $0$, this gives the result.

By the way, this argument works for any (fixed) fair or loaded die with any number of sides. It could even be a one-sided "die", and numbers on it could be positive, negative, and/or zero! I only insist that it is possible to get from any state to any other state. That is, the Markov chain is irreducible.

To prove such results fully, you need the theory of Markov chains on a finite state space. In particular, the topic of "return times". Take a look at the book Markov Chains and Mixing Times by Levin, Peres, and Wilmer, freely available here. Proposition 1.14 (ii) on page 12 gives what you want. Section 1.4 of Introduction to Stochastic Processes (2nd edition) by Gregory F. Lawler also has a good explanation.


Here is an intuitive picture. The Markov chain starts over whenever it hits the state $0$. Writing "$z$" when the chain is in state zero and "$y$" otherwise, a typical outcome looks like

$zyyyyyyyyyyyzyyzzyyyyyyyyyzyyyyzyyyyyyyyyyyyyyyyyyzy\dots$

where we have joined together a sequence of independent finite strings, like $zyyyyyyyyyyy$, of random length. Each finite string starts with one $z$ and has zero or more $y$s following.

The fact that $\pi(z)=1/n$ means that over a very long number of trials, the average proportion of $z$s in the outcome is about $1/n$. To make that work, the average distance between the $z$s must be $n$.

share|improve this answer
    
There is still something not clear. You are talking about a process $Y_n$ defined by $Y_n=X_n\pmod n$. For me this $Y_n$ such as you defined it, is not a process but just a number that has a probability distribution. Or do you mean a process $Y_m=X_m\pmod n$ where m is not necessarily equal to n? –  wnvl Jan 31 '12 at 19:11
    
@wnvl Yes, I was overloading my variables. Corrected. –  Byron Schmuland Jan 31 '12 at 19:33
    
You say "By symmetry, its unique invariant probability distribution π is uniform over the n states." I can imagine that after infinitely many throws the probability distribution of $Y_m=X_m\pmod n$ will be uniform over the n states. But certainly not in the beginning. Assume n>6, then after the first throw the distribution will not be uniform at all. If the process would start from a random location after already infinitely many throws then I can understand yor reasoning about unique invariant probability distribution π over the n states... TBC –  wnvl Jan 31 '12 at 20:11
1  
... In this case however we are sure that we have to start from 0 and if n>>6 we need allready a lot of throws to be in the possibility to have a multiple of n. Would the answer to the question have been different if we started from a random number modulo n? –  wnvl Jan 31 '12 at 20:11
    
@wnvl The initial state doesn't enter into the definition of invariant distribution. I do not claim that the distribution will be uniform after one throw. I'm sorry: I don't see the difficulty. Anyway, the result is true! –  Byron Schmuland Jan 31 '12 at 20:30
show 8 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.