Wikipedia:Reference desk/Archives/Mathematics/2020 August 19

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 19

Cumulative die score

Stimulated by a question on another forum about the probability of successive throws of a fair die giving a particular cumulative score, I've set this up as a 6th-order recurrence relation and calculated probabilities for increasing target value. As the target gets beyond 15 or so, it's apparent that the probability is converging on the fraction 2/7. Is there an obvious way of deriving this directly? → 2A00:23C6:AA08:E500:15C1:50D:E204:FC78 (talk) 11:11, 19 August 2020 (UTC)

• My interpretation of the question is that for a fixed target value, we throw a die until the cumulative result either reaches the target (success) or exceeds it (failure), and we ask the probability of success.

Consider a sequence $(u_{n})$ describing the process, i.e. $u_{0}=0,u_{n+1}=u_{n}+{\text{(result from one die roll)}}$. Define $P(n)$ the probability that over a large number of such walks the number $n$ is reached, with $P(0)=1,P(n<0)=0$. Consider a sequence reaching $n>0$: the probability of this happening is the sum of probabilities of the disjoint events (previous number was $n-d$ and we rolled a $d$) for $d\in D=\{1,2,...F\}$ ($F=6$ for a 6-face die). It follows that $P(n)={\frac {1}{F}}\sum _{d=1}^{F}P(n-d)$ (for a fair die).

The question is then whether $P(n)$ converges and if so to what. I think there is some mathematical theorem that guarantees that such a "rolling average" sequence converges, but I cannot find it right now.

We can pull the heavy guns from Constant-recursive sequence#Characterization in terms of exponential polynomials: the characteristic polynomial is $t^{d}-\sum _{k=1}^{d}{\frac {t^{d-k}}{d}}=(t-1)\sum _{k=1}^{d}{\frac {k}{d}}t^{k-1}$. 1 is a simple root of that polynomial. Proving that the other (complex) roots have moduli strictly below 1 is left as an exercise to the reader (that's a fancy way of saying I am pretty sure that is true but could not prove it). As a consequence, the sequence converges (see formula in link, root powers disappear in the high-n limit) but it does not tell us to what. Tigraan^{Click here to contact me} 12:31, 19 August 2020 (UTC)

That's pretty much what I got but you posted before I did. A simpler recursion would be P(n)=1-5P(n-1)/6-4P(n-2)/6-3P(n-3)/6-2P(n-4)/6-P(n-5)/6. If you assume there is a limit P then you can find P as the solution to P=1-5P/6-4P/6-3P/6-2P/6-P/6. In fact for an n-sided die the limit will be 2/(n+1) assuming the limit exists. Showing the limit exists is actually the tricky part. In this case you have to prove that all the roots of x⁵+2x⁵+3x³+4x²+5x+6 have modulus >1 (putting x=1/t). Wolfram Alpha can do the work of computing and plotting the roots if you want to check. It might even be true that the limit exists for n-sided die for any n, but the locations of the roots of nth degree polynomial can be unpredictable for large n, so I'm not sure. Maybe there's a way to prove the recursion is some kind of contraction mapping, which might then be used to show that the sequence converges. --RDBury (talk) 12:38, 19 August 2020 (UTC)

Your simpler recursion is interesting. It lacks the "averaging" property of mine and allows to compute the limit (assuming it exists). How did you get to it?

I could prove that $\lim _{n\rightarrow \infty }P(n+1)-P(n)\rightarrow 0$ but it does not follow that $P(n)$ converges. (Sketch: define $\delta _{n}=max_{k,l\in D}\|P(n+k)-P(n+l)\|$, it is a sequence of non-negative numbers, an easy recursion shows that it is non-increasing, hence it converges; one verifies easily enough that it cannot converge to a value different from 0.) Tigraan^{Click here to contact me} 14:54, 19 August 2020 (UTC)

...aaand immediately after posting I see the obvious: controlling the bounds, we can see that ${\frac {\delta _{n+F}}{\delta _{n}}}\leq {\frac {F-1}{F}}<1$. Hence the series sum of $\sum \delta _{n}$ converges (ratio test), and it dominates $\sum P(n+1)-P(n)$, which must therefore converge too. Tigraan^{Click here to contact me} 15:01, 19 August 2020 (UTC)

I didn't realize the two recursive formulas were that different; my fault because I just assumed they would be trivially equivalent without checking. My reasoning is to enumerate all the ways the sequence can land on the next number after n. You can get to n and then roll anything, probability P(n), or you an get to n-1 and roll something greater than 1, probability 5/6 P(n-1), or you an get to n-2 and roll something greater than 1, probability 4/6 P(n-1), etc. The sum must be 1 since the sequence must eventually get past n, so 1 = p(n)+5/6 P(n-1)+ ... 1/6 P(n-5). On the convergence issue, it amounts to proving that the critical points of (x^F-1)/(x-1) are inside the unit circle. Since the zeros of (x^F-1)/(x-1) are known to be on the unit circle, the result follows from the Gauss–Lucas theorem. --RDBury (talk) 20:27, 19 August 2020 (UTC)

PS. The advantage to your argument on convergence is that it applies to unfair die as well. You only need that the probability of each roll is greater than 0. If the die was so unfairly weighted that it was impossible to roll and odd number then the P(n) would not converge. In general it appears that. given some condition which prevents degenerate cases like this, the probabilities will converge to 1/(the expected value of the roll). There still seems to be some question about what this condition is though. For example consider the following variation: with probability 1/3 each you get either a 6-piece, 9-piece, or 20-piece serving of chicken nuggets, and this process is repeated indefinitely. What is the probability that you will have a total of n chicken nuggets at some point. Intuitively, following Deacon Vorbis' argument below, this probability will converge to 3/293/35, but I think proving this will be a bit more difficult than it was for the original version. --RDBury (talk) 21:32, 19 August 2020 (UTC)

PPS. It appears that for unfair die, the relevant theorem for complex polynomials is the Eneström-Kakeya theorem. (Seems like we should have an article on that but apparently not.) There may be an independent proof of the theorem somewhere in this thread. --RDBury (talk) 21:59, 19 August 2020 (UTC)

PPPS See [1] for a statement an proof of the theorem. (It's called Kakeya's Lemma there.) --RDBury (talk) 22:38, 19 August 2020 (UTC)

• For an intuitive, non-rigorous explanation for all of the above, note that the average value of a roll (for an n-sided die) is (n + 1)/2, i.e., the average distance between any two numbers obtained in the sequence of cumulative sums. Thus, under the reasonable notion that in the long run, all numbers are equally likely to be obtained, the probability that any specific value is obtained is just the reciprocal of that (or 2/7 for a 6-sided die). –Deacon Vorbis (carbon • videos) 15:06, 19 August 2020 (UTC)