Post

Thomas Steinke@stein.ke

Etemadi's inequality saves you a union bound when bounding all the partial sums of a sequence of independent random variables. It's an intuitive result, but the proof is not. 🙃

Thomas Steinke@stein.ke

The Poisson summation formula is one of my favorite tricks. It seems magical, but the proof is quite simple:

Thomas Steinke@stein.ke

The square root can be uniformly approximated to error ε by a rational function of degree O(log²(1/ε)). This surprising, since a polynomial approximation (e.g. Taylor series) requires degree Ω(1/ε), so rational functions are exponentially better than polynomials.

Thomas Steinke@stein.ke

Theorem. The following are equivalent. The proof is left as an exercise for the reader.

Thomas Steinke@stein.ke

Fano's inequality says that, if two random variables are equal with high probability, then they have near-maximal mutual information. In particular, if X is uniform on {0,1}^d, then I(X;Y)≥P[Y=X]·d-1 Here's an extension to random variables that are only approximately equal.

Thomas Steinke@stein.ke

The variance of X~Binomial(n,p) is E[(X-np)^2] = np(1-p). More generally, the central moments are E[(X-np)^2k] = O(knp)^k.

Thomas Steinke@stein.ke

Bernstein's inequality gives concentration bounds for sums of bounded independent random variables. It takes the variance into account, so it can be tighter than Hoeffding's & Chernoff's bounds.

Thomas Steinke@stein.ke

Neat trick for bounding the maximum of independent Gaussians:

Thomas Steinke@stein.ke

It's a well-known fact™ that estimating the mean of a Bernoulli distribution from n independent samples must have mean squared error Ω(1/n). But it's surprisingly difficult to find a clean proof or citation for this fact. Here's my attempt. 😅