The previous talk in the series is here. The next talk in the series is here.
A useful rule that is satisfied by entropy is that if X1,…,Xn are random variables, then H[X1,…,Xn] is at most H[X1]+…+H[Xn]. Shearer’s lemma is a generalization of this, where one compares H[X1,…,Xn] by a suitable weighted average of joint entropies of the form H[Xi : i ∈ S] where S is a subset of {1,2,…,n}. It has several applications, a couple of which will be presented in the next video. A quick comment here is that I forgot to give the straightforward explanation of why Shearer’s lemma is a generalization of subadditivity: subadditivity is equivalent to the case where S is a random singleton (which means we can take μ = 1/n and deduce that H[X]/n is at most the average of the H[Xi]). We start with an introduction and subadditivity of entropy, then give the statement and proof of Shearer’s lemma.
This video was produced by Tim Gowers as part of his Part III course at the University of Cambridge. Printed notes for this course are available here.