Post

I'm going to slowly repost my math notes from the other site🐦 here🦋; it's the only thing I posted over there that I think may have some long-term value & worth not deleting. These started out as notes for myself, but people seem to appreciate them. 😅 I'll keep track of all of them in this thread.

Thomas Steinke

@stein.ke

bsky.app/profile/tste...

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. 🙃

14/11/24, 5:22 pm0 reposts6 likes

Thomas Steinke

@stein.ke

17 Nov 2024

bsky.app/profile/stei...

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

19 Nov 2024

bsky.app/profile/stei...

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

14 Dec 2024

bsky.app/profile/stei...

Thomas Steinke@stein.ke

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

Thomas Steinke

@stein.ke

14 Dec 2024

bsky.app/profile/stei...

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.