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.
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$.