Perturbation of Markov Matrices

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

Theorem.

$\displaystyle || \pi - \tilde \pi ||_{TV} \leq \frac{1}{1- \tau(P)} \sum_{x} \left\| P_{x, \cdot} -\tilde P_{x, \cdot} \right\|_{TV}$

where $\tau(P)$ is the total variation between the rows of $P$ .

Specifically recall that the total variation distance is given by

|| \mu - \lambda ||_{TV} := \frac{1}{2} \sum_{x \in \mathcal X} | \mu(x) - \lambda(x) |

and we define

\tau(P) :=\frac{1}{2} \max_{x,x'} \big\| P_{x} - P_{x'} \big\|_{TV}

(From now on we will simply write $|| \cdot ||$ instead of $||\cdot||_{TV}$ )

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

\tau(P) = 1 - \min_{x,x'} \sum_{y} \min \{ p_{xy},p_{x'y} \}.

Proof. We let

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

First notice that

In the final inequality above we note that the term in square brackets is $Z^{-1}$ , and that $\tilde{ \pi}^\top 1 = 1$ and $\pi^\top Q^t = 0$ for $t\geq 1$ .

Second notice that $v^\top 1=0$ so

$v^\top Q = v^\top P - v^\top 1 = v^\top P\, .$

Continuing inductively (noting that $v^\top Q 1 = 0$ also) gives that

Third, notice that

Now putting everything together

which gives the required bound. $\square$

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

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.

Share this:

Like this:

Leave a Reply Cancel reply