9
$\begingroup$

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

$\endgroup$
5
  • 2
    $\begingroup$ 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). $\endgroup$
    – Henry
    Nov 3, 2023 at 10:04
  • $\begingroup$ 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. $\endgroup$
    – Stef
    Nov 3, 2023 at 10:04
  • $\begingroup$ Only the target number will go to infinity. $\endgroup$
    – A Math guy
    Nov 3, 2023 at 10:11
  • $\begingroup$ @AMathguy so $\frac{2}{n+1}$ as the limit. $\endgroup$
    – Henry
    Nov 3, 2023 at 10:25
  • $\begingroup$ Numberphile has a video on this topic featuring James Munro. $\endgroup$ Nov 17, 2023 at 19:42

3 Answers 3

9
$\begingroup$

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.

First 30 values of $f(6,t)

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

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

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.

$\endgroup$
6
  • 3
    $\begingroup$ 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). $\endgroup$ Nov 3, 2023 at 0:33
  • 3
    $\begingroup$ 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. $\endgroup$ Nov 3, 2023 at 1:32
  • 3
    $\begingroup$ 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...? $\endgroup$ Nov 3, 2023 at 1:36
  • 4
    $\begingroup$ @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$. $\endgroup$ Nov 3, 2023 at 4:26
  • 9
    $\begingroup$ $\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$. $\endgroup$
    – Henry
    Nov 3, 2023 at 10:01
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.