find the value of n that maximizes the expected distance travelled in two moves in "luck of the dice 2"

59 Views Asked by At

The game "Luck of the Dice" is described at the end of page 1 and the beginning of page 2 of this problem set. This question uses a slightly modified version of the game, called "Luck of the Dice 2", with the only change being that rule 2 is replaced with the following rule:

(2*) On each of his turns, player i rolls his die and moves his piece to the right by the number of squares that he rolled, say x. If his move ends on a square marked with an arrow, he moves his piece x squares forward. If that move ends on an arrow, he moves another x squares, repeating until his piece comes to rest on a square without an arrow.

Assume exactly one board square, say square number n, is marked with an arrow.

Question: Find, with proof for all $1\leq s_1\leq 15$, all choices of n that maximize the expected distance in squares the first player will travel in his first 2 turns.

To clarify, if the first player reaches the end in the first or second move, he is considered to have travelled a distance of $13$. That may complicate things slightly, but it'll make the expected value calculations more accurate.

For $s_1 = 1,$ the answer is either $n=1$ or $n=2$. For $s_1=2$ or $3$, we can just compute the expected value directly from the definition for all $n$ reasonably small (the maximum distance one can travel for $s_1 = 2$ is $6$ if there's an arrow on square 2 and $9$ if $s_1 = 3$ and there's an arrow on square 3). There's most likely a more efficient way.

I'm not sure if we can induct on $s_1$ somehow. If $s_1 \ge 12$, then as $s_1$ increases, the probability of the first player reaching square $12$ on his first move clearly increases.

For $s_1 = 4$, I think the answer to the original problem is still 4, but I can't seem to prove it in an efficient way. One can literally just use brute force to compute the expected values for $n=1,2,\cdots, 8$ (we only need to do it up to $n=8$ because for larger n, adding the arrow will result in the same expected value as if there was no arrow at all). For instance, I get expected values of $89/16,95/16,102/16$ for $n=2,3,4$.