A friend of mine posed an interesting question: given a game where you are \(K\) spaces away from a target space on an infinite linear sequence of tiles, what is the optimal choice of \(N\)-sided die to use for movement such that you minimize the average number of turns it takes to get to your goal?

Above is the problem setup. You have an infinite line of spaces ranging from \(-\infty\) to \(\infty\), with the origin as your goal. You start at space \(K\). You may now choose a \(K\)-sided die (or, rather, a number generator that returns an integer \(\in [1,N]\) from a uniform distribution). Every turn you roll your die and move a number of spaces toward the origin equal to what you rolled.

Consider the case \(K = 2\). You are two spaces away from the origin and want to get there in as few turns as possible. Suppose you choose to use a 2-sided die \((N=2)\). On your first turn you can either roll a 1 or a 2. If you roll a 2, you end up at the origin, and arrived there in 1 turn.

If you roll a 1, however, you end up on the 1 space. On your next turn you either roll a 1 and reach the origin or roll a 2 and end up on the -1 space. Above you can see the possible sequence of moves. In the worst possible case you cycle between \(\pm 1\) forever, but odds are eventually you reach the origin.

What are the average number of turns to reach the origin for \(K=2, N=2\)?

Well, since the die is perfect, you get the following:

$$ T(K=2,N=2) = \frac{1}{2}\times 1 + \frac{1}{2}\left(\frac{1}{2}\times2 + \frac{1}{2}\left(\frac{1}{2}\times3 + \ldots\right)\right)$$

$$ = 1\times\frac{1}{2} + 2\times\frac{1}{4} + 3\times\frac{1}{8} + 4\times\frac{1}{16} + \ldots = 0.5 + 0.5 + 0.375 + 0.25 + \ldots$$

$$ = \sum_{i=1}^{\infty} \frac{i}{2^i} = 2$$

So, if you are 2 spaces away and you choose to use a 2-sided die, the average number of turns is 2. Interesting.

Also note that the case \(K = 1, N = 2\) is the same. Here you are 1 space away, and it also takes you on average 2 turns to get to the origin. This is because being at state 2, 1, and -1 are all the same, turn-wise from the origin when wielding a 2-sided die.

Let us take a look at the case \(K = 3, N = 3\).

$$ T(K=3,N=3)=\frac{1}{3}\times 1 +\frac{2}{3}\left(\frac{1}{3}\times2 + \frac{2}{3}\left(\frac{1}{3}\times3 + \ldots\right)\right)$$

$$ = 1\times\frac{1}{3} + 2\times\frac{2}{6} + 3\times\frac{4}{18} + 4\times\frac{8}{42} + \ldots = \sum_{i=1}^{\infty}\frac{i 2^{i-1}}{3^i} = 3$$

And we again notice that the spaces 3,2,1,-1,-2 are all the same when wielding a 3-sided die, so $$T(K=3,N\in\{3,2,1,-1,-2\}) = 3$$.

Is there a pattern here? Yes.

$$T(K,N=K) = \sum_{i=1}^{\infty} \frac{i (K-1)^{(i-1)}}{K^i} = K$$.

And, more interestingly, being within \(K\) spaces with a \(K\)-sided die causes you to be on average \(K\) turns away from your goal.

$$T(K,|N| \leq K, N \neq 0) = K$$

But what if you have a \(K\)-sided die and are further than \(K\) spaces from the origin? What if you have a 2-sided die and are 3 spaces from the origin?

Let’s work it out: $$T(K=3,N=2) = 1 +\frac{1}{2}T(K=2,N=2) + \frac{1}{2}T(K=1,N=2) = 1 + \frac{1}{2}(2) + \frac{1}{2}(2) = 3$$

Similarly: $$T(K=4,N=2) = 1 +\frac{1}{2}T(K=3,N=2) + \frac{1}{2}T(K=2,N=2) = 1 + \frac{1}{2}(3) + \frac{1}{2}(2) = 3.5$$

In fact: $$T(K,2|K>2) = 1 +\frac{1}{2}\sum_{i=1}^{\infty} T(K-i,2)$$.

In the general case, we get:

$$T(K,N|K>N) = 1 +\frac{1}{N}\sum_{i=1}^{\infty} T(K-i,N) = 1 + \text{AVERAGE}\left(T(K-1:K-N,N)\right)$$

Thus, we can easily generate the average number of turns for any pairwise value \((K,N)\). But, we still haven’t answered the question. What is the optimal choice for \(N\)?

To answer this, let us look at the solution for \(K \leq 55\):

We find that the solution is not actually \(N = \sqrt{K}\), though that would have been a good guess. For \(K=16\), the optimal choice is not 4, but 5. Actually, \(K = 15\) has an optimal choice of 5 as well.

So there you have it. We didn’t find a closed-form solution but we can easily compute several candidate cases and find the optimal choice.