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