Chi-squared concentration inequality

ID: chi-squared-concentration-inequality

For and , the upper tail is at most above , and the lower tail is at most below . Indeed for . The Chernoff bound with proves the upper estimate. For the lower estimate, for , and optimization gives the result. The lower threshold can be negative; the chi-squared Chernoff lower-tail bound provides an always-positive alternative.

New to topics? Read the docs here!