# Applying Cauchy-Schwarz inequality

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.

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)}$$.
• 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! Oct 25, 2021 at 19:48