Where does the frog end up?
Tonight's idea
A frog lives on two lily pads, A and B. Each minute it hops or stays, with fixed chances. On A it stays with chance \(\tfrac12\) and hops with chance \(\tfrac12\). On B it hops with chance \(\tfrac14\) and stays with chance \(\tfrac34\). This is a model: real frogs are less tidy.
Write its chances of being on A and on B as a list \((a, b)\). A minute later the list is
\[H(a, b) = \left(\tfrac12 a + \tfrac14 b,\ \tfrac12 a + \tfrac34 b\right).\]
\(H\) is a linear operator: \(H(\mathbf u + \mathbf v) = H(\mathbf u) + H(\mathbf v)\) and \(H(c\,\mathbf u) = c\,H(\mathbf u)\). So you may split a list into parts, hop each part, and add. A nonzero list that \(H\) only multiplies by a number is an eigenvector. The number is its eigenvalue.
\(H\left(\tfrac13, \tfrac23\right) = \left(\tfrac13, \tfrac23\right)\): eigenvalue 1. \(H(1, -1) = \left(\tfrac14, -\tfrac14\right)\): eigenvalue \(\tfrac14\).
Every list is a mix of these two. That is why the chances settle, and how fast.
Watch one: the frog starts on A
The start is \((1, 0)\): certainly on A. Split it into the two eigenvectors. Each hop keeps the first part and multiplies the second by \(\tfrac14\), so you can write down the list after \(n\) hops:
\[(1, 0) = \left(\tfrac13, \tfrac23\right) + \tfrac23\,(1, -1) \qquad\longrightarrow\qquad \left(\tfrac13, \tfrac23\right) + \tfrac23\left(\tfrac14\right)^{n}(1, -1).\]
| hops \(n\) | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| chance on A | 1 | 0.5 | 0.375 | 0.34375 | 0.3359375 |
| gap from \(\tfrac13\) | \(\tfrac23\) | \(\tfrac16\) | \(\tfrac1{24}\) | \(\tfrac1{96}\) | \(\tfrac1{384}\) |
Hopping a minute at a time with \(H\) gives the same numbers. The gap is quartered each minute: after 10 hops it is under a millionth. The frog never settles, but its list of chances does, at the steady state of Markov chains and PageRank.
Your turn
- (a) Apply \(H\) to \(\left(\tfrac13, \tfrac23\right)\) and to \((1, -1)\) to check the two facts in the box. (b) Now the frog starts on B, so the list is \((0, 1)\). Find the list after 1, 2 and 3 hops. Each time, work out the chance on A minus \(\tfrac13\). What multiplies this gap at each hop?
- Here is a linear operator that is not a table of chances: \(S(x, y) = (2x + y,\ x + 2y)\). (a) Apply \(S\) to \((1, 1)\) and to \((1, -1)\). What are the eigenvalues? (b) Write \((1, 0)\) as a mix of \((1, 1)\) and \((1, -1)\). (c) Predict the list you get by applying \(S\) to \((1, 0)\) \(n\) times, and check \(n = 3\) by applying \(S\) three times. Does the first entry's share of the total settle?
- A different frog hops from A with chance \(p\) and from B with chance \(q\) (each from 0 to 1, not both 0), so \(H(a, b) = \big((1 - p)a + qb,\ pa + (1 - q)b\big)\). (a) Show that \((q, p)\) is left alone and that \((1, -1)\) has eigenvalue \(1 - p - q\). (b) Scale \((q, p)\) to total 1, and check against tonight's frog. (c) What happens when \(p + q = 1\)? When \(p = q = 1\)?
- Three pads in a row, A, B, C. From A or C the frog stays or hops to B, with chance \(\tfrac12\) each. From B it stays with chance \(\tfrac12\) and hops to A or to C with chance \(\tfrac14\) each. So \(H(a, b, c) = \left(\tfrac12 a + \tfrac14 b,\ \tfrac12 a + \tfrac12 b + \tfrac12 c,\ \tfrac14 b + \tfrac12 c\right)\). (a) Find the list with total 1 that \(H\) leaves alone. (b) Apply \(H\) to \((1, 0, -1)\) and to \((1, -2, 1)\). (c) The frog starts on A. Split \((1, 0, 0)\) into your three lists and find the chances after \(n\) hops, \(n \ge 1\). How many hops until every chance is within 0.001 of settled?
Stretch: why is the eigenvalue 1 always there?
Use question 3's frog, allowing \(p = q = 0\) too. (a) Show that \(H\) keeps the total of any list, even one with negative entries. Why is this so for any number of pads? (b) If \(H(\mathbf v) = \lambda\mathbf v\) with \(\lambda \ne 1\), show that \(\mathbf v\) has total 0. Check the frog eigenvectors on this sheet. (c) By (a), \(H(\mathbf v) - \mathbf v\) has total 0, so it is a multiple of \((1, -1)\). Say \(H(1, 0) - (1, 0) = s\,(1, -1)\) and \(H(0, 1) - (0, 1) = t\,(1, -1)\). Without finding \(s\) and \(t\), build a nonzero list that \(H\) leaves alone.
Answers
- (a) \(H\left(\tfrac13, \tfrac23\right) = \left(\tfrac16 + \tfrac16,\ \tfrac16 + \tfrac12\right) = \left(\tfrac13, \tfrac23\right)\) and \(H(1, -1) = \left(\tfrac12 - \tfrac14,\ \tfrac12 - \tfrac34\right) = \left(\tfrac14, -\tfrac14\right)\). (b) \(\left(\tfrac14, \tfrac34\right)\), \(\left(\tfrac5{16}, \tfrac{11}{16}\right)\), \(\left(\tfrac{21}{64}, \tfrac{43}{64}\right)\), which are \((0.25, 0.75)\), \((0.3125, 0.6875)\), \((0.328125, 0.671875)\). The gaps, starting from the start, are \(-\tfrac13\), \(-\tfrac1{12}\), \(-\tfrac1{48}\), \(-\tfrac1{192}\). Each is \(\tfrac14\) of the one before, because \((0, 1) = \left(\tfrac13, \tfrac23\right) - \tfrac13(1, -1)\).
- (a) \(S(1, 1) = (3, 3)\) and \(S(1, -1) = (1, -1)\), so the eigenvalues are 3 and 1. (b) \((1, 0) = \tfrac12(1, 1) + \tfrac12(1, -1)\). (c) After \(n\) steps, \(\tfrac12 \cdot 3^n(1, 1) + \tfrac12(1, -1) = \left(\tfrac{3^n + 1}{2}, \tfrac{3^n - 1}{2}\right)\). For \(n = 3\) this is \((14, 13)\), and directly \((1, 0) \to (2, 1) \to (5, 4) \to (14, 13)\). The entries grow without limit. The total is \(3^n\), so the first entry's share is \(\tfrac12 + \tfrac1{2 \cdot 3^n}\), which settles at \(\tfrac12\). Here the largest eigenvalue sets the growth and its eigenvector sets the shares.
- (a) \(H(q, p) = \big((1 - p)q + qp,\ pq + (1 - q)p\big) = (q, p)\). \(H(1, -1) = (1 - p - q,\ p - 1 + q) = (1 - p - q)(1, -1)\). (b) \(\left(\tfrac{q}{p + q}, \tfrac{p}{p + q}\right)\), which needs \(p + q \ne 0\). With \(p = \tfrac12\), \(q = \tfrac14\): \(\left(\tfrac13, \tfrac23\right)\) and \(1 - \tfrac12 - \tfrac14 = \tfrac14\). (c) If \(p + q = 1\) the second eigenvalue is 0, so the gap is wiped out in one hop: from either pad the chance of being on A next is \(q\), so one hop forgets the start. If \(p = q = 1\) the eigenvalue is \(-1\). The frog always hops, \(H(a, b) = (b, a)\), and the chances swap for ever. They do not settle unless the start is \(\left(\tfrac12, \tfrac12\right)\). In every other case here \(1 - p - q\) is bigger than \(-1\) and smaller than 1, and the chances settle.
- (a) \(a = \tfrac12 a + \tfrac14 b\) gives \(b = 2a\), and \(c = \tfrac14 b + \tfrac12 c\) gives \(b = 2c\). With total 1: \(\left(\tfrac14, \tfrac12, \tfrac14\right)\). (The middle equation then holds too.) (b) \(H(1, 0, -1) = \left(\tfrac12, 0, -\tfrac12\right)\), eigenvalue \(\tfrac12\). \(H(1, -2, 1) = (0, 0, 0)\), eigenvalue 0. (c) \((1, 0, 0) = \left(\tfrac14, \tfrac12, \tfrac14\right) + \tfrac12(1, 0, -1) + \tfrac14(1, -2, 1)\). The last part vanishes at the first hop, so for \(n \ge 1\) the list is \(\left(\tfrac14 + \left(\tfrac12\right)^{n+1},\ \tfrac12,\ \tfrac14 - \left(\tfrac12\right)^{n+1}\right)\). The gap is \(\tfrac1{512} \approx 0.00195\) after 8 hops and \(\tfrac1{1024} \approx 0.00098\) after 9, so 9 hops. Of the other eigenvalues, the one of largest size, here \(\tfrac12\), sets the speed.
Stretch. (a) The new total is \((1 - p)a + qb + pa + (1 - q)b = a + b\). In general, a pad holding an amount \(a\) sends it out in shares that add to 1, so it passes on exactly \(a\), and the total is kept. (b) The total of \(H(\mathbf v)\) equals the total of \(\mathbf v\), and it is also \(\lambda\) times that total. So \((1 - \lambda) \times \text{total} = 0\), and since \(\lambda \ne 1\) the total is 0. Check: \((1, -1)\), \((1, 0, -1)\) and \((1, -2, 1)\) all have total 0, and the frog eigenvectors with a nonzero total all had eigenvalue 1. (c) Take \(\mathbf v = (t, -s)\), which is \(t\,(1, 0) - s\,(0, 1)\). By linearity its change is \(t\,s\,(1, -1) - s\,t\,(1, -1) = (0, 0)\), so \(H\) leaves it alone. It is nonzero unless \(s = t = 0\), and then \(H\) leaves \((1, 0)\) alone. Here \(s = -p\) and \(t = q\), so \(\mathbf v = (q, p)\) again. A similar squeeze works for any number of pads, using more linear algebra. It takes further work to show that the list left alone can be chosen with no negative entries, so that it scales to a true list of chances. Question 3(c) shows that even this does not make the chances settle.