0
$\begingroup$

Say we have 2 probability distributions $\pi_0, \alpha_0$ on the same state space $S$ with some transition matrix $P$. Define $\pi_1 = \pi_0 \cdot P$, $\alpha_1 = \alpha_0 \cdot P$. The goal is to show that $$\vert\vert \pi_1 - \alpha_1\vert\vert_{TV} \leq \vert\vert \pi_0 - \alpha_0\vert\vert_{TV}$$
where $\vert\vert\cdot\vert\vert_{TV}$ denotes the total variation distance, which can be defined as $sup_{E \in S}\vert\pi(E)-\alpha(E)|$.

Here is my attempt:

$\vert\vert \pi_1 - \alpha_1\vert\vert_{TV} = \vert\vert \pi_0P - \alpha_0P\vert\vert_{TV} = sup_{E \in S}\vert(\pi_0P)(E)-(\alpha_0P)(E)|$

This is such a silly question, but how do I get that matrix $P$ out of there, and how do I use the fact that it's specifically a probability transition matrix (ie. all entries between $0$ and $1$) to reach the conclusion?

$\endgroup$

1 Answer 1

1
$\begingroup$

An equivalent definition of total variation distance is: $$||x-y||_{TV} = \frac{1}{2} \sum_i |x_i-y_i|.$$ Therefore: $$||\pi_1 - \alpha_1||_{TV} = ||(\pi_0-\alpha_0)P||_{TV} \leq \frac{1}{2} \sum_i \sum_j P_{j,i} | \pi_0(j) - \alpha_0(j)|.$$ After changing the order of summation we obtain: $$||\pi_1 - \alpha_1||_{TV} \leq \frac{1}{2} \sum_j | \pi_0(j) - \alpha_0(j)| \sum_i P_{j,i}.$$ Since $P$ is stochastic this is equal to $$\frac{1}{2} \sum_j | \pi_0(j) - \alpha_0(j)| = ||\pi_0 - \alpha_0||_{TV}.$$

$\endgroup$
1
  • $\begingroup$ I just worked out how to show the definition you provided is equivalent to the one I had, and your answer is brilliant. Thank you so much! $\endgroup$
    – 0k33
    Feb 19, 2019 at 20:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .