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

  • $\begingroup$ What is $P(X_i)$? $\endgroup$ – js21 Jul 26 '17 at 8:34
  • $\begingroup$ I added an update to explain the (common) notation. $\endgroup$ – 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.


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:




You can also have a look at definition 1.7 in this article :


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

It implies a particular type of isoperimetric inequality used in percolation theory.

  • $\begingroup$ The paper "Basic properties of strong mixing conditions. A survey and some open questions" by Richard C. Bradley seems to have a similar condition on p.108. $\endgroup$ – martin cripps Jul 26 '17 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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