Is the pairwise independence gap bounded to $\left[-\frac{1}{4},\frac{1}{4}\right]$? What about for n variables?

Question

The independence gap is defined as

$$\phi_{X_1, \ldots, X_n}(x_1, \ldots, x_n) \triangleq F_{X_1, \ldots, X_n}(x_1, \ldots, x_n) - \prod_{j=1}^n F_{X_j}(x_j)$$

where $F_{X_1, \ldots, X_n}(x_1, \ldots, x_n)$ is the joint CDF over random variables $X_1, \ldots, X_n$ and $F_{X_j}(x_j)$ is the marginal CDF over the random variable $X_j$.

When I first considered this function I figured that the image would be $[-1,1]$ from plugging in the min/max values in $[0,1]$ for the respective joint and marginal probabilities.

$$\underbrace{1}_{\text{joint}} - \underbrace{0}_{\text{marginals}} = \underbrace{1}_{\text{independence gap}}$$ $$\underbrace{0}_{\text{joint}} - \underbrace{1}_{\text{marginals}} = \underbrace{-1}_{\text{independence gap}}$$

But then I started considering the Frechet inequalities. If I started with the marginals only, I could put an interval on the possible values of the joint probability without any assumption of statistical independence. And then compute an interval for independence gap using basic interval arithmetic.

What I found was that for pairs of variables that the independence gaps were more tightly bounded than I had expected from the above calculations. Intead of $\phi_{X_1, X_2} \in [-1,1]$ I found that $\phi_{X_1, X_2} \in \left[ -\frac{1}{4}, \frac{1}{4} \right]$. From what I understand the Frechet inequalities don't make any special assumptions, but I could be wrong.

Is my inference correct that the pairwise independence gap is bounded to $\left[-\frac{1}{4},\frac{1}{4}\right]$?

Question

Are the bounds on the independence gap different as a function the number of variables $n \geq 2$?

Answer 1

This is not just a question about cumulative distribution functions but about events.

What is the possible range of the difference

$$P\left(A_1 \text{ and } A_2\right) - P\left(A_1\right)P\left(A_2\right) $$

or more generally for $n$ events

$$P\left(\bigwedge_{i=1}^n A_i\right) - \prod_{i =1}^n P\left(A_i\right)$$

---

We can write the individual events as

$$P\left(A_i\right) = P\left(\bigwedge_{i=1}^n A_i\right) + P\left(A_i \text{ and } \bigvee_{i=1}^n \lnot A_i\right)$$

that is, the probability of all $A_i$ plus the probability of $A_i$ when one or more of the other $A_i$ are not the case.

• The lowest minimum occurs when $P\left(\bigwedge_{i=1}^n A_i\right) = 0$ and $P\left(A_i \text{ and } \bigvee_{i=1}^n \lnot A_i\right) = 1-\frac{1}{n}$. This is when there is always exactly one of the events $A_i$ not true, which needs to occur with probability $\frac{1}{n}$ if we share the probabilities equally (which leads to the largest product). Then

  $$\text{minimum bound} = -\left(1-\frac{1}{n} \right)^n$$

• The largest maximum occur when the events are fully dependent and for all $i$ we have $P\left(A_i\right) = P\left(\bigwedge_{i=1}^n A_i\right)$ which leads to the gap being equal to

  $$\text{fully correlated gap} = P\left(\bigwedge_{i=1}^n A_i \right) - P\left(\bigwedge_{i=1}^n A_i\right)^n$$

  which has a maximum in $P\left(\bigwedge_{i=1}^n A_i\right))= (\frac{1}{n})^{\frac{1}{n-1}}$ and

  $$\text{maximum bound} = \left(\frac{1}{n}\right)^{\frac{1}{n-1}} - \left(\frac{1}{n}\right)^{\frac{n}{n-1}} $$

Among with these equations I have the image from this question in my mind Multiply, add, or condition on probability?

Also this question: If 'B is more likely given A', then 'A is more likely given B' has that image.

Answer 2

A quick Monte Carlo suggests that the bounds can be wider for $n> 2$.

import numpy as np
np.random.seed(2018)

m = 10**6

L = []
U = []

for n in range(2, 101):
    p = np.random.uniform(size=m*n).reshape(m,n)
    sump = np.sum(p, axis=1)
    prodp = np.prod(p, axis=1)

    lower = np.maximum(sump - (n-1), 0) - prodp
    upper = np.min(p, axis=1) - prodp

    L.append(np.min(lower))
    U.append(np.max(upper))
    print(n)

import matplotlib.pyplot as plt

plt.plot(range(2,101), L, label='Min Lower Bound')
plt.plot(range(2,101), U, label='Max Upper Bound')
plt.xlabel('Sample Size')
plt.ylabel('Estimated Gap')
plt.legend()
plt.show()

The result was:

which indicates that the interval on the independence gap for greater than 2 variables can be wider than that for two.

Somewhere between $n=7$ and $n=9$ the behaviour in my simulation changes. I suspect this likely showing the $m=10^6$ as a sample size becomes insufficient. Essentially we are sampling uniformly from the interior of an unit $n$-cube, which becomes inefficient for larger dimension than about $n=7$.

An exact expression for the bounds as a function of $n$ would still be appreciated.

Answer 3

For a given $n$, a naive guess is there are optimal $p$ and $q$ such the bounds of the independence gap are given by:

$$\phi \in \left[-q^n, p-p^n \right]$$

where $q \leq \frac{n-1}{n}$.

Let's visualize some cases with Desmos. Here I have separate plots for the lower and upper bounds, but don't be confused by the fact that Desmos is using a generic $x$ in both cases.

For n=2 we seem to get that $p=q=\frac{1}{2}$. For $q$ this is read off the graph where the purple curve intersects with the the red region and that the purple curve is at its minimum. As far as I have seen, this can be simplified to where $q = \frac{n-1}{n}$, which for $n=2$ gives $q = \frac{1}{2}$. The value of $p$ is whatever the maximum value of the black curve is.

For $n=3$ we get different answers for $p$ and $q$. It appears that $p \approx 0.5775$, whereas $q = \frac{2}{3}$.

Changing the $n$ slider in Desmos gives me an impression that the curves converge to a result as $n$ becomes large:

It also seemed that among the plots that there was always a unique maximum for $p$, and likewise for $q=\frac{n-1}{n}$.For $p-p^n$ the optimal value of $p$ can be specified by its derivative.

$$\frac{\partial}{\partial p} \left[ p-p^n \right] = 1 - n p^{n-1}.$$

Letting $\frac{\partial}{\partial p} \left[ p-p^n \right] = 0$, then

$$1 - n p^{n-1} = 0 \iff \sqrt[n-1]{\frac{1}{n}} = p \iff \frac{1}{\sqrt[n-1]{n}} = p$$

We know by the fundamental theorem of algebra that there could be $n-1$ candidates for $p$, but looking at the plots I think $p \in [0,1]$ will imply a unique real-valued solution.

So my revision of the interval is given by:

$$\phi \in \left[ - \left(1\ -\ \frac{1}{n}\right)^n, \left(1\ -\ \frac{1}{n}\right) n^{\left(\frac{1}{1-n}\right)} \right]$$

Plotting the lower and upper bound we can see that near-absolute-unity independence gaps are not achieved even with 14 variables.

Lastly, we can use these derived bounds to normalize any observed Frechet bounds such that $-1 \leq \phi \leq 1$ as I had originally expected:

$$\phi_{\text{Normalized}} \in \left[ \frac{\max \left(0, \sum_{k=1}^n P(A_k) - (n-1) \right) - \prod_{k=1}^n P(A_k) }{\left( 1 - \frac{1}{n} \right)^n}, \frac{\min_k \{ P(A_k) \} - \prod_{k=1}^n P(A_k)}{\left(1 - \frac{1}{n} \right)n^{\frac{1}{1-n}}} \right]$$

All of these results are provisional on my guess being correct, which it readily may not be.