Introduction to Probability · Problem 11.2.27

Markov Chains — Grinstead & Snell

Mathematics — Probability · absorbing-markov-chains

Problem

Consider an absorbing Markov chain with state space SS. Let ff be a function defined on SS with the property that f(i)=∑j∈Spijf(j),f(i) = \sum_{j \in S} p_{ij} f(j), or in vector form f=Pf\mathbf{f} = \mathbf{Pf}. Then ff is called a harmonic function for P\mathbf{P}. If you imagine a game in which your fortune is f(i)f(i) when you are in state ii, then the harmonic condition means that the game is fair in the sense that your expected fortune after one step is the same as it was before the step. (a) Show that for ff harmonic, f=Pnf\mathbf{f} = \mathbf{P}^n \mathbf{f} for all nn. (b) Show, using (a), that for ff harmonic f=P∞f\mathbf{f} = \mathbf{P}^\infty \mathbf{f}, where P∞=lim⁡n→∞Pn=(0B0I).\mathbf{P}^\infty = \lim_{n \to \infty} \mathbf{P}^n = \begin{pmatrix} \mathbf{0} & \mathbf{B} \\ \mathbf{0} & \mathbf{I} \end{pmatrix}. (c) Using (b), prove that when you start in a transient state ii your expected final fortune ∑kbikf(k)\sum_k b_{ik} f(k) is equal to your starting fortune f(i)f(i). In other words, a fair game on a finite state space remains fair to the end.

Related theory

Browse the problem library