Bound covariance of two discrete random variables Let $X,Y$ be two random variables over a discrete probability space, such that $X \in [0,1]$ and $Y \in [0,1]$.  I want to prove that $$ |\text{Cov}[X,Y]| \leq \sqrt{0.5 \; I[X,Y]}$$ where $I[]$ is the mutual information of the variables.  Is there an "elegant" way to prove that?  Some smart argument rather than technical analysis.
This follows from Pinsker's inequality. The inequality states that for any two distributions (here, discrete) $P$, and $Q$, it holds that

$$\|P-Q\| \le \sqrt{2D_{\text{KL}}(P\|Q)} $$
where $D_{\text{KL}}(\cdot \|\cdot)$ is the Kullback–Leibler divergence and $|P-Q|$ is their total variation.

For the right-hand side, recall that for any $X,Y$ random variables with joint distribution $p_{x,y}(x,y)$ and marginals $p_x(x)$, $p_y(y)$, we have
$$I(X,Y) = D_{\text{KL}}(p_{x,y} \| p_x p_y).$$

So if we define $P = p_{x,y}$ and $Q=p_xp_y$, we obtain the desired right-hand side.

On the other hand, by definition,
$$
\begin{align}
\| P - Q\| &amp; = \sum_{x,y}|p(x,y) - p_x(x)p_y(y)| \\
&amp; \ge \sum_{x,y}|p(x,y) - p_x(x)p_y(y)| \cdot xy \\
&amp; = \sum_{x,y}|p(x,y)xy - p_x(x)x\cdot  p_y(y)y|\\
&amp; \ge \left|\sum_{x,y} \left(p(x,y)xy - p_x(x)x\cdot  p_y(y)y\right)\right|\\
&amp; = \left|E[XY] - E[X]E[Y]\right| \\
&amp;= |\text{cov}(X,Y)|.
\end{align}
$$
The first equality follows since $x,y \in [0,1]$ and each term is non-negative. The rest of the derivation is mostly algebra. I'm probably missing a factor 2 of the normalization of the total variation. This will give the right constant inside the square root.