# A dice probability 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.)

• It might be better to write $f(n,t)$. For given $t>0$ you will have $\lim\limits_{n \to \infty} f(n,t)=0$ and for given $n>0$ you will have $\lim\limits_{t \to \infty} f(n,t)=\frac{2}{n+1}$ (each roll increases the total, by an expected $\frac{n+1}2$, so about $\frac2{n+1}$ of numbers are hit by the sequence of totals). Commented Nov 3, 2023 at 10:04
• Note that the exact probability depends on the value of both $n$ and $t$, not just $n$. For instance, if $t = 1$ then obviously the probability is $1/n$, and if $t > 1$ the probability is going to be larger than $1/n$. If both $n$ and $t$ go to infinity, the limit of $f(n,t)$ is likely going to be 0 anyway.
– Stef
Commented Nov 3, 2023 at 10:04
• Only the target number will go to infinity. Commented Nov 3, 2023 at 10:11
• @AMathguy so $\frac{2}{n+1}$ as the limit. Commented Nov 3, 2023 at 10:25
• Numberphile has a video on this topic featuring James Munro. Commented Nov 17, 2023 at 19:42

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

• So... For a n sided dice, the space with the most probility is t=n? Commented Nov 4, 2023 at 1:42
• @AMathguy Yes, if you don't allow t=0. I edited the answer to make that clear Commented Nov 4, 2023 at 8:20
• So, can we say that the graph decreases when the next term is 1 more than a muitiple of 6? Commented Nov 14, 2023 at 13:10

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.

• I think you may be mixing up $n$ and $t$ here. According to the question-asker, $n$ is the number of sides of the die and $t$ is the target value. Though I agree the question is confusing because the probability should depend on $t$ (and on the labels of the die, of course). Commented Nov 3, 2023 at 0:33
• For large $n$, the very first roll will exceed $t$ with probability $1-t/n$. So the probability of hitting $t$ is at most $t/n$ (the probability that the very first roll doesn't already blow it), which goes to zero. Commented Nov 3, 2023 at 1:32
• I'm a probability ignoramus, but I wonder if there's a critical threshold phenomenon where the probability of hitting $t=t(n)$ goes to zero if $t$ grows slower than, maybe, linearly; $1$ if it grows faster...? Commented Nov 3, 2023 at 1:36
• @ZachTeitler Actually I think the probability goes to 0 for any $t(n)$. In other words $\max\{$prob hitting $t\mid t\ge 1\}\to 0$ as $n\to\infty$. Commented Nov 3, 2023 at 4:26
• $\frac27$ is hardly a surprise: each roll increases the total, by an expected $\frac{n+1}2$, so about $\frac2{n+1}$ of numbers are hit by the sequence of totals, and the randomness of each roll soon smooths out the starting probability when $t=0$ of $1$ as $t$ increases for given $n$. Commented Nov 3, 2023 at 10:01

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