How does changing a transition matrix change the corresponding invariant distribution? Let $T$ be an $N \times N$ ergodic transition matrix, and let
$$
E =
\begin{bmatrix}
0_{1,1} & \cdots &\varepsilon_{1,j} &\cdots & -\varepsilon_{1,k} & \cdots & \\
0_{1,2} & \cdots & & & & & \\
\vdots & \ddots & & & & & 0_{N,N}
\end{bmatrix}
$$
be an $N \times N$ matrix that only has two non-zero entries: $\varepsilon > 0$ in position $1,j$ and $-\varepsilon$ in position $1,k$.
There must exist some invariant distribution $\lambda$ such that $\lambda T = \lambda$. If $T + E$ is also an ergodic transition matrix, then there must exist an invariant distribution $\hat{\lambda}$ such that $\hat{\lambda}(T + E) = \hat{\lambda}$.
I conjecture that $\hat{\lambda}_j > \lambda_j$ and $\hat{\lambda}_k < \lambda_k$, but I have been unable to prove it or to find a published result. So far I've tried solving:
$$(\lambda + e)(T + E) = \lambda + e \Rightarrow \lambda E + eT + eE = e$$
subject to the constraints that $\sum_{i = 1}^N e_i = 0$ and $-1 < e_i < 1$, but I have not been able to show that $e_j > 0 > e_k$. I have been unable to find counterexamples either, even after writing a script that randomly generates matrices.
 A: The conjecture is true, and here is a probabilistic argument: Recall that $1 / \lambda_j$ is the mean sojourn time from state $j$, that is,
$$ 1 / \lambda_j = \mathbf{E}[\tau | X_0 = j] , $$
where
$$ \tau = \min\{n > 0 : X_n = j\} . $$
Here $X_n$ is a Markov chain with transition matrix $T$. Denote by $p_{xy}$ the entries of the matrix $T$, and let $q_{xy}$ be the entries of the matrix $T + E$.
Let $S_1, S_2, \ldots$ be the (increasing) sequence of all $n$ such that $X_{n-1} = 1$ and $X_n = k$. Let $M$ be a geometric random variable with parameter $\delta = \varepsilon / p_{1,k}$, independent from the process $X_n$. Consider
$$ \hat{\tau} = \min(\tau, S_M) . $$
We claim that $\hat{\tau}$ (conditionally on $X_0 = j$) is equal in distribution to the sojourn time of a Markov chain with transition matrix $T + E$ (conditionally on $X_0 = j$). This clearly implies that $1 / \hat{\lambda}_j < 1 / \lambda_j$, which is equivalent to the original conjecture. (The other inequality, $\hat{\lambda}_k < \lambda_k$ is obtained by exchanging the roles of $T$ and $T + E$, and $j$ and $k$).
In order to prove our claim, it suffices to show that
$$ \mathbf{P}(\hat{\tau} = n, X_1 = x_1, \ldots, X_{n-1} = x_{n-1} | X_0 = j) = q_{jx_1} q_{x_1x_2} \ldots q_{x_{n-2}x_{n-1}} q_{x_{n-1}j} . \tag{*}$$
Suppose that the sequence of states $1,k$ occurs in $x_1, \ldots, x_{n-1}$ exactly $m$ times. The left-hand side of ($^*$) can be expressed as the sum of
$$ \mathbf{P}(M > m, \tau = n, X_1 = x_1, \ldots, X_{n-1} = x_{n-1} | X_0 = j) = (1 - \delta)^m p_{jx_1} p_{x_1x_2} \ldots p_{x_{n-2}x_{n-1}} p_{x_{n-1}j} $$
and, if $x_{n-1} = 1$,
$$ \mathbf{P}(M = m + 1, X_1 = x_1, \ldots, X_{n-1} = x_{n-1}, X_n = k | X_0 = j) = \delta (1 - \delta)^m p_{jx_1} p_{x_1x_2} \ldots p_{x_{n-2}x_{n-1}} p_{x_{n-1}k} . $$
Recall that $q_{xy} = p_{xy}$ except $q_{1k} = (1 - \delta) p_{1k}$ and $q_{1j} = p_{1j} + \varepsilon = p_{1j} + \delta p_{1k}$. Furthermore, in the above products, $p_{1j}$ appears only if $x_{n-1} = 1$ (as the last term), and $p_{1k}$ appears exactly $m$ times. This gives the desired result ($^*$).
