$$

Adapted from the tutorial Information theory in combinatorics I by Shachar Lovett at Simons.

Entropy is subadditive: the information you have in a pair of random variables $(X,Y)$ is bounded by the information you have in each of them individually

$$\mathrm{H}[X,Y]\le \mathrm{H}[X]+\mathrm{H}[Y].$$

In fact, the difference between the two is precisely the mutual information $\mathrm{I}[X:Y]$.

Shearer’s lemma generalizes this principle to groups of variables, not just individual variables: the point is that if both sides have the same variables, but the right side takes the entropy of smaller groups, then the right side overcounts some of the mutual information, so it’s bigger. For example:

$$2\cdot \mathrm{H}[X,Y,Z]\le \mathrm{H}[X,Y]+\mathrm{H}[X,Z]+\mathrm{H}[Y,Z].$$

And in general, if you have $n$ variables $X_1,\dots ,X_n$ and $m$ groups $I_1,\dots ,I_m\subseteq [n]$ such that each variable is contained in exactly¹ $q$ of the groups, Shearer’s lemma says that

$$q\cdot \mathrm{H}[X_1,\dots ,X_n]\le \mathrm{H}[X_{I_1}]+\cdots +\mathrm{H}[X_{I_m}].$$

Proof

You can “prove” the simple subadditivity principle using the chain rule:

$$\mathrm{H}[X,Y]=\mathrm{H}[X]+\mathrm{H}[Y\mid X]\le \mathrm{H}[X]+\mathrm{H}[Y],$$

since conditioning can only decrease entropy.

Similarly, we can prove Shearer’s lemma by applying the chain rule on both sides, and observing that the left side has stronger conditioning. Specifically, we rewrite the LHS as

$$q\cdot \mathrm{H}[X_1,\dots ,X_n]=q\cdot \mathrm{H}[X_1]+q\cdot \mathrm{H}[X_2\mid X_1]+\cdots +q\cdot \mathrm{H}[X_n\mid X_{[n-1]}]$$

and for each set $I_j=\{i_1,\dots ,i_k\}$ (with $i_1<\cdots <i_k$), we rewrite the RHS as

$$\begin{array}{rl}\mathrm{H}[X_{I_j}]& =\mathrm{H}[X_{i_1}]+\mathrm{H}[X_{i_2}\mid X_{i_1}]+\cdots +\mathrm{H}[X_{i_k}\mid X_{i_1},\dots ,X_{i_{k-1}}]\\ & \ge \mathrm{H}[X_{i_1}\mid X_{[i_1-1]}]+\mathrm{H}[X_{i_2}\mid X_{[i_2-1]}]+\cdots +\mathrm{H}[X_{i_k}\mid X_{[i_k-1]}].\end{array}$$

Because each variable $i$ is contained in exactly $q$ of the sets $I_j$, summing this up will produce exactly $q$ copies of $\mathrm{H}[X_i\mid X_{[i-1]}]$.

Shadows

Shearer’s lemma is particularly useful in combinatorics if you let $({\mathit{X}}_1,\dots ,{\mathit{X}}_n)$ be uniform over some set of points you want to show is small.

As a toy example, suppose I have a set $S\subseteq {\mathbb{R}}^2$ and I tell you that its “shadows” on the $x$- and $y$-axis have $\le n$ points.² How many points can $S$ have? The answer is easy: there are only $n$ possible $x$-coordinates and $n$ possible $y$-coordinates, so there can be at most $n^2$ points. This is achieved by an $n\times n$ grid.

Although it’s very overkill, you could have used the subadditivity of entropy to prove this. Let $(X,Y)$ be a uniformly random point in $S$. Then $\mathrm{H}[X,Y]=\log |S|$. But $X$ and $Y$ are distributions over $\le n$ points, so each can only contain $\log n$ bits of information. So we have

$$\log |S|=\mathrm{H}[X,Y]\le \mathrm{H}[X]+\mathrm{H}[Y]\le 2\log n\Rightarrow |S|\le n^2.$$

If you move to three dimensions, though, it’s less obvious. This time, I have $S\subseteq {\mathbb{R}}^3$, and I tell you that its shadows on the $xy$-, $xz$- and $yz$-plane have $\le n$ points. How many points can $S$ have? The best “elementary” argument observes that there are $\le n$ possible values $(x,y)$, and there are also $\le n$ possible values for $z$, so $|S|\le n^2$. Again letting $(X,Y,Z)$ be a uniformly random point in $S$, this corresponds to the following entropy argument

$$\log |S|=\mathrm{H}[X,Y,Z]\le \mathrm{H}[X,Y]+\mathrm{H}[Z]\le \mathrm{H}[X,Y]+\mathrm{H}[X,Z]\le 2\log n\Rightarrow |S|\le n^2.$$

But the obvious example is the $\sqrt{n}\times \sqrt{n}\times \sqrt{n}$ grid, which has only $n^{3/2}$ points. To show that this is optimal, we use Shearer’s lemma:

$$2\log |S|=2\mathrm{H}[X,Y,Z]\le \mathrm{H}[X,Y]+\mathrm{H}[X,Z]+\mathrm{H}[Y,Z]\le 3\log n\Rightarrow |S|\le n^{3/2}.$$

Entropy deficit version

Because entropy deficit is basically “negative entropy”, we get an inequality in the other direction:

$$q\cdot \mathrm{D}[{\mathit{X}}_1,\dots ,{\mathit{X}}_n]\ge \mathrm{D}\left[{\mathit{X}}_{I_1}\right]+\cdots +\mathrm{D}\left[{\mathit{X}}_{I_m}\right].$$

(where each variable is in exactly³ $q$ of the groups $I_1,\dots ,I_m$). This says that if $\mathit{X}$ is “locally far from uniform” in the sense that the “marginals” ${\mathit{X}}_{I_j}$ are far from uniform, then $\mathit{X}$ must also be proportionally far.

For example, suppose I have some events $E_1,\dots ,E_m$, and I tell you that each $\mathrm{Pr}[E_j]\le p$. What can you say about the probability $\mathrm{Pr}\left[\underset{j}{\bigwedge }{E}_j\right]$ that they all happen simultaneously?

• If the events are independent, you get $\le p^m$.
• But absent any additional information, the best you can get is $\le p$: indeed, they could all be the same event.

Now, assume the events $E_1,\dots ,E_m$ are “read-$q$”: that is, each $E_j$ depends only on a groups $I_j\subseteq [n]$ of some underlying independent random variables $x_1,\dots ,x_n$, so that each variable is $q$ groups. We’ll see that you get $\le p^{m/q}$. This is optimal, since those $m$ events could be $m/q$ independent events, each repeated $q$ times.

Let $I_j\subseteq [m]$ be the set of variables queried by event $E_j$. Let $\mathit{X}$ be uniform over $\left\{x\right|\underset{j}{\bigwedge }{E}_j(x)\}$. Then

• $\mathrm{D}\left[\mathit{X}\right]=\log \frac{1}{\mathrm{Pr}[\underset{j}{\bigwedge }{E}_j]}$;
• ${\mathit{X}}_{I_j}$ can only take values in $\left\{x_{I_j}\right|E_j(x)\}$, so $\mathrm{D}\left[{\mathit{X}}_{I_j}\right]\le \log \frac{1}{\mathrm{Pr}[E_j]}$.

#to-write make the logic above clearer

Therefore, we get

$$\begin{array}{rl}\mathrm{Pr}\left[\underset{j}{\bigwedge }{E}_j\right]& =2^{-\mathrm{D}\left[\mathit{X}\right]}\\ & \le 2^{-\frac{\mathrm{D}\left[{\mathit{X}}_{I_1}\right]+\cdots +\mathrm{D}\left[{\mathit{X}}_{I_m}\right]}{q}}\\ & \le {(\mathrm{Pr}[E_1]\cdots \mathrm{Pr}[E_m])}^{1/q}\\ & \le p^{m/q}.\end{array}$$

Related

Other applications

• Shearer’s lemma gives tight bounds on the number of independent sets in bipartite $n\times n$ $d$-regular graphs: $\le (2^{d+1}-1{)}^{n/d}\approx 2^{n+n/d}$, which is achieved by $n/d$ copies of $K_{d,d}$. The variable to look at is the indicator (in ${\{0,1\}}^{2n}$) of a uniformly random independent set.

Similar results

• Gavinsky, Lovett, Saks, and Srinivasan⁴ proved a read-$q$ variant of the Chernoff bound (which similarly worsens the bound from $m$ to $m/q$).
• The Local lemma is another result about a relaxed notion of independence. However,
  • the assumption is stronger: the events are not allowed to share variables with too many other events, whereas Shearer’s lemma only assumes that each variable is queried few times;
  • it’s a lower bound on $\mathrm{Pr}\left[\underset{j}{\bigwedge }\overline{E_j}\right]$, not an upper bound on $\mathrm{Pr}\left[\underset{j}{\bigwedge }{E}_j\right]$.

1. We could also write “at least $q$”, since adding more variables to a group can only increase the RHS. ↩

2. That is, if we write $S_x:=\{x\mid (x,y)\in S\}$ then $|S_x|\le n$, and similarly for $y$. ↩

3. #to-write ↩

4. Dmytro Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan, “A Tail Bound for Read-k Families of Functions”. ↩