The Critical Line – Volume 18

Annie the Actuary loves Australia and exploring the outback. She and three other friends have dedicated their annual leave to the great Australian pilgrimage across the Nullarbor over the New Years period and are loving every minute of it. They are now on the return leg of the journey. Annie sees the following Billboard halfway across, which they didn’t notice on the way across.

Annie and her friends realise that the billboard is in fact a puzzle to keep passengers and drivers minds active – and that when solved it reads ‘Happy new year and welcome to two thousand and eighteen’. Several hundred kilometres go by and Annie and her friends are beginning to feel lethargic – they see another billboard and have a feeling there could be a great reward for them if they can solve it quickly enough!  Can you solve it?

The Critical Line Volume 17 Solution – by Dan Mayoh

Link to original problem is here

The answers (given to 5 decimal places) are as follows:

Probability of terminating at each goal:

Goal 1 (-2,2) = 0.26106

Goal 2 (2,2) = 0.13412

Goal 3 (2,-2) = 0.18648

Goal 4 (-2,-2) = 0.41834

Probability of walk taking more than 20 steps = 0.34995

Expected value of number of steps = 19.71945

Several people sent in correct solutions that provided answers to this level of precision or higher.  These included Stephen Edwards, Min Chen, Andrew Parker, Maiyuran Arumugam and Chris Barry.

 Several other people tackled the problem via simulation which provided observational answers close to these theoretical results, but not accurate to this level of precision.  These include Lawrence Uy, Kevin Song and Mathieu Jones.

The winner of the book voucher is Chris Barry.

How to approach the problem:

Since this random walk can be thought of as a Markov Chain with 25 available states including 4 terminating states, we can solve it analytically by setting up a 25*25 transition matrix.

Here’s one approach (not the best approach) to solving the problem from here using Excel that I suspect many people used.  Call this 25*25 transition matrix “A”.  By raising A to the power n, we can easily read off the probability of being in state j after n steps given we started at state i.  In Excel, which has an MMULT function but not a function for raising a matrix to the nth power, this can easily be done for values of n equal to 2, 4, 8, 16, 32, 64.  E.g. if the original 25*25 transition matrix is given the defined name ‘MatrixA’, then A^2 = MMULT(MatrixA,MatrixA).  If we name that result MatrixA2, then A^4 = MMULT(MatrixA2,MatrixA2).  By continuously squaring the previously calculated matrix we can arrive at A^n for all of the powers of 2.  Once we get to A^256 we have a 100% probability (within 5 decimal places) of being in a terminating state and can read off our answers.  The answer to part 2 (probability of the walk taking more than 20 steps) can be identified once we find A^20, which we can find as =MMULT(MatrixA16,MatrixA4).

However finding the expected value of the number of steps using this approach is more problematic, unless we want to generate A^n for all 256 values of n, which will take a lot of worksheet space and a lot of copying/pasting.  And even then it ignores the small number of cases where the walk takes longer than 256 steps.

Here’s another approach, also using Excel, that allows us to find the answers more easily.  This is essentially the approach Chris Barry used, well done Chris!  The key is to set up our 25*25 transition matrix A so that the 4 terminating states occupy the final 4 rows and final 4 columns of the 25*25 matrix.  We can then split up A into 4 parts, which I will call W, X, Y and Z as shown below.

We can set up this group of 25*25 cells in Excel and give the defined names “W” and “X” to the relevant 21*21 and 21*4 regions.

We now need to calculate two other matrices.  The first we will call “N”, such that N = (I-W)^(-1) where I is the 21*21 Identity Matrix.  In Excel, we can calculate this by selecting a range of 21*21 cells and entering the array formula =MINVERSE(MUNIT(21)-W).  If you are using an older version of Excel that doesn’t have the MUNIT function, you can instead use =MINVERSE(MMULT(W,MINVERSE(W))-W).

The second matrix we need we will call F.  It will be a 21 row * 4 column matrix such that F = N*X.

Now, we can answer the questions.

The probability of ending at each of the 4 goals will be 4 values in the top row of F.

The expected value of the number of steps will be the sum of the top row of N.

And the probability of the walk taking more than 20 steps will be the sum of the top row of W^20.  The first approach provided describes how to use Excel to find W^20.

CPD: Actuaries Institute Members can claim two CPD points for every hour of reading articles on Actuaries Digital.