Rolling a die

[radosr]

You roll a fair n-sided die repeatedly and sum the outcomes. What is the expected number of rolls until the sum is a multiple of n?

 

[Jing Chen]

You roll a fair n-sided die repeatedly and sum the outcomes. What is the expected number of rolls until the sum is a multiple of n?

n

 

[radosr]

n

Good! But how and why?

 

[Tom Maloney]

Good! But how and why?

Jing Chen just knows.

I think it involves a derivative of a geometric series. But I'm too lazy to TeX it out...

 

[Tom Maloney]

Look at what you have me doing Rados... on a Friday night!

Let (Y) be the number of rolls it takes until the sum equals a multiple of (n). Let (X_i) be the results of the rolls. Let's think about (P(Y=k)).

The first roll is a multiple of (n) only when it lands on (n), so (P(Y=1) = \frac{1}{n}).

For (Y=2), the first roll cannot land on (n), so there are (n-1) choices. The second roll has to land on the unique number such that (X_1 + X_2 = n). Therefore (P(Y=2) = \frac{n-1}{n} \frac{1}{n}).

Someone more elegant than me can explain that (P(Y=k) = \frac{(n-1)^{k-1}}{n^k}).

Therefore (\mathbb{E}[Y] = \sum_{k=1}^{\infty} k P(Y=k) = \sum_{k=1}^{\infty} k \frac{(n-1)^{k-1}}{n^k}).

Note that (\frac{d}{dn} \bigg( \frac{n-1}{n} \bigg)^k = \frac{1}{n} k \frac{(n-1)^{k-1}}{n^k}.)

Therefore (\mathbb{E}[Y] = \sum_{k=1}^{\infty} n \frac{d}{dn} \bigg( \frac{n-1}{n} \bigg)^k = n \frac{d}{dn} \sum_{k=1}^{\infty} \bigg( \frac{n-1}{n} \bigg)^k = n \frac{d}{dn} \bigg( \frac{1}{1-\frac{n-1}{n}} - 1 \bigg) = n \frac{d}{dn} (n-1) = n.)

 

[koupparis]

Easier way, let E be the number of rolls required until you get a multiple of n. Then E = 1/n + (n-1)/n*(E+1) hence E = n.

 

[jovens]

Correct answer but not that trivial, let (E_n) be the event of multiple of n, and in general E(j) be the event of residue j mod n.
then we have n equations:

(E(j)= 1/n+1/n\sum_{k\neq j} (E(k) +1))

then the solution is E(j)==n, for any j.

 

[koupparis]

Note that E(i) = E(j) =E for any i, j, rearrange and you have what I wrote.

 

[Karth]

Easier solution: consider the cumulative sum of the dice rolls modulo n. After each roll, there is only one way to get this number to 0 modulo n. This problem is thus equivalent to computing the expected value of a geometric distribution with parameter p = 1/n, which is just n.