Would you ever stop rolling the die?

Question

You have a six-sided die. You keep a cumulative total of your dice rolls. (E.g. if you roll a 3, then a 5, then a 2, your cumulative total is 10.) If your cumulative total is ever equal to a perfect square, then you lose, and you go home with nothing. Otherwise, you can choose to go home with a payout of your cumulative total, or to roll the die again.

My question is about the optimal strategy for this game. In particular, this means that I am looking for an answer to this question: if my cumulative total is $n$, do I choose to roll or not to roll in order to maximize my cumulative total? Is there some integer $N$ after which the answer to this question is always to roll?

I think that there is such an integer, and I conjecture that this integer is $4$. My reasoning is that the square numbers become sufficiently sparse for the expected value to always be in increased by rolling the die again.

As an example, suppose your cumulative total is $35$. Rolling a $1$ and hitting 36 means we go home with nothing, so the expected value of rolling once is:

$$E(Roll|35) = \frac 0 6 + \frac {37} 6 + \frac {38} 6 + \frac{39} 6 + \frac {40} {6} + \frac{41}{6} = 32.5$$

i.e.

$$E(Roll|35) = \frac 1 6 \cdot (37 + 38 + 39 + 40 + 41) = 32.5$$

But the next square after $35$ is $49$. So in the event that we don't roll a $36$, we get to keep rolling the die at no risk as long as the cumulative total is less than $42$. For the sake of simplification, let's say that if we roll and don't hit $36$, then we will roll once more. That die-roll has an expected value of $3.5$. This means the expected value of rolling on $35$ is:

$$E(Roll|35) = \frac 1 6 \cdot (40.5 + 41.5 + 42.5 + 43.5 + 44.5) = 35.42$$

And since $35.42 > 35$, the profit-maximizing choice is to roll again. And this strategy can be applied for every total. I don't see when this would cease to be the reasonable move, though I haven't attempted to verify it computationally. I intuitively think about this in terms of diverging sequences.

I recently had this question in a job interview, and thought it was quite interesting. (And counter-intuitive, since this profit-maximizing strategy invariably results in going home with nothing.)

Answer 1

If you keep rolling the die forever, you will hit a perfect square with probability 1. Intuitively, every time you get close to a square (within distance 6), you have a 1/6 chance to hit the square. This happens infinitely many times, and so you're bound to hit a square eventually.

Slightly more formally, suppose that you roll the die infinitely often whatever happens. Your trajectory (sequence of partial sums) has the property that the difference between adjacent points is between $1$ and $6$. In particular, for each number $N$, there will be a point $x$ in the trajectory such that $N-6 \leq x < N$. If $x$ is the first such point, then you have a chance of $1/6$ to hit $N$ as your next point. Furthermore, if $N_2 > N_1+6$, then these events are independent. So your probability of hitting either $N_1$ or $N_2$ at the first shot once "in range" is $1-(5/6)^2$. The same argument works for any finite number of separated points, and given infinitely many points, no matter how distant, we conclude that you hit one of them almost surely.

Answer 2

How to use your observation in general:

Just checking things for $35$ isn't indicative of the general case, which for large values is different. Take your argument and use a general square $n^2$.

Suppose you're at $n^2-1$. You can leave with $n^2-1$, or you can roll. On a roll, you lose everything with probability $\frac{1}{6}$. With probability $\frac{5}{6}$ you'll get at least $(n+1)^2-6 = n^2 + 2n - 5$ by rolling until it isn't safe to any more. So, for a simple lower bound, we want to know if $\frac{5}{6}(n^2 + 2n - 5)$ is greater than $n^2-1$. For large $n$, this is not the case, and we can actually get an upper bound by similar reasoning:

---

An upper bound:

[A tidied up version of the original follows. Keeping the original upper bound would have required a few extra lines of logic, so I've just upped it slightly to keep it brief.]

An upper bound: Suppose we're between $n^2-5$ and $n^2-1$. If we roll, the best things could go for us would be to lose $\frac{1}{6}$ the time, and, when we don't lose, we get in the range $(n+1)^2-6$ to $(n+1)^2-1$ (the highest we could get without taking another risk). Just comparing current valuation, you're trading at least $n^2-5$ for at most $\frac{5}{6}(n^2 + 2n)$ by the time you get to the next decision. The difference is $-\frac{1}{6}n^2 + \frac{5}{3}n + 5$. For $n \geq 13$ this is negative. So if you're at $13^2-k$ for $1 \leq k \leq 6$, don't roll. (Higher $n$ making this difference even more negative gives this conclusion. See next paragraph for details.)

Extra details for the logic giving this upper bound: Let $W_n$ be the current expected winnings of your strategy for the first time you are within $6$ of $n^2$, also including times you busted or stopped on your own at a lower value. The above shows that, if your strategy ever includes rolling when within $6$ of $n^2$ for $n \geq 13$, then $W_{n+1}$ is less than $W_n$. Therefore there's no worry about anything increasing without bound, and you should indeed never go above $168$.

---

An easy lower bound (small numbers):

Low values: For $n = 3$ we have $(5+6+7+8)/6 > 3$ so roll at $n = 3$. Except for the case $n = 3$, if we roll at $n$, we'll certainly get at least $\frac{5}{6}(n+3)$. So if $\frac{5}{6}(n+3) - n > 0$, roll again. This tells us to roll again for $n < 18$ at the least. Since we shouldn't stop if we can't bust, this tells us to roll again for $n \leq 18$.

---

An algorithm and reported results for the general case:

Obtaining a general solution: Start with expected values of $n$ and a decision of "stay" assigned to $n$ for $163 \leq n \leq 168$. Then work backwards to obtain EV and decisions at each smaller $n$. From this, you'll see where to hit/stay and what the set of reachable values with the optimal strategy is.

A quick script I wrote outputs the following: Stay at 30, 31, 43, 44, 45, 58, 59, 60, 61, 62, and 75+. You'll never exceed 80. The overall EV of the game is roughly 7.2. (Standard disclaimer that you should program it yourself and check.)

Answer 3

Let's deal with the trivial straight up: If you are not within 6 of the next square then you will keep rolling.

If you are within 6 of $n^2$ then your decision is to take the money or roll the dice. If you win, then you proceed to the next decision point (which may be immediately if you are still less than $n^2$). The cases where $n\le3$ are special because you can hit 1 of 2 perfect squares with your next roll.

Each roll is a new game with your current winnings as the stake - you do not stand to lose zero as you did with the first roll because now you have something of value.

The following gives the expected value of the next roll for numbers up to 49. For most numbers greater than 9 this is negative.

$$0: 2.67$$ $$1: N/A$$ $$2: 2.5$$ $$3: 0.33$$ $$4: N/A$$ $$5: 1.17$$ $$6: 1$$ $$7: 0.83$$ $$8: 0.67$$ $$9: N/A$$ $$10: -0.83$$ $$11: -1$$ $$12: -1.17$$ $$13: -1.33$$ $$14: -1.5$$ $$15: -1.67$$ $$16: N/A$$ $$17: 3.5$$ $$18: 3.5$$ $$19: -3.83$$ $$20: -4$$ $$21: -4.17$$ $$22: -4.33$$ $$23: -4.5$$ $$24: -4.67$$ $$25: N/A$$ $$26: 3.5$$ $$27: 3.5$$ $$28: 3.5$$ $$29: 3.5$$ $$30: -7.5$$ $$31: -7.67$$ $$32: -7.83$$ $$33: -8$$ $$34: -8.17$$ $$35: -8.33$$ $$36: N/A$$ $$37: 3.5$$ $$38: 3.5$$ $$39: 3.5$$ $$40: 3.5$$ $$41: 3.5$$ $$42: 3.5$$ $$43: -11.83$$ $$44: -12$$ $$45: -12.17$$ $$46: -12.33$$ $$47: -12.5$$ $$48: -12.67$$

Answer 4

If you denote the expected gain of all future throws when you already have cumulated $X$ and throw a $Y$ by $G(X,Y)$, then this is:

• $G(X,Y) = $undefined, if $X$ is a square. (Not relevant, but I just mention it.)
• $G(X,Y) = -X$, if $X$ is not a square but $X+Y$ is a square.
• $G(X,Y) = Y+MAX\left(0,\frac{1}{6}\sum_{i=1}^6 G(X+Y,i)\right)$ otherwise.

The first two are easy to see, in the last one the sum calculates the expected gain of all future throws excluding this throw, and the maximum with 0 is taken because you only continue playing if your expected future gain is positive.

I have made an excel table of this, with $1\le Y \le 6$ and $1\le X \le 188$. I have found that by increasing the upper bound for $X$, the expected values for lower $X$ don't change; with the upper bound of $188$ I trust all values up to $160$ (but I have no proof).

In this table, the expected gain is negative for $X=30, 31, 43, 44, 45, 58, 59, 60, 61, 62, 75, 76, 77, 78, 79, 80, \ldots$. I stop here, because these are six consecutive numbers, and to reach higher numbers you will reach one of them. So, according to my excel-calculations, the optimal strategy is to play until you reach one of the numbers in the list.

---

Update: I had not seen the update to aes' answer yet, but I see now that we independently arrived to the same set of numbers.

Answer 5

I'm not sure about the precise value of the chance to hit a given integer given persistent consecutive dice rolls (I may edit it in for the sake of being exhaustive), but it's certain to converge towards some constant past 9 as the distance between square numbers becomes greater than the range of the die. You can brute force the probabilities below 9, but the EV is always going to be lower so there's not any point in doing so.

This is because this problem is a variant of the St Petersburg paradox (http://en.wikipedia.org/wiki/St._Petersburg_paradox) in which the value of the reward grows without bound at a rate faster than the chance of the reward; you can expect to win infinite money with repeated play. In this case, your chance for hitting any given square number grows slower than the quadratically growth of the reward, meeting the conditions for the paradox.

A number of proposed solutions exist but the problem does occasionally attract new discussion and does not yet have a definitive resolution.

Answer 6

Extending @aes 's solution by simulation, my computations suggest you in fact always stay when within 6 of a perfect square, for a large enough square.

First, let's cast this as a dynamic programming problem:

$V\left(n\right)=\begin{cases} 0 & \hspace{1em}\exists k\in\mathbb{N} s.t. k^{2}=n\\ \max\left\{ n,\frac{1}{6}\sum\limits_{m=1}^{6}V\left(n+m\right)\right\} & \hspace{1em}\nexists k\in\mathbb{N} s.t. k^{2}=n \end{cases}$

That is, your value conditional on having currently the cumulative sum $n$ is given by choosing to stay (taking $n$) or averaging over future values, unless $n$ is a perfect square.

To make this computable, consider a finite version of the problem, where we force $V(n)=n$ for all $n$ past some threshold $N$; call this approximation $\tilde{V}\left(n;N\right)$.

$\tilde{V}\left(n;N\right)=\begin{cases} 0 & \hspace{1em}\exists k\in\mathbb{N} s.t k^{2}=n\\ \max\left\{ n,\frac{1}{6}\sum\limits_{m=1}^{6}\tilde{V}\left(n+m\right)\right\} & \hspace{1em}\nexists k\in\mathbb{N} s.t. k^{2}=n\cap n<N\\ n & \hspace{1em}\nexists k\in\mathbb{N} s.t. k^{2}=n\cap n\geq N \end{cases}$

I approximated this with the following code in R (slow, I know):

value_functions<-c()

NNN<-10000
squares<-cumsum(seq(1,2*ceiling(sqrt(NNN+6))-1,by=2))

for (NN in ceiling(.8*NNN):NNN){
  values<-0:(NNN+6)
  values[squares+1]<-0
  for (nn in (NN-1):0){
    values[nn+1]<-ifelse(nn %in% squares,0,
                         max(nn,sum(values[(nn+2):(nn+7)])/6))
  }
  value_functions<-rbind(value_functions,values[0:NNN])
}

Here's a plot for $N=9990,\ldots,10000$, $n=1,\ldots,200$ (that we can't tell the plots for separate $N$ apart suggests convergence):

It may be hard to see, but basically what's going on is:

1. at a perfect square, value is 0
2. just after, we are secure for some time--and we'll roll for sure. because we know for sure that we'll roll many times, value doesn't increase (that money is guaranteed).
3. at 6 before the next perfect square, or value plummets--now there's a risk of failure if we choose to continue.
4. just prior to this, our value increases--we've eliminated some of the risk of failure by getting, say, 7 less than a square, which guarantees we'll be able to roll again risk-free.

Building on @aes 's finding, here are the counts at which we drop out, according to my simulation:

  [1]   30   31   43   44   45   58   59   60   61   62   75   76   77   78   79   80   94   95   96   97   98   99  115  116  117  118  119  120  138  139  140  141  142  143  163  164  165  166
 [39]  167  168  190  191  192  193  194  195  219  220  221  222  223  224  250  251  252  253  254  255  283  284  285  286  287  288  318  319  320  321  322  323  355  356  357  358  359  360
 [77]  394  395  396  397  398  399  435  436  437  438  439  440  478  479  480  481  482  483  523  524  525  526  527  528  570  571  572  573  574  575  619  620  621  622  623  624  670  671
[115]  672  673  674  675  723  724  725  726  727  728  778  779  780  781  782  783  835  836  837  838  839  840  894  895  896  897  898  899  955  956  957  958  959  960 1018 1019 1020 1021
[153] 1022 1023 1083 1084 1085 1086 1087 1088 1150 1151 1152 1153 1154 1155 1219 1220 1221 1222 1223 1224 1290 1291 1292 1293 1294 1295 1363 1364 1365 1366 1367 1368 1438 1439 1440 1441 1442 1443
[191] 1515 1516 1517 1518 1519 1520 1594 1595 1596 1597 1598 1599 1675 1676 1677 1678 1679 1680 1758 1759 1760 1761 1762 1763 1843 1844 1845 1846 1847 1848 1930 1931 1932 1933 1934 1935 2019 2020
[229] 2021 2022 2023 2024 2110 2111 2112 2113 2114 2115 2203 2204 2205 2206 2207 2208 2298 2299 2300 2301 2302 2303 2395 2396 2397 2398 2399 2400 2494 2495 2496 2497 2498 2499 2595 2596 2597 2598
[267] 2599 2600 2698 2699 2700 2701 2702 2703 2803 2804 2805 2806 2807 2808 2910 2911 2912 2913 2914 2915 3019 3020 3021 3022 3023 3024 3130 3131 3132 3133 3134 3135 3243 3244 3245 3246 3247 3248
[305] 3358 3359 3360 3361 3362 3363 3475 3476 3477 3478 3479 3480 3594 3595 3596 3597 3598 3599 3715 3716 3717 3718 3719 3720 3838 3839 3840 3841 3842 3843 3963 3964 3965 3966 3967 3968 4090 4091
[343] 4092 4093 4094 4095 4219 4220 4221 4222 4223 4224 4350 4351 4352 4353 4354 4355 4483 4484 4485 4486 4487 4488 4618 4619 4620 4621 4622 4623 4755 4756 4757 4758 4759 4760 4894 4895 4896 4897
[381] 4898 4899 5035 5036 5037 5038 5039 5040 5178 5179 5180 5181 5182 5183 5323 5324 5325 5326 5327 5328 5470 5471 5472 5473 5474 5475 5619 5620 5621 5622 5623 5624 5770 5771 5772 5773 5774 5775
[419] 5923 5924 5925 5926 5927 5928 6078 6079 6080 6081 6082 6083 6235 6236 6237 6238 6239 6240 6394 6395 6396 6397 6398 6399 6555 6556 6557 6558 6559 6560 6718 6719 6720 6721 6722 6723 6883 6884
[457] 6885 6886 6887 6888 7050 7051 7052 7053 7054 7055 7219 7220 7221 7222 7223 7224 7390 7391 7392 7393 7394 7395 7563 7564 7565 7566 7567 7568 7738 7739 7740 7741 7742 7743 7915 7916 7917 7918
[495] 7919 7920 8094 8095 8096 8097 8098 8099 8275 8276 8277 8278 8279 8280 8458 8459 8460 8461 8462 8463 8643 8644 8645 8646 8647 8648 8830 8831 8832 8833 8834 8835 9019 9020 9021 9022 9023 9024
[533] 9210 9211 9212 9213 9214 9215 9403 9404 9405 9406 9407 9408 9598 9599 9600 9601 9602 9603 9795 9796 9797 9798 9799 9800 9994 9995 9996 9997 9998 9999

---

I'm still not fully satisfied that we've got a fully rigorous solution yet.

Basically, all that we've done so far ASSUMES a finite solution. My simulations are cruxed on that we can always find a stopping point; same for @aes. His upper bound assumes we're trading off $n^2-1$ for $(n+1)^2-1$, but, in the language of the problem as stated above, we're actually trading $n^2-1$ for $V\left(\left(n+1\right)^2-1\right)$. If this is itself infinite, the whole problem unravels.

That is, I'm still not convinced we've found an upper bound--once we prove an upper bound, the simulations by me, @aes and @Pakk all line up.

Answer 7

The game can be boiled down to the decision near each square. Should one decide to try and overcome the the square, there is (once you passed 9) a fixed chance of success, let's call it $p$ (it can be calculated exactly, but that is not important here).

We first consider the game without the loss, so if we hit the square we just go home keeping the money so far earned.

In that case you of course would never stop rolling. But we can show, that the expected value is nevertheless finite: For everytime we get over a square $n^2$ we secure the difference to the next square $(n+1)^2$ as a payout. This payout amounts to $(n+1)^2-n^2=2n+1$.

Consequently the expected value would be about $\sum_{n=1}^{\infty}(2n+1)p^n$. This a convergent sum. If we want to know the expectation under the condition that we already overcame $m$ squares, it is $W_m=\sum_{n=1}^{\infty}(2(n+m)+1)p^n$, that is what the future is "worth".

If we now switch back to the other game, where continuing is not free, but incurres an ever rising cost (the probability-weighted cost at each square is $C_m=m^2(1-p)$ as $m^2$ is the amount we would have to give up, if we hit the suare $m^2$, and $(1-p)$ is the chance to actually hit it), that is the "cost" we have to pay for the future.

We now just have to compare the "worth of the future" we calculated with the "cost of the future".

The worth of the future $W_m$ increases linearly in $m$ (meaning from decision to decision), while the probability weighted cost to continue the game $C_m$ increases quadratically in $m$ (meaning from decision to decision).

So the answer is: Yes, you would stop rolling the die at some point as the expected cost of staying in the game will overtake the expected gain at some point.

Answer 8

I'm not great with the maths of this so I decided to try to understand it in my own way - using Excel.

I ran a simulation of this 7776 times. Of these, 2649 games died when a 1 or 4 was rolled straight away. I assume these are of no interest to us since we don't get to make a decision to roll again.

Of the remaining 5127, 457 still failed to make it past 4. So around 8% made a mistake by even taking their 2nd roll - but they should still be included in the analysis in my opinion.

Taking the mean of all these 5127 games, we get 32.419 as the max winnings achieved before dying. This so far away from every other answer. I've been trying to see where I might have gone wrong but I can't see any flaws in my reasoning.

Here is a table of the drop-outs up to 144:

There are only 159 games still running after 144. The highest any managed to achieve was 900 - 1 game.

Answer 9

Many people discuss here that "the estimated gain of the game is not guaranteed finite." I will prove this part by a very simple argument.

The probability that a particular number is hit is $1/3.5$. Now this is not i.i.d. for pairs of numbers, but we always get at least $1/6$ for any conditional probability $P(\text{hit $k$}|\text{hit or not hit something given})$.

This means that no matter what is your strategy, you won't gain more than $n^2$ if you gained at least $(n-1)^2$ with probability at least $1/6$. (Either your strategy is to stop, of you lose the game.) Therefore

$$E \leq \frac16\sum n^2(5/6)^n = 330.$$

Needed to say, $330$ is a very optimistic upper bound of course, and anything like this is reachable moreorless only if you know the next number you roll. (Because then you really gain $n^2$ with probability $\sim (5/6)^n$. The true best possible expected gain is much much much lower, as others show.)

Answer 10

Since, as shown above, the player will eventually land on a perfect square with probability one, the strategy here will also depend on the player's utility of wealth function.