The random walker's chances
Tonight's idea
A walker stands on a path of squares numbered 0 to 4. It flips a fair coin and steps one square left or right, again and again. Squares 0 and 4 are exits: the walk stops there. At 4 the walker wins. At 0 it loses.
Let \(p_k\) be the chance of winning from square \(k\). Then \(p_0 = 0\) and \(p_4 = 1\). From square 2, half of all walks step to 1 first and half to 3, so \(p_2 = \tfrac12 p_1 + \tfrac12 p_3\).
If every neighbour is equally likely to be the next step, the chance of winning from a square is the average of its neighbours' chances. Exits are fixed: 1 at a winning exit, 0 at a losing one.
The rule works on any network of squares. A square with three neighbours averages three chances. Numbers that sit at the average of their neighbours are called harmonic.
Two facts we use without proof, true for every network on this sheet: the walk is certain to stop, and only one set of numbers fits the averaging rule.
Watch one: squares 0 to 4
Write the rule at each square that is not an exit. \(p_1 = \tfrac12(0 + p_2)\), \(p_2 = \tfrac12(p_1 + p_3)\) and \(p_3 = \tfrac12(p_2 + 1)\).
Solve. Put the first and third into the second: \(p_2 = \tfrac12\left(\tfrac12 p_2 + \tfrac12 p_2 + \tfrac12\right) = \tfrac12 p_2 + \tfrac14\), so \(p_2 = \tfrac12\). Then \(p_1 = \tfrac14\) and \(p_3 = \tfrac34\).
A shortcut for paths. "\(p_k\) is the average of \(p_{k-1}\) and \(p_{k+1}\)" says the chances go up in equal steps. Four equal steps climb from 0 to 1, so each step is \(\tfrac14\). The shortcut is only for squares in a row. On other networks, write the equations.
Your turn
- A path has squares 0 to 6. The walker flips a fair coin for each step, loses at 0 and wins at 6. (a) Find the chance of winning from each of the squares 1 to 5. (b) Check the averaging rule at square 2. (c) On a path 0 to 100, with exits at 0 and 100, what is the chance of winning from square 1?
- In the house, the walker steps along a line to a neighbouring square, each neighbour equally likely. (The floor joins two exits, so it is never walked.) Let \(a\), \(b\), \(r\) be the chances of winning from A, B, R. (a) Write the three averaging equations. (b) Solve them. Hint: add the equations for \(a\) and \(b\).
- On the grid, the walker steps one cell up, down, left or right, each with chance \(\tfrac14\). A step off the grid ends the walk: the walker has left through that side. (From K, up leaves through the top side and left through the left side.) It wins if it leaves through the top side. (a) Find the chance of winning from M without equations. (b) From T and S the chances of winning are \(t = \tfrac{59}{112}\) and \(s = \tfrac{3}{16}\). Use the averaging rule at K to find \(k\). (c) From K, what is the chance of leaving through the bottom side?
- At the junction, every step goes to a neighbour, all equally likely. Let \(j\) be the chance of winning from J. (a) Use the path shortcut to write the chances at P and Q in terms of \(j\), then the averaging rule at J to find \(j\). (b) Replace Q and its exit by a dead end D, whose only neighbour is J. Find the new \(j\).
Stretch: chances and temperatures
A simple model of heat: exits are held at fixed temperatures, and once things settle every other square is at the average of its neighbours. (a) In the house, hold the losing exit at 0 and the winning exit at 1. What are the settled temperatures at A, B and R, and why? (b) Now hold the losing exit at 20 degrees and the winning exit at 100. Find the three temperatures and check the averaging rule.
Answers
- (a) Six equal steps climb from 0 to 1, so the chance from square \(k\) is \(\tfrac{k}{6}\): \(\tfrac16, \tfrac13, \tfrac12, \tfrac23, \tfrac56\). (b) The neighbours of square 2 have chances \(\tfrac16\) and \(\tfrac12\). Their average is \(\tfrac12\left(\tfrac16 + \tfrac36\right) = \tfrac26 = \tfrac13\), the chance at square 2. (c) One hundred equal steps, so \(\tfrac{1}{100}\). Starting next to the losing exit, the walker wins only one time in a hundred on average.
- (a) \(a = \tfrac13(0 + b + r)\), \(b = \tfrac13(1 + a + r)\), \(r = \tfrac12(a + b)\). (b) Adding the first two gives \(3(a + b) = 1 + (a + b) + 2r\). The third says \(2r = a + b\), so \(3(a+b) = 1 + 2(a+b)\) and \(a + b = 1\). Then \(r = \tfrac12\). Now \(3a = b + r = (1 - a) + \tfrac12\), so \(4a = \tfrac32\) and \(a = \tfrac38\), \(b = \tfrac58\). The roof is equally far from both exits, so \(r = \tfrac12\) is no surprise.
- (a) \(\tfrac14\). The walk is certain to leave, and a quarter turn of the grid about M moves each side to the next and keeps the rules the same. So the four sides are equally likely from M, and their chances add to 1. (b) From K, up wins (1), left leaves through the wrong side (0), right goes to T and down goes to S. So \(k = \tfrac14\left(1 + 0 + \tfrac{59}{112} + \tfrac{21}{112}\right) = \tfrac14 \cdot \tfrac{192}{112} = \tfrac37\). (c) \(\tfrac{1}{14}\). Flip the grid over the diagonal through K: top and left swap, so the chance of leaving through the left side is also \(\tfrac37\). Bottom and right swap too, so they share what remains: \(1 - \tfrac67 = \tfrac17\), and half of that is \(\tfrac{1}{14}\).
- (a) P is halfway along a path from J to the winning exit, so its chance is \(\tfrac12(j + 1)\). Q is halfway from J to a losing exit, so its chance is \(\tfrac12 j\). At J: \(j = \tfrac13\left(0 + \tfrac12(j+1) + \tfrac12 j\right)\), so \(3j = j + \tfrac12\) and \(j = \tfrac14\). (P is \(\tfrac58\) and Q is \(\tfrac18\).) (b) D has one neighbour, so its chance is the average of one number: \(d = j\). At J: \(j = \tfrac13\left(0 + \tfrac12(j + 1) + j\right)\), so \(6j = 3j + 1\) and \(j = \tfrac13\). A dead end only wastes time. The answer is the same as if J had just two neighbours, the losing exit and P.
Stretch. (a) \(\tfrac38\), \(\tfrac58\) and \(\tfrac12\). The temperatures obey the same equations as the chances in question 2, with the same fixed values at the exits, and only one set of numbers fits. (b) Try temperature \(= 20 + 80 \times\) chance. It gives 20 and 100 at the exits, and A \(= 50\), B \(= 70\), R \(= 60\). Check: A is \(\tfrac13(20 + 70 + 60) = 50\), B is \(\tfrac13(100 + 50 + 60) = 70\), R is \(\tfrac12(50 + 70) = 60\). It works because multiplying every number by 80 and adding 20 does the same to every average. So a random walk can answer a heat question, and a heat question can answer a random walk.