CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Bất đẳng thức xác suất (1) – Markov, Chebyshev, Chernoff, Jensen inequalities

Posted by Trần Quốc Long on Tháng Sáu 19, 2009

Định lý (tổng xác suất – union bound): Nếu \displaystyle A_1,\ldots, A_n,\ldots là các sự kiện thì xác suất để ít nhất một sự kiện xảy ra nhỏ hơn tổng xác suất của tất cả các sự kiện.

\displaystyle \mathrm{Pr}\{ \exists i: A_i \textrm{ happens }\}=\mathrm{Pr}\{\cup_{i=1}^\infty A_i\} \leq \sum_{i=1}^\infty\mathrm{Pr}\{A_i\}

Định lý (Markov): Với biến ngẫu nhiên \displaystyle X không âm thì

\displaystyle \mathrm{Pr}\{X\geq u\}\leq \frac{E[X]}{u}

Chứng minh:

\displaystyle E[X]=\int_0^\infty xp(x)dx = \int_0^u xp(x)dx+\int_u^\infty xp(x) dx

\displaystyle \geq \int_u^\infty xp(x) dx\geq u\int_u^\infty p(x)dx = u \mathrm{Pr}\{X\geq u\}

Định lý (Chebyshev): Với biến ngẫu nhiên \displaystyle X bất kì ta có

\displaystyle \mathrm{Pr}\{|X-E[X]|\geq u\}\leq \frac{V[X]}{u^2}

Chứng minh: Do biến \displaystyle (X-E[X])^2 không âm, áp dụng bất đẳng thức Markov, ta có

\displaystyle \mathrm{Pr}\{|X-E[X]|\geq u\} = \mathrm{Pr}\{(X-E[X])^2\geq u^2\}\leq \frac{E[(X-E[X])^2]}{u^2}=\frac{V[X]}{u^2}

Tổng quát hơn, ta có

\displaystyle \mathrm{Pr}\{|X-E[X]|\geq u\} \leq \inf_{q>0}\frac{E[(X-E[X])^q]}{u^q}

Định lý (Chernoff): Với biến ngẫu nhiên \displaystyle X bất kì ta có

\displaystyle \mathrm{Pr}\{X\geq u\}\leq \inf_s e^{-su} M_X(s)

trong đó \displaystyle M_X(s)=E[e^{sX}]hàm sinh moment của \displaystyle X.

Chứng minh: Áp dụng định lý Markov,với mọi \displaystyle s\in \mathbb{R}, ta có

\displaystyle \mathrm{Pr}\{X\geq u\}=\mathrm{Pr}\{e^{sX}\geq e^{su}\} \leq \frac{E[e^{sX}]}{e^{su}}

Định lý (Jensen): Nếu hàm \displaystyle f(x) là hàm lồi thì với biến ngẫu nhiên \displaystyle X bất kì ta có

\displaystyle E[f(X)]\geq f(E[X])

Chứng minh:

Đặt \displaystyle x_0 = E[X], với hàm lồi \displaystyle f(x) ta có

\displaystyle f(x)\geq f(x_0)+f'(x_0)(x-x_0),\forall x

Lấy kì vọng hai vế ta có

\displaystyle E[f(X)]\geq\underbrace{f(x_0)}_{=f(E[X])} +f'(x_0)\underbrace{(E[X]-x_0)}_{=0}=f(E[X])

9 phản hồi to “Bất đẳng thức xác suất (1) – Markov, Chebyshev, Chernoff, Jensen inequalities”

  1. Huy Dinh said

    May cai nay hay nha !
    U*’ng dung de lam gi the dai ca Long ?

  2. H.T.D. said

    Long,

    Co ket qua nao lien quan den how tight are those bounds? (or was any of them proven to be strict bound ?).

    Thanks

  3. huy said

    Anh cho em hoi vi sao EX= (trong chung minh bat dang thuc markov), vi sao ta co the bo duoc tich phan tu -vo cung den 0 cua xf(x) a?

  4. Dung said

    Anh xem lại chứng minh BDT Jensen vì không phải mọi hàm lồi đều tồn tại đạo hàm mà chỉ tồn tại đạo hàm trái và đạo hàm phải thôi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: