What's the motivation of entropy as a combinatorical tool? What problems is it able to solve?

Question

I am interested in using Shannon's entropy in combinatorics. It is often presented with a motivation of how much information can be passed, but assume I am not interested in that, I want to understand why it is useful as a tool to bound objects (with examples now).

Several examples that demonstrate that very nontrivial results follow from relatively entropy arguments are:

1. Bregman's inequality about permanents.
2. Whiteny's inequality about volume and its projections.
3. Shearer's lemma and numerous consequences; bounds on the number of independent sets in bipartite d-regular graph, number of homomorphisms to graph...
4. The largest size of an intersection unique family (see https://link.springer.com/article/10.1007/BF02579460 ).

If you could help me with the following I'd be very happy;

1. How would someone just interested in counting and bounding combinatorics arrive at entropy?

2. A common theme (noted by my proffessor when teaching about it) to some of the results are that original proofs used convexity arguments, how healthy is it to be think of entropy in combinatorics as a clean way to state convexity arguments and deriving nontrivial results by assigning weights to objects and bounding sums?

3. When can proofs be translated to entropy proofs? For instance I find it strange there is the $k-intersection$ proof with entropy, while I'm not aware of an entropy proof for sperner's theorem about antichains.

4. When are problems suspectible to entropy methods?

Cheers.

Answer 1

I'll only attempt to answer question 1.

Let's say you have 10 objects, divided into three blocks of respective sizes 2, 5 and 3. What's the probability that a random endomorphism of your set of objects preserves the blocks, i.e. sends each element of the set to an element of the same block? It's

$$ \frac{\text{number of block-preserving endos}}{\text{number of endos}} = \frac{2^2 5^5 3^3}{10^{10}} = \biggl(\frac{2}{10}\biggr)^2 \biggl(\frac{5}{10}\biggr)^5 \biggl(\frac{3}{10}\biggr)^3 $$

Now, the entropy of a finite probability distribution $p = (p_1, \ldots, p_n)$ is, by definition,

$$ H(p) = -\log\bigl(p_1^{p_1} \cdots p_n^{p_n}\bigr). $$

Associated with our set-up is the probability distribution $p = (2/10, 5/10, 3/10)$. The probability that a random endomorphism of our set preserves the blocks is, then, simply

$$ e^{-10H(p)}. $$

In particular, the answer only depends on the number of elements in the set and the entropy of $p$ — not on the block sizes themselves.

This is one way in which entropy arises naturally in elementary counting problems. It also shows that sometimes, it's the exponential of entropy that plays the more fundamental role.

Answer 2

Three tutorial lectures on entropy and counting by David Galvin (2014) provides an answer to Q1:

The key property of Shannon’s entropy that makes it useful as an enumeration tool is that over all random variables that take on at most $n$ values with positive probability, the ones with the largest entropy are those which are uniform on their ranges, and these random variables have entropy exactly $\log_2 n$. So if $C$ is a set, and $X$ is a uniformly randomly selected element of $C$, then anything that can be said about the entropy of $X$ immediately translates into something about $|C|$.

The notes contain an extensive bibliography of combinatorial problems that have been solved using entropy as an enumeration tool starting from Erdös & Rényi (1963) and including two applications to antichains in a Boolean lattice (in connection with Q3).

Concerning Q2, the role of entropy as a proxy for convexity has been explored in Forward and Reverse Entropy Power Inequalities in Convex Geometry (2016), as discussed here on MO by one of the authors.

Answer 3

Entropy arguments are part of the toolkit of the probabilistic method. So the first step in answering the question of how someone just interested in combinatorics might be led to entropy is to ask how they might be led to consider the probabilistic method. I'm assuming you already have some feeling for this—arguments that just require approximate counting rather than explicit enumeration are often susceptible to probabilistic methods.

Given this, the question becomes when entropy specifically might be a useful concept. The intuition I would offer is that entropy is likely to be a useful tool when there is a natural way to think of some random variables in your problem as yielding information about other random variables. For example if you look at Radhakrishnan's proof of Brégman's theorem, he sets up an appropriate sequence of random variables and estimates how much information you get at each step.

Now you might ask, what's the difference between two random variables being dependent, and one random variable yielding information about the other? Strictly speaking, there is no difference. However, sometimes you're not interested in the exact way that two random variables are correlated, and you just want a single number that estimates how much information you're getting. In that case, entropy is your friend.

As for convexity—the simplest and most useful bound for entropy is easily proved using a convexity argument. So any argument that relies chiefly on that bound will likely feel like a convexity argument. But I don't think the converse holds; convexity is a very general and powerful tool and my feeling is that one can't expect every convexity argument to be translatable into an entropy argument.

Answer 4

Disclaimer: I'm not an expert on entropy. But I think that it is just a tool that makes calculations a lot simpler, similarly to certain applications of Kolmogorov-complexity. I think the best is if you compare the extremely complicated proof of Dedekind's problem by Kleitman with the elegant solution by Kahn. The complicated way in which certain events influence each other is excellently captured by entropy. Of course, it is just another tool; sometimes it works, sometimes it doesn't simplify the calculations.

Answer 5

I wanted to share another answer, that I feel comfortable with after trying to look for examples and intuition.

We start with the following riddle:

Find the least $k(n)$ so that there are $k$ subsets $D_1,...,D_k$ of $[n]$ s.t $|D_1\cap A|,...,|D_k \cap A|$ uniquely determine $A$ for each $A\subset[n]$.

This is an interesting question (coming from- there are $n$ bits, at each turn you pick a subset and are told how many of them are turned on, but you ask the questions nonadaptively, and need to determine the bits).

An easy initial observation is this;

Each intersections has at most $n+1$ options, and so $(n+1)^k\geq 2^n$, so $k\geq n/log_2(n)$.

Another way to phrase this, is that we can encode $n$ bits using $k\cdot log_2(n+1)$. Entropy for me, is all about encoding things. Now here will come the twist of entropy, it is not about deterministically encoding things, but rather, encoding most of the things, that is, we want to be able to encode\decode a random message of the possible inputs (with the given distribution on it). This is formalized, and this is where the expression for entropy most naturally arises for me, in the theorem of Shannon:

https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem

I won't repeat it here, but the point is that we have $X_1,..,X_n$ iid in a probability space $W$. Given $w$ in our world, we define the random variable $Y(w)$ to be $P(w' s.t X_1(w')=X_1(w),X_2(w')=X_2(w)..)$. We can calculate the expectation, but we don't have any theorem to handle concentration of product. So we do the usual, we take $log$. From this and the large law of numbers we easily obtain the theorem. It is nice because some easy corollaries are: $H(X,Y)\leq H(X)+H(y)$, $H(uniform)$ is maximizes given size of range.

Back to the riddle, the point is that if we take a bunch copies of random $A$, if we insisted to deterministically encode each one, we'd get the same bound.

But there are $2$ excellent twists:

1. For uniform distribution, even though we now allow to encode only with h.p, it is still hard and demands many bits.

2. For other distributions, this "tensorization" made a difference, a formula we can calculate.

Indeed, we have $n=H(uniform A)=H(|D_1\cap A|,...,|D_k \cap A|)\leq \sum H(|D_i \cap A|)$. So we want to bound $H(|D_i \cap A|)$.

Now if we're brute, and just insist on deterministically encoding all possible values of $|D_i \cap A|$, we don't get any improvement, but the whole point is that we allow us to only do so with h.p.

Since we expect this thing to be concentrated around $|D_i|/2$ with an interval of around $~\sqrt(|D_i|)$ around, we need only ~$log(\sqrt|D_i|$ bits, which is about half our original! (i.e we got a bound of about $2n/log(n)$).

To summarize, the trick is to tensorize (maybe there is a slight connection to the proof of the crossing inequality) by allow a small degree of freemdom, which traps uniform the uniform distribution.