0
$\begingroup$

I am trying to understand a proof concerning the strong stationary times of finite Markov Chains presented in ‘Markov Chains and Mixing Times’. More specifically, I am struggling to work out how the Cauchy-Schwarz inequality is applied in a step of the proof. In what follows, I will use $P(x, y)$ to denote the probability of moving from state $x$ to state $y$ and $\pi(x)$ to denote the value of stationary distribution at state $x$. Additionally I will use $\mathcal{X}$ to denote the set of all states. The proof claims that the following can be shown via the Cauchy—Schwarz inequality:

$$ \sum_{z \in \mathcal{X}}\pi(z)\frac{P^{t}(x, z)P^{t}(y, z)}{{\pi(z)}^{2}} \geq \left(\sum_{z \in \mathcal{X}}\sqrt{P^{t}(x, z)P^{t}(y, z)} \right)^{2} $$

I am not really sure how Cauchy-Schwarz is applied here to get this result. I am also not sure if Cauchy-Schwarz alone is enough or if you have to use some extra information regarding the stochasticity of both $P$ and $\pi$. Any help would be appreciated.

I am assume that I need to write the sum on the left hand side in the form of $\langle u , u \rangle \cdot \langle v, v\rangle$ But can’t work out how to do this. For those curious I am trying to understand the proof of Lemma 6.17 in ‘Markov Chains and Mixing Times’ by Levin and Peres.

EDIT: Following AngryAvian’s helpful reply I now understand how the CS-inequality is being applied. I have added the full derivation here for anyone that may be interested

Note that, because $\pi$ is a distribution, we have that $$ \langle \sqrt{\pi}, \sqrt{\pi}\rangle = \sum_{z \in \mathcal{X}}\sqrt{\pi(z)} = \sum_{z \in \mathcal{X}}\pi(z) = 1. $$

Thus we have $$ \sum_{z \in \mathcal{X}}\pi(z)\frac{P^{t}(x, z)P^{t}(y, z)}{{\pi(z)}^{2}} = \left(\sum_{z \in \mathcal{X}}\pi(z)\frac{P^{t}(x, z)P^{t}(y, z)}{{\pi(z)}^{2}}\right)\langle \sqrt{\pi}, \sqrt{\pi}\rangle \\ = \left(\sum_{z \in \mathcal{X}}\sqrt{\pi(z)\frac{P^{t}(x, z)P^{t}(y, z)}{{\pi(z)}^{2}}}\sqrt{\pi(z)\frac{P^{t}(x, z)P^{t}(y, z)}{{\pi(z)}^{2}}}\right)\langle \sqrt{\pi}, \sqrt{\pi} \rangle \\ \geq \left(\sum_{z \in \mathcal{X}}\sqrt{\pi(z)}\sqrt{\pi(z)\frac{P^{t}(x, z)P^{t}(y, z)}{{\pi(z)}^{2}}}\right)^{2} \\ = \left(\sum_{z \in \mathcal{X}}\sqrt{P^{t}(x, z)P^{t}(y, z)}\right)^{2} $$

Where the inequality follows from the CS-inequality. So the fact that $\pi$ is a distribution is crucial here, as it allows you to add an inner product in order to leverage CS.

$\endgroup$

1 Answer 1

1
$\begingroup$

Try $\langle u, u\rangle \langle v, v \rangle \ge (\langle u, v \rangle)^2$ with $u_z = \sqrt{\pi(z)\frac{P(x,z) P(y,z)}{\pi(z) \pi(z)}}$ and $v_z = \sqrt{\pi(z)}$.

$\endgroup$
1
  • $\begingroup$ Ah I see, so the fact that $\pi$ is a distribution is used here. Thanks for the help, I have updated the answer with the full derivation! $\endgroup$ Oct 25, 2021 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.