Probabilistic proof for derivative of invariant distribution of a Markov chain

Question

Let $P$ be an irreducible Markov matrix, and $\pi$ its stationary distribution. Let $D$ be a perturbation matrix which is zero except for two entries in row $r$: $$D_{rg}=+1 \qquad D_{r\ell}=-1.$$ Let $\widetilde{P}(\delta)=P+\delta D$ and let $\widetilde{\pi}(\delta)$ be its stationary distribution. The matrix $\widetilde{P}(\delta)$ is a perturbed version of $P$ where transitions from $r$ happen a little more to the gaining state $g$ and a little less to the losing state $\ell$.

In [1], Conlisk derived, based on identities in [2], the following remarkable formula for the effect on the stationary probability of the gaining state: $$ \frac{d}{d\delta} \widetilde{\pi}_g(\delta) = \pi_r\frac{m_{\ell g}}{m_{gg}}.$$ Here $M$ is the mean first-passage time matrix, with $m_{ij}$ defined to be the expected number of steps, when the chain starts at $i$, that it takes to first visit $j$ after that.

Conlisk's proof [1], and Schweitzer's calculations that underlie it, use the fundamental matrix of the chain. It seems that such a simple formula should have a fairly simple, and probabilistic, proof. Is there one out there?

[1] Conlisk, J., 1985. Comparative statics for Markov chains. Journal of Economic Dynamics and Control, 9(2), pp.139-151.

[2] Schweitzer, P.J., 1968. Perturbation theory and finite Markov chains. Journal of Applied Probability, 5(2), pp.401-413.

Answer 1

Here's another, perhaps more probabilistic, approach. It's known that $\pi$ can be represented in terms of the mean occupation times as follows. Fix a state, for convenience $r$. Then, for any state $j$, $$ \pi_j=m_{rr}^{-1} E^r\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=j\}}\right], $$ where $E^r$ denotes expectation for the chain started in $r$, and $T_r$ is the first return time to $r$. (This dates back to work of Chung and Harris from the '50s; see the extension below at (*).) The "redirection" you have in mind will only be (possibly) enacted in the first transition, so conditioning on that transition will allow you easily to develop a formula for $\tilde m_{rr}(\delta)\cdot\tilde\pi_j(\delta)$: For $j\not=r$, $$ \tilde m_{rr}\tilde\pi_j = \tilde P_{r\ell}\cdot E^\ell\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=j\}}\right] +\tilde P_{rg}\cdot E^g\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=j\}}\right] +\sum_{i\not=\ell,g,r} P_{ri}\cdot E^i\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=j\}}\right] $$ and likewise $$ m_{rr}\pi_j = P_{r\ell}\cdot E^\ell\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=j\}}\right] + P_{rg}\cdot E^g\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=j\}}\right] +\sum_{i\not=\ell,g,r} P_{ri}\cdot E^i\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=j\}}\right]. $$ (I have abbreviated $\tilde\pi_j(\delta)$ to $\tilde \pi_j$, etc.) Subtracting $$ \tilde m_{rr}\tilde\pi_j-m_{rr}\pi_j = \delta\left\{ E^g\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=j\}}\right]- E^\ell\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=j\}}\right]\right\}. $$ Similarly, $$ \tilde m_{rr} =m_{rr}+\delta(m_{gr}-m_{\ell r}). $$ The derivative of $\tilde\pi_g(\delta)$ at $\delta=0$ therefore satisfies $$ {\tilde\pi'_g(0)\over \pi_r}= E^g\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=g\}}\right]- E^\ell\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=g\}}\right]+\pi_g\cdot(m_{\ell r}-m_{gr}). $$ By the strong Markov property at time $T_g$, $$ E^g\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=g\}}\right]- E^\ell\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=g\}}\right]=E^g\left[ \sum_{n=0}^{T_r-1}1_{\{X_n=g\}}\right]\cdot P^\ell[T_g>T_r]. $$ It's known (see Lemma 7 in Section 2.2 of the unpublished book of Aldous and Fill on Markov Chains: https://www.stat.berkeley.edu/users/aldous/RWG/book.html) that $$ E^g \left[\sum_{n=0}^{T_r-1}1_{\{X_n=g\}}\right]=\pi_g\cdot(m_{gr}+m_{rg}). $$ To verify Conlisk's identity we thus need to show that $$ m_{\ell g}=(m_{rg}+m_{gr})\cdot P^\ell[T_r<T_g]+m_{\ell r}-m_{gr}. $$ This follows immediately from Corollary 10 in section 2.2 of Aldous and Fill. The discussion there is probabilistic and based on the following observation (Proposition 3 of Section 2.1): If $S$ is a (possibly randomized) stopping time with $X_S=i$ and $E^i[S]<\infty$, then $$ E^i\left[\sum_{n=0}^{S-1} 1_{\{X_n=j\}}\right]=\pi_j\cdot E^i[S].\qquad\qquad(*) $$ It may be noted that A&F develop several formulas involving the fundamental matrix using this fact, and further probabilistic arguments.