[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

Consider an absorbing Markov chain with state

space [math]S[/math]. Let [math]f[/math] be a function defined on [math]S[/math] with the property that

[[math]] f(i) = \sum_{j \in S} p_{ij} f(j)\ , [[/math]]

or in vector form

[[math]] \mat{f} = \mat{Pf}\ . [[/math]]

Then [math]f[/math] is called a harmonic function for [math]\mat{P}[/math]. If you imagine a game in which your fortune is [math]f(i)[/math] when you are in state [math]i[/math], 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.

• Show that for [math]f[/math] harmonic
  [[math]] \mat{f} = \mat{P}^n{\mat{f}} [[/math]]
  for all [math]n[/math].
• Show, using (a), that for [math]f[/math] harmonic
  [[math]] \mat{f} = \mat{P}^\infty \mat{f}\ , [[/math]]
  where
  [[math]] \mat{P}^\infty = \lim_{n \to \infty} \mat{P}^n = \pmatrix{ [[/math]]
  \begin{tabular}{l|r} \mat{0} & \mat{B} \\ \hline \mat{0} & \mat{I} \\ \end{tabular}
  [[math]] \cr}\ . [[/math]]
• Using (b), prove that when you start in a transient state [math]i[/math] your expected final fortune
  [[math]] \sum_k b_{ik} f(k) [[/math]]
  is equal to your starting fortune [math]f(i)[/math]. In other words, a fair game on a finite state space remains fair to the end. (Fair games in general are called martingales. Fair games on infinite state spaces need not remain fair with an unlimited number of plays allowed. For example, consider the game of Heads or Tails (see Example). Let Peter start with 1 penny and play until he has 2. Then Peter will be sure to end up 1 penny ahead.)