2 General Markov Chains (September 10, 1999)

2.10 Move to other chapters

2.10.1 Attaining distributions at stopping times

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 TT such that

Pσ(XT)=μ().P_{\sigma}(X_{T}\in\cdot)=\mu(\cdot). (2.29)

Clearly, for any state jj we have EσTjEσT+EμTjE_{\sigma}T_{j}\leq E_{\sigma}T+E_{\mu}T_{j}, which rearranges to EσTEσTj-EμTjE_{\sigma}T\geq E_{\sigma}T_{j}-E_{\mu}T_{j}. So if we define

t¯(σ,μ)=inf{EσT:TT a stopping time satisfying (2.29)}\bar{t}(\sigma,\mu)=\inf\{E_{\sigma}T:\mbox{ $T$ a stopping time satisfying }(% \ref{sigmu})\}

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

Theorem 2.36

t¯(σ,μ)=maxj(EσTj-EμTj)\bar{t}(\sigma,\mu)=\max_{j}(E_{\sigma}T_{j}-E_{\mu}T_{j}).

2.10.2 Differentiating stationary distributions

From the definition (2.6) of the fundamental matrix ZZ 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)(i,j)-entry πj\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.

Lemma 2.37

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

ddαπ=π𝐑𝐙.\frac{d}{d\alpha}\pi=\pi{\bf R}{\bf Z}.

Proof. Write η=ddαπ\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 ηΠ=0\eta\Pi=0 because iηi=ddα(iπi)=0\sum_{i}\eta_{i}={\textstyle\frac{d}{d\alpha}}(\sum_{i}\pi_{i})=0.