# A notion of weak dependence

Let $(X_1,\ldots,X_n)$ be a collection of random variables. For $\alpha\ge1$, let us say that these are $\alpha$-weakly dependent if for all $1\le k\le n$ and all $1\le i_1<\ldots< i_k$, we have $$\alpha^{-k}\le \frac{ P(X_{i_1},\ldots,X_{i_k})} {\prod_{j=1}^k P(X_{i_j})} \le \alpha^k .$$ Obviously, the $n$-tuple is independent iff it is $1$-weakly dependent.

Question: Is this notion new? Related to any other notions of weak dependence? Known to imply concentration results?

Update. $P(X_i)$ is shorthand for $P(X_i=x_i)$; i.e., it specifies the distribution of $X_i$.

• What is $P(X_i)$? – js21 Jul 26 '17 at 8:34
• I added an update to explain the (common) notation. – Aryeh Kontorovich Jul 26 '17 at 10:00

This reminds me of the notion of $(\epsilon, k)$-wise independence for random bit vectors. That is, given a set of $n$ random binary bits $X_i \sim \text{Bernoulli}\left(\frac{1}{2}\right)$, they are said to be $(\epsilon, k)$-wise independent if for any $S \subset [n], |S| = k,$ we have that $\left| \text{Pr}\left(\cap_{i \in S}\mathbb{1}\{X_i = 1\}\right) - 2^{-k} \right| \leq \epsilon$. This came up when I was crashing a course on probabilistic algorithms.

In your scenario, seeing as we are comparing the ratio between probabilities, we would achieve $k$-wise independence if the ratio $r := \frac{\text{Pr}\left(\cap_{i \in S}\mathbb{1}\{X_i = 1\}\right)}{2^{-k}} = 1$. Naturally the comparison to make then it would make sense to define this around the inequality $|r - 1| \leq \epsilon$, or for that matter try to bound the difference of log probabilities in an $\epsilon$-ball.

---EDIT---

I was thinking about this a little more, I think the independence relation we want to look at is indeed $r = 1 \iff \log\text{Pr}\left(\cap_{i \in S}\mathbb{1}\{X_i = 1\}\right) - \log2^{-k} = 0$.

In the same vein as almost $k$-wise independence, we would like to bound this difference in some $\epsilon$-ball, choosing $\epsilon < k\log\alpha$, since the inequality:

$$\alpha^{-k} \leq \frac{\text{Pr}\left(\cap_{i \in S} X_i\right)}{\prod_{i \in S}\text{Pr}(X_i)} \leq \alpha^k$$

implies the inequality in the case of random binary bits

$$\left|\log\text{Pr}\left(\cap_{i \in S}\mathbb{1}\{X_i = 1\}\right) - \log2^{-k}\right| \leq k\log\alpha.$$

Your particular presentation of probabilities generalizes this to finite collections of arbitrary random variables.

Some of the more popular resources on the topic:

where it is called a "decoupling inequality". Only the upper bound, though, and not completely the same as yours (up to a constant in front of $\alpha^k$).