Applying Cauchy-Schwarz inequality

Question

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.

Answer 1

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)}$.