This note is about a well-known result called the “diffusion lemma”, which establishes (with high probability) the existence of a desired structure in a random set. Diffusion lemmas have been central to two recent well-known results. (b) A proof of the fractional Kahn-Kalai conjecture by Frankston, Kahn, Narayanan, and Park (2019). The lemma was first proven (and later refined) by a delicate enumeration argument, but by Shannon’s noiseless coding theorem (Rao, 2019) and Shannon’s manipulation of entropy bounds (Tao, 2020), another was also given.
In this note, we present a new proof of the diffusion lemma, taking advantage of explicit recasting of the proof in the language of Bayesian statistical inference. From this point of view, we show that the proof proceeds in a simple and principled probabilistic way, leading to a truncated second moment computation that ends the proof. This proof can also be viewed as a demonstration of the “planting trick” introduced by Achlioptas and Coga-Oghlan (2008) in their study of random constraint satisfaction problems.
