# Number of dice rolls taken to reach a certain sum

I was reading about sums of dice rolls and Chernoff bounds, and I thought of a question I couldn't obviously answer with the techniques I know.

You're given some number $x$ and told it was generated by summing subsequent (I.I.D.) rolls of an $n$-sided die, where the sides are numbered $1, 2, ..., n$. Let $X$ be a random variable representing the number of rolls that were summed.

What do we know about the distribution of $X$? Can we analyze it using Chernoff bounds?

To make it more concrete, say you're given the number 36 and told it is the sum of rolls of a standard six-sided die. It's very unlikely that it took 36 rolls for the sum to be 36 (the probability of 36 '1's in a row) and it's similarly unlikely that it only took six rolls (six '6's in a row - interestingly this is much more likely than the other extreme).

Thanks very much for your help.

• The question does not define the distribution of the random variable $X$. You might want to make your idea more precise. – Did Apr 3 '14 at 23:02
• @Did, I think what OP wants is the probability of having observed a sum $S$ in the $k$'th roll, conditioned on the event that the sum $s$ has been observed at some point during the experiment. – Hoda Apr 4 '14 at 1:05
• @Hoda This is an option (with S=s, I guess). Maybe the OP will tell us... – Did Apr 4 '14 at 5:53

It is easy in practice to find the probability that the partial sum after $t$ dice throws is $s$ using a recurrence: $$P(S_t=s)=\sum_{i=1}^6 P(S_{t-1}=s-i)/6$$ starting with $P(S_0=0)=1.$ For example $P(S_{6}=36)= \frac{1}{6^{6}}$, $P(S_{7}=36)= \frac{917}{6^{7}}$ and $P(S_{36}=36)= \frac{1}{6^{36}}$.

If you suppose that the target $x=36$ was set in advance, the probability the target is hit is $\sum_t P(S_t=36) \approx 0.285711734$. So assuming you are asked the question when the target is hit (and if not then the experiment is restarted), you can work out the conditional probabilities by dividing the probabilities by this sum. You get the approximate figures in the table below.

The conditional expected value for $T$ is about $10.5238577$, slightly higher than Ross Millikan's quick approximation of $\frac{2}{7}\cdot 36\approx 10.2857$.

t   P(S_t=36)   P(S_t=36 | S_i=36 for some i)
6   2.143E-05   7.502E-05
7   3.276E-03   1.147E-02
8   2.184E-02   7.645E-02
9   5.324E-02   1.864E-01
10  7.153E-02   2.504E-01
11  6.331E-02   2.216E-01
12  4.069E-02   1.424E-01
13  2.017E-02   7.061E-02
14  8.033E-03   2.812E-02
15  2.642E-03   9.246E-03
16  7.323E-04   2.563E-03
17  1.737E-04   6.078E-04
18  3.563E-05   1.247E-04
19  6.377E-06   2.232E-05
20  1.001E-06   3.505E-06
21  1.385E-07   4.847E-07
22  1.691E-08   5.918E-08
23  1.824E-09   6.384E-09
24  1.737E-10   6.080E-10
25  1.457E-11   5.100E-11
26  1.073E-12   3.754E-12
27  6.889E-14   2.411E-13
28  3.831E-15   1.341E-14
29  1.825E-16   6.387E-16
30  7.342E-18   2.570E-17
31  2.447E-19   8.566E-19
32  6.579E-21   2.303E-20
33  1.371E-22   4.797E-22
34  2.077E-24   7.269E-24
35  2.036E-26   7.126E-26
36  9.695E-29   3.393E-28


The average roll of a six sided die is $3 \frac 12$, so you would expect to have rolled about $\frac 27\cdot 36 \approx 10$ times to get a sum of $36$