Upper/lower bound on covariance two dependent random random variables. X and Y are two dependent random variables. Marginal pmfs f(X) and f(Y) is given, but joint pmf f(X,Y) is not known. Is it possible to find upper/lower bound on covariance cov(X,Y)?
 A: The covariance between $X$ and $Y$ is defined as
$$
\mathrm{Cov}(X,Y)={\rm E}[(X-\mu_X)(Y-\mu_Y)],
$$
where $\mu_X={\rm E}[X]$ and $\mu_Y={\rm E}[Y]$ are the two means. By Cauchy-Schwarz' inequality we have
$$
\begin{align}
|\mathrm{Cov}(X,Y)|&=|{\rm E}[(X-\mu_X)(Y-\mu_Y)]|\leq {\rm E}\left[(X-\mu_X)^2\right]^{1/2}{\rm E}\left[(Y-\mu_Y)^2\right]^{1/2}\\
&=\sqrt{\mathrm{Var}(X)\mathrm{Var}(Y)}.
\end{align}
$$
where
$$
\mathrm{Var}(X)\mathrm{Var}(Y)=\left\{\int (x-\mu_X)^2\, f_X(x)\,\mathrm dx\right\}\cdot\left\{\int (y-\mu_Y)^2f_Y(y)\,\mathrm dy\right\}.
$$
Every value between the lower and upper bound can be realized. To see this let $X,X'$ be i.i.d. and $U$ a Bernoulli variable independent of $(X,X')$ with $P(U=1)=p$. If we let $Y=UX+(1-U)X'$, then
$$
\mathrm{Cov}(Y,X)=\mathrm{Cov}(UX,X)+\mathrm{Cov}((1-U)X',X)=\mathrm{Cov}(UX,X).
$$
By expanding this we obtain 
$$
\mathrm{Cov}(Y,X)=E[U]\mathrm{Var}(X)=p\sqrt{\mathrm{Var}(X)\mathrm{Var}(Y)}
$$
since $X\sim Y$. Letting $p$ vary between $0$ and $1$ we can realize all values between $0$ and the upper bound $\sqrt{\mathrm{Var}(X)\mathrm{Var}(Y)}$.
Finally, let $Y=-(UX+(1-U)X')$, then we still have $X\sim Y$, but now
$$
\mathrm{Cov}(X,Y)=-p\sqrt{\mathrm{Var}(X)\mathrm{Var}(Y)}.
$$
