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

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

Binomial anti-concentration: P[ Binomial(n, k/n) = k ] ≥ Ω( 1 / √k )