1
$\begingroup$

A special dice has four sides (1, 2, 3, 4). You roll the dice continuously and sum up the values until the sum is greater than or equal to 100. What is the expected value of the sum?

I am attempting to find an analytical solution to these. I realize it can be done with generating functions but that requires a computer to solve. I am wondering if there is a way to utilize symmetry (as this question involves a 4-sided dice rather than 6-sided) to get a nice solution?

$\endgroup$
  • $\begingroup$ Why would the four values (100, 101, 102, 103) be equally likely? Take a simple case lets say we roll the dice twice, so our sum can be any value from 2 - 8. Clearly, 2 will be less likely than 4 as we can get to 2 by rolling two 1's (1 + 1 = 2) whereas 4 we can get to by rolling 3,1 or 2,2. $\endgroup$ – genescuba Aug 12 at 23:30
  • $\begingroup$ Yeah, I was a bit hasty there. Let me think for a second... $\endgroup$ – lulu Aug 12 at 23:31
  • 1
    $\begingroup$ @lulu : A numerical experiment says not uniform. Possibly because there is only one way to land on 103: land on 99 then roll a 4, and many ways to land on 100. $\endgroup$ – Eric Towers Aug 12 at 23:31
  • $\begingroup$ @EricTowers Yes, I just simulated it and reached the same conclusion. $100$ is far more likely. $\endgroup$ – lulu Aug 12 at 23:32
  • $\begingroup$ But I still believe that the key point is that you are equally likely to land on each of the numbers just below $100$. Thus we see that $p_{100}=4\times p_{103}$ and so on. Since these sum to $1$... $\endgroup$ – lulu Aug 12 at 23:39
2
$\begingroup$

Ignoring the rounding issue, empirically less than $10^{-17}$,

  • the probability of ending on $100$ is $\frac4{10}$
  • the probability of ending on $101$ is $\frac3{10}$
  • the probability of ending on $102$ is $\frac2{10}$
  • the probability of ending on $103$ is $\frac1{10}$

making the expected final value $101$

More generally if with a $d$ sided fair die and you have a target $n\gg d$, the expected stopping value is approximately $n + \sum \limits_{j=0}^{d-1} \frac{2j(d-j)}{d(d+1)} = n + \frac{d-1}{3}$

$\endgroup$
  • $\begingroup$ How did you arrive at those probabilities? $\endgroup$ – genescuba Aug 12 at 23:38
  • 1
    $\begingroup$ @genescuba $100$ could be preceded by $96, 97, 98, 99$; $101$ by $97, 98, 99$; $102$ by $98, 99$; $103$ by $99$. And $1+2+3+4=10$. $\endgroup$ – Henry Aug 12 at 23:41
  • $\begingroup$ Right, but don't we have to consider the probabilities to get to 96, 97, ... giving us a recurrence to solve? $\endgroup$ – genescuba Aug 12 at 23:49
  • $\begingroup$ You need the probabilities of ever hitting $96,97,98,99$ and these are all approximately the same. You do not need to know the value, but it is about $0.4$ here or for a $d$ sided die about $\frac{2}{d+1}$ since the average step is $2.5$ or more generally $\frac{d+1}{2}$ $\endgroup$ – Henry Aug 12 at 23:52
  • 1
    $\begingroup$ How does this address OP's "find an analytical solution"? $\endgroup$ – Eric Towers Aug 13 at 0:25
1
$\begingroup$

Let $p(n)$ the probability of landing on $n$. We have \begin{align*} p(x) &= 0, x \leq 0 \\ p(1) &= 1/4 \\ p(2) &= 1/4 + (1/4) p(1) \\ p(3) &= 1/4 + (1/4) p(1) + (1/4) p(2) \\ p(4) &= 1/4 + (1/4) p(1) + (1/4) p(2) + (1/4) p(3) \text{.} \end{align*} Then for $4 < x \leq 100$, $$ p(x) = (1/4) (p(x-4) + p(x-3) + p(x-2) + p(x-1)) \text{.} $$ And finally, \begin{align*} p(101) &= (1/4)(p(97) + p(98) + p(99)) \\ p(102) &= (1/4)(p(98) + p(99)) \\ p(103) &= (1/4)p(99) \text{.} \end{align*}

If we just grind through this (with a computer, say), we find \begin{align*} p(100) &= \frac{1483 \cdot 433429007217529406760887788822132850019412104490152405847}{4^{100}} \\ p(101) &= \frac{5^2 \cdot 5849 \cdot 374249521 \cdot 13476060839 \cdot 653694064078297082499263551694346971}{4^{100}} \\ p(102) &= \frac{5^3 \cdot 25951 \cdot 792647 \cdot 1496090412665813 \cdot 83546326261154633177972168761717}{4^{100}} \\ p(103) &= \frac{5^4 \cdot 280530121 \cdot 707720114206970708492483 \cdot 1295024776631696849057419}{4^{100}} \end{align*}

You might ask: why did he factor those? To which the answer is: If the analytic expression you are seeking has a product in the numerator, how many factors are there and how complicated must they be? We can see that such an expression cannot have more than three factors, there is a simple behaviour in powers of $5$, and the factors must be relatively complicated.

We can simulate the iterated calculation with matrix multiplication. Starting with the vector $$ \begin{pmatrix} p(1) \\ p(2) \\ p(3) \\ p(4) \end{pmatrix} = \begin{pmatrix} \frac{1}{4} \\ \frac{5}{16} \\ \frac{25}{64} \\ \frac{125}{256} \end{pmatrix} \text{,} $$ we might be fooled into thinking the result is a simple power of $5$ over a power of $4$, but it is not, as we can see from $$ \begin{pmatrix} p(2) \\ p(3) \\ p(4) \\ p(5) \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1/4 & 1/4 & 1/4 & 1/4 \\ \end{pmatrix} \cdot \begin{pmatrix} \frac{5}{16} \\ \frac{25}{64} \\ \frac{125}{256} \\ \frac{369}{1024} \end{pmatrix} \text{.} $$

Let's call that matrix $M$.

If we keep multiplying by $M$, we can produce all the values of $p$ up to $p(100)$, at which point, we should stop and evaluate $p(101)$ through $p(103)$ using the equations above (or by using a different matrix, but figuring out that matrix is about as much work as just using the above equations). Every time we multiply by $M$, we advance by one. With zero applications, the last entry in the vector is $p(4)$. With $96$ applications, the last entry in the resulting vector is $p(100)$. Thus, we want to know a short cut for finding the $96^\text{th}$ power of $M$. One way uses $96 = 3 \cdot 32 = 3 \cdot 2^5$, so we square the matrix five times, then cube the result. This gives \begin{align*} M^2 &= \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1/4 & 1/4 & 1/4 & 1/4 \\ 1/16 & 5/16 & 5/16 & 5/16 \end{pmatrix} \\ &\vdots \\ M^{32} &= \left( \begin{array}{cccc} \frac{28822929547725725}{288230376151711744} & \frac{57645967609791105}{288230376151711744} & \frac{86469319984686289}{288230376151711744} & \frac{115292159009508625}{288230376151711744} \\ \frac{115292159009508625}{1152921504606846976} & \frac{230583877200411525}{1152921504606846976} & \frac{345876029448673045}{1152921504606846976} & \frac{461169438948253781}{1152921504606846976} \\ \frac{461169438948253781}{4611686018427387904} & \frac{922338074986288281}{4611686018427387904} & \frac{1383504947749899881}{4611686018427387904} & \frac{1844673556742945961}{4611686018427387904} \\ \frac{1844673556742945961}{18446744073709551616} & \frac{3689351312535961085}{18446744073709551616} & \frac{5534025856688099085}{18446744073709551616} & \frac{7378693347742545485}{18446744073709551616} \\ \end{array} \right) \\ M^{96} &= \left( \begin{array}{cccc} \frac{9807971461541688681220646970903113588698612048390246045}{98079714615416886934934209737619787751599303819750539264} & \frac{19615942923083377351721844949808533352050942306285379969}{98079714615416886934934209737619787751599303819750539264} & \frac{29423914384625066083201154619301720212372456275919516625}{98079714615416886934934209737619787751599303819750539264} & \frac{39231885846166754818790563197606420598477293189155396625}{98079714615416886934934209737619787751599303819750539264} \\ \frac{39231885846166754818790563197606420598477293189155396625}{392318858461667547739736838950479151006397215279002157056} & \frac{78463771692333509543673151081218874953271741382716380805}{392318858461667547739736838950479151006397215279002157056} & \frac{117695657538500264225677942996840554006681062414296916501}{392318858461667547739736838950479151006397215279002157056} & \frac{156927543384667019151595181674813301447967118292833463125}{392318858461667547739736838950479151006397215279002157056} \\ \frac{156927543384667019151595181674813301447967118292833463125}{1569275433846670190958947355801916604025588861116008628224} & \frac{313855086769334038426757434465238983841876291049455049625}{1569275433846670190958947355801916604025588861116008628224} & \frac{470782630154001057326287785999688801261054083823698986345}{1569275433846670190958947355801916604025588861116008628224} & \frac{627710173538668076054306953662175517474691367950021129129}{1569275433846670190958947355801916604025588861116008628224} \\ \frac{627710173538668076054306953662175517474691367950021129129}{6277101735386680763835789423207666416102355444464034512896} & \frac{1255420347077336152660687680361428723266559841121354981629}{6277101735386680763835789423207666416102355444464034512896} & \frac{1883130520616004229761336691523131452842196532147841327629}{6277101735386680763835789423207666416102355444464034512896} & \frac{2510840694154672305359458097660930722518907703244817074509}{6277101735386680763835789423207666416102355444464034512896} \\ \end{array} \right) \text{.} \end{align*} So we can multiply out $M^{96} \cdot (p(1) \dots p(4))^T$ to get the $p(97) \dots p(100)$ vector, then finish by using the equations above to extract the $p(101) \dots p(103)$ vectors.

(Some readers might imagine we can perhaps save a little effort using an eigensystem decomposition, so that one takes the $96^\text{th}$ power of a diagonal matrix (so one just takes each entry of the matrix to its $96^\text{th}$ power), but this isn't a big win. That diagonal (i.e., the list of eigenvalues of $M$) is $$\mathrm{diag}\left(1,\frac{1}{4} \left(-1+\frac{5^{2/3} \left(1+i \sqrt{3}\right)}{2 \sqrt[3]{3 \left(4 \sqrt{6}-9\right)}}-\frac{\left(1-i \sqrt{3}\right) \sqrt[3]{5 \left(4 \sqrt{6}-9\right)}}{2\ 3^{2/3}}\right),\frac{1}{4} \left(-1+\frac{5^{2/3} \left(1-i \sqrt{3}\right)}{2 \sqrt[3]{3 \left(4 \sqrt{6}-9\right)}}-\frac{\left(1+i \sqrt{3}\right) \sqrt[3]{5 \left(4 \sqrt{6}-9\right)}}{2\ 3^{2/3}}\right),\frac{1}{4} \left(-1-\frac{5^{2/3}}{\sqrt[3]{3 \left(4 \sqrt{6}-9\right)}}+\frac{\sqrt[3]{5 \left(4 \sqrt{6}-9\right)}}{3^{2/3}}\right)\right)$$ and computing powers of these algebraic numbers takes Mathematica vastly longer than the repeated powering of $M$ described above.)

Notice that we have directly written $p(100) \dots p(103)$ as linear combinations of $p(1) \dots p(4)$, which is an analytic expression in terms of the starting probabilities. You could, in fact, pick arbitrary probability for $p(1) \dots p(4)$ and use the above to find the resulting probabilities for arriving at dice sums $\geq 100$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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