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

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 )

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.