Return to Answer

My favorite proof so far is the one from Theorem 4.5 of Yihong Wu's lecture notes, which uses the data processing inequality to reduce the problem to the binary case — after which it is just a matter of proving a simple inequality: \begin{equation} 2(p-q)^2 \leq p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q} \tag{1} \end{equation} The cases where either $p$ or $q$ is in $\{0,1\}$ are easily checked , so we can assume $p,q\in(0,1)$. To prove (1) in this case, we introduce the function $f\colon(0,1)\to\mathbb{R}$ defined by $f(x) = p\log x + (1-p)\log(1-x)$, and observe that the RHS of (3) is exactly $f(p)-f(q)$. We then can write $$ f(p)-f(q) = \int_{q}^p f'(x)dx = \int_{q}^p \frac{p-x}{x(1-x)}dx \geq 4\int_{q}^p (p-x)dx = 4\cdot\frac{1}{2}(p-q)^2 $$ which is (1) (in the middle, we used the fact that $x(1-x) \leq 1/4$ for $x\in(0,1)$).

My favorite proof so far is the one from Theorem 4.5 of Yihong Wu's lecture notes, which uses the data processing inequality to reduce the problem to the binary case: if $S$ is a measurable subset of the domain, then we can consider the two random variable $\mathbf{1}_S$ under $P$ and $Q$, respectively, which has then distribution either $\mathrm{Bern}(P(S))$ or $\mathrm{Bern}(Q(S))$. First $$ \operatorname{TV}(\mathrm{Bern}(P(S)), \mathrm{Bern}(Q(S))) = |P(S)-Q(S)| \tag{1} $$ so we get the TV between $P$ and $Q$ by taking the supremum over all $S$. By the DPI, however, $$ \operatorname{KL}(\mathrm{Bern}(P(S))\ \|\ \mathrm{Bern}(Q(S))) \leq \operatorname{KL}(P\ \|\ Q) \tag{2} $$

This shows that it suffices to prove the binary case of Pinsker's, which is just a matter of proving a simple inequality: \begin{equation} 2(p-q)^2 \leq p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q} \tag{3} \end{equation} The cases where either $p$ or $q$ is in $\{0,1\}$ are easily checked , so we can assume $p,q\in(0,1)$. To prove (3) in this case, we introduce the function $f\colon(0,1)\to\mathbb{R}$ defined by $f(x) = p\log x + (1-p)\log(1-x)$, and observe that the RHS of (3) is exactly $f(p)-f(q)$. We then can write $$ f(p)-f(q) = \int_{q}^p f'(x)dx = \int_{q}^p \frac{p-x}{x(1-x)}dx \geq 4\int_{q}^p (p-x)dx = 4\cdot\frac{1}{2}(p-q)^2 $$ which is (3) (in the middle, we used the fact that $x(1-x) \leq 1/4$ for $x\in(0,1)$).

My favorite proof so far is the one from Theorem 4.5 of Yihong Wu's lecture notes, which uses the data processing inequality to reduce the problem to the binary case — after which it is just a matter of proving a simple inequality: \begin{equation} 2(p-q)^2 \leq p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q} \tag{1} \end{equation} The case where either $p$ or $q$ is in $\{0,1\}$ are easily checked , so we can assume $p,q\in(0,1)$. To prove (1) in this case, we introduce the function $f\colon(0,1)\to\mathbb{R}$ defined by $f(x) = p\log x + (1-p)\log(1-x)$, and observe that the RHS of (3) is exactly $f(p)-f(q)$. We then can write $$ f(p)-f(q) = \int_{q}^p f'(x)dx = \int_{q}^p \frac{p-x}{x(1-x)}dx \geq 4\int_{q}^p (p-x)dx = 4\cdot\frac{1}{2}(p-q)^2 $$ which is (1) (in the middle, we used the fact that $x(1-x) \leq 1/4$ for $x\in(0,1)$).

My favorite proof so far is the one from Theorem 4.5 of Yihong Wu's lecture notes, which uses the data processing inequality to reduce the problem to the binary case — after which it is just a matter of proving a simple inequality: \begin{equation} 2(p-q)^2 \leq p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q} \tag{1} \end{equation} The cases where either $p$ or $q$ is in $\{0,1\}$ are easily checked , so we can assume $p,q\in(0,1)$. To prove (1) in this case, we introduce the function $f\colon(0,1)\to\mathbb{R}$ defined by $f(x) = p\log x + (1-p)\log(1-x)$, and observe that the RHS of (3) is exactly $f(p)-f(q)$. We then can write $$ f(p)-f(q) = \int_{q}^p f'(x)dx = \int_{q}^p \frac{p-x}{x(1-x)}dx \geq 4\int_{q}^p (p-x)dx = 4\cdot\frac{1}{2}(p-q)^2 $$ which is (1) (in the middle, we used the fact that $x(1-x) \leq 1/4$ for $x\in(0,1)$).

My favorite proof so far is the one from Theorem 4.5 of Yihong Wu's lecture notes, which uses the data processing inequality to reduce the problem to the binary case — after which it is just a matter of proving a simple inequality, which follows from Taylor's theorem.

My favorite proof so far is the one from Theorem 4.5 of Yihong Wu's lecture notes, which uses the data processing inequality to reduce the problem to the binary case — after which it is just a matter of proving a simple inequality: \begin{equation} 2(p-q)^2 \leq p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q} \tag{1} \end{equation} The case where either $p$ or $q$ is in $\{0,1\}$ are easily checked , so we can assume $p,q\in(0,1)$. To prove (1) in this case, we introduce the function $f\colon(0,1)\to\mathbb{R}$ defined by $f(x) = p\log x + (1-p)\log(1-x)$, and observe that the RHS of (3) is exactly $f(p)-f(q)$. We then can write $$ f(p)-f(q) = \int_{q}^p f'(x)dx = \int_{q}^p \frac{p-x}{x(1-x)}dx \geq 4\int_{q}^p (p-x)dx = 4\cdot\frac{1}{2}(p-q)^2 $$ which is (1) (in the middle, we used the fact that $x(1-x) \leq 1/4$ for $x\in(0,1)$).