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.


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

  • $\begingroup$ Thank you!! This looks great $\endgroup$
    – Ben Golub
    Nov 28, 2021 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.