# Relations between probabilities of "almost" independent random variables

Let $X$ and $Y$ be two random variables, such that the (average) mutual information is very small: $$0 \le I(X;Y) \le \epsilon \ll 1$$

In this case, we say that $X$ and $Y$ are almost independent. Now, can we deduce something like: $$\forall x,y \quad \Pr[X=x,Y=y] \le \Pr[X=x]\cdot\Pr[Y=y] + \delta$$ with $\delta$ being a (possibly negative) function of $\epsilon$?

If the general case above cannot be proven, maybe we can use the following special case:

Let $X$ and $Y$ be discrete random variables, taking values from a finite set $D$ with $|D|=2^n$. Moreover, let $\epsilon$ be exponentially small in $n$, say $\epsilon = 2^{-n/2}$.

Can we now obtain $\delta$ as a function of $\epsilon$?

• A little more precision in the main statement would help. Where you write $\Pr[XY]$, what is that exactly? A probability attaches to a measurable set (an event), not to a random variable. Do you perhaps mean to state something about $\Pr_{(X,Y)}[A\times B]$ relative to $\Pr_X[A]\Pr_Y[B]$ for all $X$-measurable sets $A$ and $Y$-measurable sets $B$?
– whuber
Aug 13, 2013 at 20:22
• @whuber: Thanks, you're right. I corrected the statement. Aug 13, 2013 at 20:28
• It can be insightful to look at simple examples. For instance, consider these probabilities for $(X,Y)$: $(0,0)\to 1-2\gamma$, $(0,1)\to\gamma$, $(1,0)\to\gamma$, and $(1,1)\to 0$, with $0\le\gamma\le 1/2$. If I have computed correctly, there appears to be a huge inverse relationship between $I(X;Y)$ and the discrepancy you write down, which would preclude the existence of a useful bound for $\delta$. The difficulty seems to stem from the fact that $I$ is a multiplicative relationship among probabilities whereas $\delta$ is an additive measure; there's no apparent connection between them.
– whuber
Aug 13, 2013 at 20:37
• @whuber: I think I've found a proof. You may verify that your example works in the inequality I obtained. Aug 19, 2013 at 6:32

Let $D_{\mathrm{KL}}(P\|Q)$ denote the Kullback–Leibler divergence between discrete probability distributions $P$ and $Q$. It is well-known that the following relation holds between the KL-divergence and mutual information: $$I(X;Y)=D_{\mathrm{KL}}(P(X,Y)\|P(X)P(Y)) \enspace,$$ where $P(Z)$ denotes the probability distribution corresponding to the random variable $Z$.
Now, consider the definition of total variation distance between discrete probability distributions $P$ and $Q$: $$\Delta = \frac 1 2 \sum_x \left| P(x) - Q(x) \right|\enspace.$$
Pinsker's inequality gives the relation between the KL divergence and the total variation distance: $$\Delta(P,Q) \le \sqrt{\frac{\ln 2}{2} D_{\mathrm{KL}}(P\|Q)} \enspace.$$ (The term $\ln 2$ appears since I'm measuring the entropy in bits, while the respective Wikipedia formula uses nats.)
Finally, we note that for any $x,y$, we have ($\delta$ and $\epsilon$ are defined in the question): $$|\delta| = \Big|\Pr[X=x,Y=y]-\Pr[X=x]\cdot\Pr[Y=y] \Big| \le 2\Delta(P(X,Y),P(X)P(Y)) \le 2\sqrt{\frac{\ln2}{2}D_{\mathrm{KL}}(P(X,Y),P(X)P(Y))}=2\sqrt{\frac{\ln2}{2}I(X;Y)}=\sqrt{2\epsilon\ln2} \enspace.$$