We consider the impact on the stationary distribution of perturbing a Markov chain’s transition matrix. This argument due to Seneta. We show if and are probability matrices of a irreducible finite state Markov chains with stationary distributions and then we can show that

**Theorem.**

where is the total variation between the rows of .

Specifically recall that the total variation distance is given by

and we define

(From now on we will simply write instead of )

A few facts about $\tau(P)$ that we will prove after proving the above theorem are

1.

2.

3.

**Proof.** We let

Here is know as the fundamental matrix of . The sum over is well defined since (after we take out the only eigenvector of size ) the spectral radius of is less than .

First notice that

In the final inequality above we note that the term in square brackets is , and that and for .

Second notice that so

Continuing inductively (noting that also) gives that

Third, notice that

Now putting everything together

which gives the required bound.

**References.**

The term fundamental matrix is due to the study of Paul Schweitzer who first initiated the study of perturbations of Markov chains.

The arguments above are from Seneta.

The survey of Cho and Meyer compares several such bounds, they note the bound of Seneta is a factor of $n$ larger than other bounds, in the argument above we slightly tweak Seneta’s argument to improve this factor of .

Seneta, E. “Perturbation of the stationary distribution measured by ergodicity coefficients.” *Advances in Applied Probability* 20.1 (1988): 228-230.

Schweitzer, Paul J. “Perturbation theory and finite Markov chains.” *Journal of Applied Probability* (1968): 401-413.

Cho, Grace E., and Carl D. Meyer. “Comparison of perturbation bounds for the stationary distribution of a Markov chain.” *Linear Algebra and its Applications* 335.1-3 (2001): 137-150.