Chernoff bound

For every

λ > 0

, Markov inequality applied to

e^{λ X}

gives

P (X \geq t) \leq e^{- λ t} E [e^{λ X}] .

Optimizing over

λ

gives the Chernoff bound in terms of the moment-generating function of

X

.

Table of contents
- Entrywise concentration of a Gaussian Gram matrix Chernoff bound

Entrywise concentration of a Gaussian Gram matrix

For a

d \times p

matrix of independent standard normal entries and

0 < t < 1

, diagonal entries of

A^{T} A / d - I

have two-sided tails bounded by

2 e^{- d t^{2} /8}

, while off-diagonal entries have tails bounded by

2 e^{- d t^{2} /4}

. A union bound over

p

diagonal entries and

p (p - 1) /2

distinct off-diagonal entries controls their common entrywise maximum norm.

 Ancestors (7)

 Incoming links (68)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Chernoff bound by

Wikipedia Bot  1

The Chernoff bound is a probabilistic technique used to provide exponentially decreasing bounds on the tail distributions of sums of independent random variables. It is particularly useful in the analysis of algorithms and in fields like theoretical computer science, statistics, and information theory. ### Overview: The Chernoff bound gives us a way to quantify how unlikely it is for the sum of independent random variables to deviate significantly from its expected value.

 Read the full article

  See all articles in the same topic Create my own version