# Probabilistic proof for derivative of invariant distribution of a Markov chain

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.

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 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.