A dice probability question

Question

Suppose you have a die with $n$ sides labeled $1,2,\ldots,n$. Each turn, you roll the die and add the number you get to the running total (which starts at $0$). You do this for an infinite number of turns. For some positive integer $t$, consider the probability that the total is $t$ in one of the turns.

Call the resulting probability $f(n,t)$. What is $f(n,t)$ as $t$ approaches infinity?

Also,can we modify the formula that it gives the probility of throw $k$ at once using the formula $f(n,t,k)$? (In the last question,we say k is one.)

(I don't know if it will work but I tried it,and I modified it that you can say is using a number of turns which that number is divisible by k.I hope it helps.)

Answer 1

There is a simple recursion formula to calculate $f(n,t)$: $$ f(n,t) = \begin{cases} 0 & \text{if $t<0$} \\[1ex] 1 & \text{if $t=0$} \\[1ex] \frac{1}{n} & \text{if $t=1$} \\[1ex] \frac{n+1}{n}f(n,t-1)-\frac{1}{n}f(n,t-1-n)) & \text{if $t>1$} \end{cases} $$

Proof: Obvious for the cases up to $t=1$. For $t>1$ consider that $f(n,t)$ is the sum of the probabilities of all paths to $t$ (a path to $t$ being a sequence of integers that sum up to $t$).

All paths to $t$ can be constructed from a path to $t-1$ by exactly one of the following

(1) prepending a $1$ (all paths to $t-1$ can be used)

(2) increasing the first number (only paths not starting with $n$ can be used)

The probability of a path of type (1) is $\frac{1}{n}$ of the probability of the original path, so the probabilities of the paths of type (1) sum up to $\frac{1}{n}f(n,t-1)$.

The probability of a path of type (2) equals the probability of the original path. So the probability of paths of type (2) equals $f(n,t-1)$ minus the sum of the probabilities of paths to $t-1$ that start with $n$. The latter sum equals $\frac{1}{n}f(n,t-(n+1))$ (first roll $n$ and then take a path to $t-1-n$) $\square$

It is interesting to look at the first 30 values of $f(6,t)$. First we see a steep increase due to the increasing possibilities. Then at $t=7$ a sudden drop, because we lose the possibility to roll it in one turn. Then it evens out very quickly. We see a small bump at about $t=13$ as an echo to the first drop.

An alternative recursion formula is

$$ f(n,t) = \begin{cases} 0 & \text{if $t<0$} \\[1ex] 1 & \text{if $t=0$} \\[1ex] \frac{1}{n}\sum_{i=1}^n{f(n,t-i)} & \text{if $t>0$} \end{cases} $$

So starting from $t=1$ each value is the average of the preceeding $n$ values. This can be shown in a similar manner, considering each possibility for the first roll separately.

From this, it is easy to see that the values increase from $t=1$ to $t=n$ and after that never reach the maximum value at $t=n$ again.

Regarding the moving window of the average, it can be seen that the range of fluctuations between the values is dampened by at least a factor $n$ after each $n$ values. Thus the sequence converges. The probability to hit some high $t$ must be close to the average density of the paths, which is reciprocal to the average dice value. Thus the limit of $f(n,t)$ must be $2/(n+1)$

Answer 2

Interestingly, the probability that $t$ occurs for a standard die $n=6$ as $t\to\infty$ is $\frac27$, with exponential convergence towards that value.

This is a standard generating function problem. The probabilities for one throw are the coefficients of $a(x)=\frac16(x+x^2+x^3+x^4+x^5+x^6)$, so the probabilities for infinitely many throws are the coefficients of $A(x)=1/(1-a(x))$. Now we can write $$ A(x) = \frac{2}{7(1-x)} + \frac{30+20x+12x^2+6x^3+2x^4}{7(6+5x+4x^2+3x^3+2x^4+x^5)}.$$

The coefficients of the first term are all $\frac27$. The second term has smallest singularity with absolute value greater than 1 (about 1.37) so its coefficients go to 0 exponentially fast.

In the case of a die with labels $1,2,\ldots,n$, the same approach gives a generating function with $$A_n(x) = \frac{2}{(n+1)(1-x)} + \frac{P_n(x)}{Q_n(x)},$$ where $P_n(x)$ and $Q_n(x)$ are polynomials with positive coefficients. The smallest zero of $Q_n(x)$ is outside the unit circle, so the probability that $t$ occurs converges to $\frac{2}{n+1}$ as $t\to\infty$.

As Sam has pointed out, this doesn't immediately answer the question of what happens when $t$ is fixed and $n\to\infty$. In that case the probability goes to 0, which one could guess from the above but probably has an even more elementary proof. I believe that it follows from the Berry-Esseen version of the central limit theorem. I have to run but I'll put this in if nobody else does in the next few hours.

After $N$ tosses, the distribution of totals is approximately normal with mean $N(n+1)/2$ and variance $N(n^2-1)/12$. The distribution is log-concave so a local limit theorem holds; i.e., the point probabilities near the mean also match the normal distribution. That means, after $N$ tosses no total has probability greater than $O(N^{-1/2}n^{-1})$. Moreover a suitable concentration inequality will show that totals outside $[Nn/2-N^{1/2}n^{1+\varepsilon},Nn/2+N^{1/2}n^{1+\varepsilon}]$ have vanishingly small probability, so with high probability there are only a small number of toss numbers that that can hit a given total. This is all hand-wavy but can be made rigorous. The conclusion is that for all $t(n)\ge 1$ the probability of hitting $t(n)$ goes to 0 as $n\to\infty$.

All that being said, I'm sure there is some stock theorem in random walks or Markov chains that gives this result immediately.

Answer 3

Here is a "soft" argument, turning into a proof the idea of Henry in a comment.

Let $X_i$ denote the rolling average after $i$ rolls, and let $\tau_k$ be the first moment it is at least $kn$. Observe that $Y_k=X_{\tau_k}-kn$ is a Markov chain (on the state space $\{0,\dots,n-1\}$) which is irreducible and aperiodic. Therefore, its distribution converges as $k\to \infty$ to its equilibrium distribution, exponentially quickly, independently of the initial state. But if $t=kn+r$ with $1\leq r\leq n$, then the probability in question is $\mathbb{P}_{n-r}(Y_k=0)$ for the chain started at $Y_0=n-r$.

It follows that if $t$ is large, then $f(n,s)$ is approximately the same (with an exponentially small error) for $s=t,t+1,\dots,t+N$. Note that $\frac{1}{N+1}\sum_{s=t}^{t+N}{f(n,s)}=\mathbb{E}Q_{t,t+N}$, where $Q_{t,t+N}$ is the proportion of the points hit in the interval $[t,t+N]$.

On the other hand, by the law of large numbers, $Q_{t,t+N}\approx\frac{2}{n+1}$ with large probability, and hence $\mathbb{E}Q_{t,t+N}\approx \frac{2}{n+1}$. (E.g. the event $Q_{t,t+N}<\frac{2}{n+1}-\epsilon$ means that $(N+1)(\frac{2}{n+1}-\epsilon)-1$ independent rolls summed up to at least $N-6$, which has vanishing probability).

So, choosing first $N$ such that this $\approx$ above is as good as we please, and then $t$ so that each $f(n,s)$ is as close to its limit as we please, we see that the limit is actually $2/(n+1)$.