15.6 Practice Problems
Problem 15.6.1. Find the stationary distribution of the two-state chain with \(p_{12} = a\), \(p_{21} = b\), and the mean time between visits to state \(1\).
Show solution
Solution. \(\pi _1a = \pi _2b\) and \(\pi _1 + \pi _2 = 1\), so \(\pi = \bigl (\frac b{a + b}, \frac a{a + b}\bigr )\). The mean return time to state \(1\) is \(1/\pi _1 = (a + b)/b\).
Problem 15.6.2. In Example 15.1.1, brand \(B\) can raise its loyalty from \(0.7\) to \(0.8\) by a campaign, taking the extra \(0.1\) from customers who would have switched to \(A\). Find the new long-run share of \(B\).
Show solution
Solution. The \(B\) row becomes \((0.1, 0.8, 0.1)\). Solving \(\pi = \pi P\) with the other rows unchanged: \(\pi _A = 0.8\pi _A + 0.1\pi _B + 0.1\pi _C\), \(\pi _C = 0.1\pi _A + 0.1\pi _B + 0.6\pi _C\), \(\sum \pi = 1\). From the second, \(0.4\pi _C = 0.1(\pi _A + \pi _B) = 0.1(1 - \pi _C)\), so \(\pi _C = 0.2\); then the first gives \(0.2\pi _A = 0.1\pi _B + 0.02\) with \(\pi _A + \pi _B = 0.8\), so \(\pi _A = 0.333\), \(\pi _B = 0.467\). \(B\)’s share rises from \(0.35\) to \(0.47\).
Problem 15.6.3. A gambler with Rs. 1 bets Rs. 1 at a time, winning with probability \(0.4\), and stops at Rs. 0 or Rs. 3. Find the probability of reaching Rs. 3 and the expected number of bets, by the fundamental matrix.
Show solution
Solution. Transient states \(1, 2\): \(Q = \begin {pmatrix} 0 & 0.4 \\ 0.6 & 0 \end {pmatrix}\), \(R\) (to \(0\), to \(3\)) \(= \begin {pmatrix} 0.6 & 0 \\ 0 & 0.4 \end {pmatrix}\). \(I - Q\) has determinant \(1 - 0.24 = 0.76\), so \(N = \frac 1{0.76}\begin {pmatrix} 1 & 0.4 \\ 0.6 & 1 \end {pmatrix}\). From state \(1\): \(P(\text {reach } 3) = (NR)_{12} = \frac {0.4 \times 0.4}{0.76} = 0.211\), and the expected number of bets is \((1 + 0.4)/0.76 = 1.84\).
Problem 15.6.4. In Example 15.3.2, verify the rule of Proposition 15.3.1 by computing \(m_5\), \(m_6\) and \(A(4)\), \(A(5)\).
Show solution
Solution. \(m_5 = r_5 + S_4 - S_5 = 2300 + 375 - 200 = 2475\) and \(m_6 = 2800 + 200 - 200 = 2800\). \(A(4) = 2756.25 > m_5\), so keeping the machine a fifth year lowers the average, to \(A(5) = 2700\); \(m_6 = 2800 > 2700\), so a sixth year raises it. Replace after \(5\) years.
Problem 15.6.5. Show that in Example 15.4.2 replacing in condition \(1\) as well would be worse, using the optimal costs.
Show solution
Solution. In condition \(1\), keeping costs \[ 1000 + 0.9(0.6 \times 12\,700 + 0.3 \times 13\,450 + 0.1 \times 13\,450) = 1000 + 0.9 \times 13\,000 = 12\,700 , \] while replacing costs \[ 4000 + 0.9(0.7 \times 9450 + 0.2 \times 12\,700 + 0.1 \times 13\,450) = 4000 + 0.9 \times 10\,500 = 13\,450 . \] Keeping is cheaper by \(750\), so the policy is right not to replace in condition \(1\).
Problem 15.6.6. Why is value iteration slow when \(\beta \) is close to \(1\), and how many iterations are needed to reduce the error by a factor \(10^{-6}\) when \(\beta = 0.99\)?
Show solution
Solution. The error shrinks by the factor \(\beta \) per iteration, so \(k\) iterations give \(\beta ^k\). For \(\beta ^k = 10^{-6}\), \(k = 6\ln 10/(-\ln \beta ) = 13.8/0.01005 = 1375\) iterations at \(\beta = 0.99\), against \(131\) at \(\beta = 0.9\). Policy iteration, whose number of steps hardly depends on \(\beta \), is then preferable.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.