Proof

Proof. For an independent Bernoulli sample, $\mathrm{Pr}(|\hat{p}-p|>u)\le 2e^{-2n{u}^2}$. One elementary proof bounds the centered log moment-generating function by $t^2/8$: its second derivative is a variance on an interval of length one and is at most $1/4$. Exponential Markov inequality and optimization prove the concentration estimate. Apply it to the two ensembles, take a union bound, and combine with Theorem thm:recordgap.