Essays/DiceGame

Here's a simple problem that was once given on a maths puzzle site.

Consider a children's game that is played on a board with a hundred fields numbered from 1 to 100. You start with a marker on field 1, and you win when you reach cell 100 or would go past it. You throw with a single standard dice, and if you throw 1 or a composite number, you advance that many squares; if you throw a prime number, you have to go back that many squares. If you'd have to go back before field 1, you land on 1 instead. The question is to calculate the expected number of times you have to cast the dice to win.

There are two ways to solve this task. One is to do a simulation of such games and compute the average. While this might not give a precise answer, even a bad approximation is enough because the choices given in the puzzle were quite far apart. The other is to compute the solution exactly using linear algebra.

Before we do the calculation, let's try to estimate the number in head. You have to advance 99 squares in order to win, and in every turn, you advance (1+4+6-2-3-5)/6 = 1/6 squares. Thus, you'd think you'll need about 99*6 = 594 turns to win. That was, at least, what I was thinking before I did the real calculation, as I was very surprised that the result turned out to be much less than this.

Let's see the exact calculations in J. We can think of the game as a Markov-chain of 99 states (one for each square except for the last one). We will have to calculate the transition matrix P of this Markov-chain. Once we have that, it's easy to find out the expected number of steps. Indeed, let s be the vector of expected number of states to win from each state, then s = 1 + P s (with 1 meaning a vector of all 1-s). This can then easily be solved for s: s = (I - P)^-1^ 1. To understand that equation, let's write it as s,,i,, = 1 + p,,ij,, s,,j,, which is true because from state i, you have to take one step to any state j and then take s,,j,, more steps in average to win, and you have to average these values with weight p,,ij,,.

First, here's a vector of the possible moves:

   ]move =: (]*_1:^1:=#@:q:)"0 >:i.6
1 _2 _3 4 _5 6

Then two numbers we'll need: the number of possible moves, and the number of states:

   ]nst =: <:100
99

(We have to subtract one from the number of squares on the board, because you never actually use the one numbered with 100.)

Now let's see the transition matrix P:

   p =: (+/%#) ([: =/&(i.nst) [:0&>.(i.nst)&+)"0 move

Here, for every possible outcome of the throw, (i.nst)&+ calculates which square we'd arrive from each square, 0&>. makes sure we never go back any further than square 1, =/&(i.nst) gives a vector with 1 on the state where we arrive and 0 on every other square, and (+/%#) averages these vectors over all possible throws, so we get the probability to arrive on each square. To understand what we get, you may want to run this line with nst set to a smaller value.

Now let's calculate the matrix I - P:

   a =: (=i.nst) - p

And the vector of all ones:

   b =: nst$1

And finally we can solve the linear equation:

   ]s =: b %. a

The result for the question is the number of turns to win from the first square:

   ]s0 =: {.s
371.381

As a homework, consider the variant of the game where, when you would have to go back to a square before 1, you do not move the marker (but the throw is still counted). If you would reach or advance past square 100, you still win. The answer you should get is 365.777.

Here's a simulation solution. Compute move as above, then do this:

   (+/%#) {.@:((>:@:{.,1:>.{:+({~?@:#)@:(move"_))^:(100"_>{:)^:_)"1] 10000$,:0 1
368.994

Contributed by B Jonas

---