6
$\begingroup$

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$?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ 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$? $\endgroup$
    – whuber ♦
    Commented Aug 13, 2013 at 20:22
  • $\begingroup$ @whuber: Thanks, you're right. I corrected the statement. $\endgroup$
    – Sadeq Dousti
    Commented Aug 13, 2013 at 20:28
  • 2
    $\begingroup$ 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. $\endgroup$
    – whuber ♦
    Commented Aug 13, 2013 at 20:37
  • $\begingroup$ @whuber: I think I've found a proof. You may verify that your example works in the inequality I obtained. $\endgroup$
    – Sadeq Dousti
    Commented Aug 19, 2013 at 6:32

1 Answer 1

Reset to default
5
$\begingroup$

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

PS: This specially appears to be consistent with an example by @whuber (see comments below the question).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.