Bounded Differences Inequality (aka Azuma-Hoeffding Inequality)

Name: Bounded Differences Inequality (aka Azuma-Hoeffding Inequality)
Uploaded: 2024-11-06T17:36:28Z
Duration: 19 min 47 s
Description: An important tail bound in probabilistic analysis. A Lipschitz function with independent random inputs is concentrated about its mean. Two applications: (1) the coupon collector problem; (2) the chromatic number of a random graph.

19:47

Up Next

Threshold for a Random Graph to Contain a Triangle

Continue

An important tail bound in probabilistic analysis. A Lipschitz function with independent random inputs is concentrated about its mean. Two applications: (1) the coupon collector problem; (2) the chromatic number of a random graph.