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?
On
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$.
Ignoring the rounding issue, empirically less than $10^{-17}$,
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}$