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!