Toss a fair die until the cumulative sum is a perfect square-Expected Value

Suppose we keep tossing a fair dice until we want to stop, at which point the game ends and our score is the cumulative sum, or until the cumulative sum is a perfect square, in which case we lose and end up with a score of $0$.

We can set up a Markov-style recurrence. Define $f(k)$ to be the expected value of the game if the current cumulative sum is $k$. Clearly, $f(k)$ is $0$ if $k$ is a perfect square. In addition, $f(k)=\text{max}\{k,\sum_{i=1}^6 f(k+i)\}$.

How can we solve such a recurrence to find a good estimate/bounds of the expected score ($f(0)$) and the optimal strategy? Can these methods be extended to a game where we lose if the cumulative sum is an even number, or a perfect cube?

Solution 1:

The only time we might consider stopping is when $k$ is nearly a perfect square. Suppose $k \approx n^2$ (more specifically, take $n^2-6\leq k<n^2$).

If we stop, our score is always at least $n^2-6$. If we try to continue past $n^2$, and then stop when we nearly reach $(n+1)^2$, the probability that we actually make it past $n^2$ is at most $\frac{5}{6}$, so the expected score is at best $\frac{5}{6}\left((n+1)^2 - 1\right)=\frac{5}{6}\left(n^2+2n\right)$. So stopping now is better than going through $(n+1)^2$ whenever $n^2-6>\frac{5}{6}(n^2+2n)$, and possibly sooner. This inequality holds whenever $n \geq 13$.

So, if $n$ is at least $13$, stopping is better than going one more round, and going multiple extra rounds isn't ever going to help matters (since the inequality never stops being true, so going one extra round is better than going two extra, which is better than going three extra, and so on). That means we're always better off stopping before we attempt to exceed $13^2=169$; that is, when $k$ is at least $163$.

Since this is finite (and not too large!) it should be straightforward if tedious to figure out the optimal strategy and expected value for all $k<163$.

Some simple Sage code (for exact rational arithmetic) to find the optimal strategy follows:

#!/usr/bin/env sage -python

from sage.all import *

evs_dict = dict([(n, QQ(n)) for n in range(163, 169)])

for n in range(162, -1, -1):
    if sqrt(n) in ZZ and n != 0:
        evs_dict[n] = 0
    else:
        evs_dict[n] = max(QQ('1/6') * sum(evs_dict[n+k] for k in range(1, 7)), n)

for n in range(0, 169):
    ev = evs_dict[n]
    print n, ev if ev in ZZ else ev.n()

It seems that it is optimal to stop when $k \geq 75$ and near a perfect square, or when $k \in \{30, 31, 43, 44, 45, 58, 59, 60, 61, 62 \}$. Also, $f(0) \approx 7.17549931276711$.

The "perfect cube" version of this problem should work similarly.

The version where you lose if you hit a power of $2$ is more interesting. You can check that even in the worst case — where you land on $2^n-6$ — the chance of successfully getting past $2^n$ is larger than $\frac{1}{2}$, and going up to $2^{n+1}$ will roughly double your score if successful. So the expected value of continuing one more round actually exceeds the expected value of stopping — and yet, the expected value of continuing forever is clearly zero! That is, there is no optimal strategy, just a succession of better and better strategies.

Infinite games are weird sometimes...