Hoeffding lower-tail bound for Hamming balls
ID: hoeffding-lower-tail-bound-for-hamming-balls
For a uniform vertex of the Hamming cube, distance from a fixed vertex is the sum of independent Bernoulli random variables with parameter . The lower-tail Hoeffding inequality implies that the fraction of vertices at distance at most , , is at most . Strict-radius balls satisfy the same upper bound.
New to topics? Read the docs here!