We quote a result, Theorem 2.36, which may look superficially like the identities in section 2.2.1 but which in fact is deeper, in that it cannot be proved by mere matrix manipulations or by Proposition 2.3. The result goes back to Baxter and Chacon [44] (and is implicit in Rost [301]) in the more general continuous-space setting: a proof tailored to the finite state space case has recently been given by Lovász and Winkler [240].

Given distributions $\sigma,\mu$, consider a stopping time $T$ such that

$P_{\sigma}(X_{T}\in\cdot)=\mu(\cdot).$ | (2.29) |

Clearly, for any state $j$ we have $E_{\sigma}T_{j}\leq E_{\sigma}T+E_{\mu}T_{j}$, which rearranges to $E_{\sigma}T\geq E_{\sigma}T_{j}-E_{\mu}T_{j}$. So if we define

$T$ |

then we have shown that $\bar{t}(\sigma,\mu)\geq\max_{j}(E_{\sigma}T_{j}-E_{\mu}T_{j})$. Surprisingly, this inequality turns out to be an equality.

$\bar{t}(\sigma,\mu)=\max_{j}(E_{\sigma}T_{j}-E_{\mu}T_{j})$.

From the definition (2.6) of the fundamental matrix $Z$ we can write, in matrix notation,

$({\rm{\bf I}}-{\bf P}){\bf Z}={\bf Z}({\rm{\bf I}}-{\bf P})={\rm{\bf I}}-\Pi$ | (2.30) |

where $\Pi$ is the matrix with $(i,j)$-entry $\pi_{j}$. The matrix ${\rm{\bf I}}-{\bf P}$ is not invertible but (2.30) expresses ${\bf Z}$ as a “generalized inverse” of ${\rm{\bf I}}-{\bf P}$, and one can use matrix methods to verify general identities in the spirit of section 2.2.1. See e.g. [186, 215]. Here is a setting where such matrix methods work well.

Suppose ${\bf P}$ (and hence $\pi$ and ${\bf Z}$) depend on a real parameter $\alpha$, and suppose ${\bf R}=\frac{d}{d\alpha}{\bf P}$ exists. Then, at $\alpha$ such that ${\bf P}$ is irreducible,

$\frac{d}{d\alpha}\pi=\pi{\bf R}{\bf Z}.$ |

Proof. Write $\eta=\frac{d}{d\alpha}\pi$. Differentiating the balance equations $\pi=\pi{\bf P}$ gives $\eta=\eta{\bf P}+\pi{\bf R}$, in other words $\eta({\rm{\bf I}}-{\bf P})=\pi{\bf R}$. Right-multiply by ${\bf Z}$ to get

$\pi{\bf R}{\bf Z}=\eta({\rm{\bf I}}-{\bf P}){\bf Z}=\eta({\rm{\bf I}}-\Pi)=% \eta-\eta\Pi.$ |

But $\eta\Pi=0$ because $\sum_{i}\eta_{i}={\textstyle\frac{d}{d\alpha}}(\sum_{i}\pi_{i})=0$.

Generated on Mon Jun 2 14:23:48 2014 by LaTeXML