# Distribution at First Time a Sum Reaches a Threshold

Consider the following problem. Roll a die many times, and stop when the total exceeds $$M$$, for some prescribed threshold $$M$$. Call this time $$\tau$$, and call the running score after $$n$$ rolls $$X_n$$.

What is the distribution of $$X_\tau$$?

Of course $$X_\tau \in [M,M+5]$$. However, I can get little beyond this. Moreover, for small $$M$$ the distribution should be very sensitive, and I doubt have a nice form. However, if I define $$X'_\tau = X_\tau - M$$, then it seems to me that $$X'_\tau$$ should have a limiting distribution at $$M \to \infty$$.

Extra comments. $$\quad$$ Note that there are various related questions here on maths.SE, but these (as far as I have seen) are about determining $$\tau$$, in particular its expectation, $$E(\tau)$$.

Also, one can solve for $$E(\tau)$$ directly. If I write $$k_M$$ for $$E(\tau)$$ with threshold $$M$$, then $$\textstyle k_M = \tfrac16 \sum_{j=1}^6 k_{M-j} + 1,$$ and writing $$\ell_M = k_M - k_{M-1}$$ we get $$\textstyle \ell_M = \tfrac16 \sum_{j=1}^6 \ell_{M-j}.$$ In principle, by trying the solution $$\ell_r = r^\lambda$$ and solving $$6 \lambda^6 - \lambda^5 - \lambda^4 - \lambda^3 - \lambda^2 - \lambda - 1 = 0,$$ (see this WolframAlpha computation), and calculating some initial conditions by hand, then one can find $$k_M = E(\tau)$$. Note that this would involve finding six initial conditions and solving a set of six simultaneous equations. This is only for the $$\ell$$-s; one then needs to convert this into the $$k$$-s. This does not sound like fun to me! =P

By a simple martingale argument---$$(X_n - \tfrac72n)_{n\ge0}$$ is a martingale, and $$\tau$$ is a deterministically bounded stopping time---from this one immediately gets $$E(X_\tau) = \tfrac27 E(\tau)$$ (for any $$M$$).

• Does hitting $M$ exactly count as being done; or do you have to have a sum strictly greater than $M$? – paw88789 Feb 5 '19 at 16:03
• Yes, hitting $M$ counts as being done; this is why $X_\tau$ can be equal to $M$ (and not $M+6$). However, my title says exceeds, so I see where your confusion lies!---changed now :) – Sam T Feb 6 '19 at 9:34

Let $$p^M_i$$ be the probability that $$X_{\tau(M)}=M+i$$ for $$i=0,1,\dots,5$$, and $$p^M$$ denote the column vector of these six values.

You can compute $$p_M$$ from $$p_{M-1}$$ as follows. There are two ways to achieve a final value of $$M+i$$; either the first time that you value at or above $$M-1$$ you reach is $$(M-1)+(i+1)$$, or the first value at or above $$M-1$$ you reach is $$M-1$$, and then from there you jump immediately to $$M+i$$. Therefore, $$p_i^M=\begin{cases}p^{M-1}_{i+1}+\frac16 p^{M-1}_0 & i<5\\\frac16p_0^{M-1} & i=5\end{cases}$$ This can be written as a matrix equation: $$p^M=\begin{bmatrix} \frac16 & 1 & \\ \frac16 &0 & 1 &\\ \frac16 & 0&0 & 1 &\\ \frac16 & 0&0&0& 1 &\\ \frac16 & 0&0&0&0& 1 \\ \frac16 & 0&0 &0&0&0\\ \end{bmatrix}p^{M-1}$$ with zeroes above the super-diagonal. Letting $$A$$ be the above matrix, then this proves $$p^M=A^Mp^0,$$ where $$p^0$$ is a vector whose first entry is $$1$$ and whose other entries are zero.

The limiting distribution $$p$$ will satisfy $$p=Ap$$. This means that $$p_i=p_{i+1}+\frac16p_0$$, so that $$p$$ is an arithmetic progression with difference $$-\frac16p_0$$. A little thought shows that this implies $$p=\left(\frac{6}{21},\frac{5}{21},\frac{4}{21},\frac{3}{21},\frac{2}{21},\frac{1}{21}\right)^T.$$

• Ah, yes, I didn't think of writing $M+i = (M-1) + (i+1)$. (To be honest, I really should have!) It's clear what to do if you hit $M-1$, but if one is at $M-3$, say, it was less clear to me. I now feel kinda stupid not having got that, but it's always easy once you see a solution---doesn't mean it was easy to find the solution! =P – Sam T Feb 6 '19 at 9:42
• Also, while the whole argument was in the second paragraph, thanks for writing out the details of the rest so that I didn't have to go through them myself =P – Sam T Feb 6 '19 at 9:43
• Also, it appears to me that this should be pretty easy to generalise, yes? If one has a "die" that gives output $X$ (discrete), simply replace the column of $\tfrac16$s with the appropriate distribution? One then just solves the related $p = Ap$ with this new column, which again is pretty easy due to the nature of the matrix. Am I missing something? – Sam T Feb 6 '19 at 20:26
• @SamT That's right! The limiting distribution should be the reverse cumulative sums of the pmf of X, renormalized to be a probability distribution. – Mike Earnest Feb 6 '19 at 20:29
• That's a really cool result, actually! :) – Sam T Feb 6 '19 at 21:50

Inspired by the answer from @MikeEarnest, I wonder if the following alternate proof is valid, for the limiting case? This proof has the advantage(?) of less algebra, and hopefully more intuition into why the distribution is 6:5:4:3:2:1.

Imagine you keep rolling forever. A number is reached if it is the sum at some point in time, otherwise it is skipped. Clearly in the limit, all numbers have the same probability $$q$$ of being reached. (This follows from ergodicity, right? In fact, ergodicity would suggest $$q = {1 \over 3.5}$$, but we don't need its exactly value for now.)

Now consider the interval of interest, $$X_\tau \in [M, M+5]$$:

• $$X_\tau = M+5$$ iff $$M-1$$ is reached and the next roll is $$6$$. This happens with probability $$q/6$$.

• $$X_\tau = M+4$$ iff (a) $$M-1$$ is reached and the next roll is $$5$$, or, (b) $$M-2$$ is reached and the next roll is $$6$$. So this happens with probability $$2q/6$$.

• Note that the case of reaching $$M-2$$, then rolling $$1$$ to reach $$M-1$$, then rolling $$5$$ to reach $$M+4$$, is included in (a) but not in (b), so we did not double-count.
• Similarly, $$X_\tau = M+3, M+2, M+1, M$$ with probabilities $$3q/6, 4q/6, 5q/6, 6q/6$$ respectively.

Since these 6 possibilities are exhaustive, we have $$(1+2+3+4+5+6)q/6 = 1 \implies q = {6 \over 21} = {1 \over 3.5}$$ as I originally suspected; in particular, this implies that $$P(X_\tau = M + j) = (6-j)q/6 = (6-j)/21,$$ agreeing with Mike's answer.

• Interesting! I hope you don't mind, but I added one line to your answer; you hadn't explicitly repeated what the distribution was, so I thought that would be helpful. \\ But yes, I'm pretty sure that argument is valid -- it's a bit late (11pm) for me to think about it now, but I'll just check tomorrow that the ergodicity argument is fine – Sam T Feb 9 '19 at 22:07
• @SamT you edit contains a typo :) (which i fixed) but is otherwise good. anyway, this approach assumes the "obvious" fact that in the limit every large number is reached with same prob $q$. Under this assumption the proof is valid (I think), but proving this "obvious" assumption would require bringing in heavier machinery. But hopefully this gives more insight into why the distribution is 6:5:4:3:2:1. – antkam Feb 9 '19 at 22:20
• Yes, it definitely does give insight -- and for a 'roll distribution $R$' (ie more general than just $\text{Uniform}(1,...,6)$), it does generalise (although general distributions could get messy to write out). Definitely a +1! – Sam T Feb 9 '19 at 23:09
• hmm, @SamT interesting observation re: a general roll distribution $R$. E.g. $R=\{1,10,27\}$ would be pretty tedious to write out and the distribution of $X_\tau \in [M, M+26]$ would also be pretty interesting. As long as the possible $R$ values have $gcd = 1$, the "obvious" ergodic assumption should hold. – antkam Feb 9 '19 at 23:23
• Yeah, I think you're right: tedious, but the method would certainly work. And good shout on the $\text{gcd}$! – Sam T Feb 10 '19 at 10:44