Complex Network 분석(2. Chernoff Bound)

강의주소

Markov Inequality

음이 아닌 R.V. 의 a 보다 큰 구간의 확률과 평균과의 관계

Chebyshev Inequality

편차가 a 보다 큰 구간의 확률과 분산과의 관계

Chernoff Bound

i.i.d R.V.의 n개의 합의 확률의 유계

(1) Gaussian distribution, (2) Exponential distribution, (3) Poisson distribution, (4) Bernoulli distribution 의 Chernoff Bound

Chernoff Bound(Poisson Trials)

independent poisson trials 의 n개의 합의 확률의 유계

(1) $\delta \in (0,1]$ 일때, (2) $\delta > 5$ 일때