Đăng bởi tqlong on Tháng Sáu 19, 2009
Định lý (tổng xác suất – union bound): Nếu 
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.
Định lý (Markov): Với biến ngẫu nhiên 
không âm thì
![\displaystyle \mathrm{Pr}\{X\geq u\}\leq \frac{E[X]}{u}](http://s2.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7BX%5Cgeq+u%5C%7D%5Cleq+%5Cfrac%7BE%5BX%5D%7D%7Bu%7D&bg=fafcff&fg=2a2a2a&s=0 "\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](http://s3.wordpress.com/latex.php?latex=%5Cdisplaystyle+E%5BX%5D%3D%5Cint_0%5E%5Cinfty+xp%28x%29dx+%3D+%5Cint_0%5Eu+xp%28x%29dx%2B%5Cint_u%5E%5Cinfty+xp%28x%29+dx&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle E[X]=\int_0^\infty xp(x)dx = \int_0^u xp(x)dx+\int_u^\infty xp(x) dx")
Định lý (Chebyshev): Với biến ngẫu nhiên 
bất kì ta có
![\displaystyle \mathrm{Pr}\{|X-E[X]|\geq u\}\leq \frac{V[X]}{u^2}](http://s3.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7B%7CX-E%5BX%5D%7C%5Cgeq+u%5C%7D%5Cleq+%5Cfrac%7BV%5BX%5D%7D%7Bu%5E2%7D&bg=fafcff&fg=2a2a2a&s=0 "\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](http://s1.wordpress.com/latex.php?latex=%5Cdisplaystyle+%28X-E%5BX%5D%29%5E2&bg=fafcff&fg=2a2a2a&s=0 "\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}](http://s2.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7B%7CX-E%5BX%5D%7C%5Cgeq+u%5C%7D+%3D+%5Cmathrm%7BPr%7D%5C%7B%28X-E%5BX%5D%29%5E2%5Cgeq+u%5E2%5C%7D%5Cleq+%5Cfrac%7BE%5B%28X-E%5BX%5D%29%5E2%5D%7D%7Bu%5E2%7D%3D%5Cfrac%7BV%5BX%5D%7D%7Bu%5E2%7D&bg=fafcff&fg=2a2a2a&s=0 "\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}](http://s3.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7B%7CX-E%5BX%5D%7C%5Cgeq+u%5C%7D+%5Cleq+%5Cinf_%7Bq%3E0%7D%5Cfrac%7BE%5B%28X-E%5BX%5D%29%5Eq%5D%7D%7Bu%5Eq%7D&bg=fafcff&fg=2a2a2a&s=0 "\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 bất kì ta có
trong đó ![\displaystyle M_X(s)=E[e^{sX}]](http://s3.wordpress.com/latex.php?latex=%5Cdisplaystyle+M_X%28s%29%3DE%5Be%5E%7BsX%7D%5D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle M_X(s)=E[e^{sX}]")
là hàm sinh moment của .
Chứng minh: Áp dụng định lý Markov,với mọi 
, ta có
![\displaystyle \mathrm{Pr}\{X\geq u\}=\mathrm{Pr}\{e^{sX}\geq e^{su}\} \leq \frac{E[e^{sX}]}{e^{su}}](http://s3.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7BX%5Cgeq+u%5C%7D%3D%5Cmathrm%7BPr%7D%5C%7Be%5E%7BsX%7D%5Cgeq+e%5E%7Bsu%7D%5C%7D+%5Cleq+%5Cfrac%7BE%5Be%5E%7BsX%7D%5D%7D%7Be%5E%7Bsu%7D%7D&bg=fafcff&fg=2a2a2a&s=0 "\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 
là hàm lồi thì với biến ngẫu nhiên bất kì ta có
![\displaystyle E[f(X)]\geq f(E[X])](http://s3.wordpress.com/latex.php?latex=%5Cdisplaystyle+E%5Bf%28X%29%5D%5Cgeq+f%28E%5BX%5D%29&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle E[f(X)]\geq f(E[X])")
Chứng minh:
Đặt ![\displaystyle x_0 = E[X]](http://s1.wordpress.com/latex.php?latex=%5Cdisplaystyle+x_0+%3D+E%5BX%5D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle x_0 = E[X]")
, với hàm lồi 
ta có
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])](http://s1.wordpress.com/latex.php?latex=%5Cdisplaystyle+E%5Bf%28X%29%5D%5Cgeq%5Cunderbrace%7Bf%28x_0%29%7D_%7B%3Df%28E%5BX%5D%29%7D+%2Bf%27%28x_0%29%5Cunderbrace%7B%28E%5BX%5D-x_0%29%7D_%7B%3D0%7D%3Df%28E%5BX%5D%29&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle E[f(X)]\geq\underbrace{f(x_0)}_{=f(E[X])} +f'(x_0)\underbrace{(E[X]-x_0)}_{=0}=f(E[X])")
Bài viết này được đăng vào Tháng Sáu 19, 2009 lúc 8:00 sáng và tập tin được lưu ở Công cụ xác suất.
Tagged: Chebyshev, Chernoff, Jensen, Markov, Union bound. Bạn có thể theo dõi các phản hồi của bài viết này thông qua RSS 2.0 dòng thông tin.
Bạn có thể bỏ qua phần còn lại và gửi phản hồi. Ping đã bị khóa.
Huy Dinh đã nói
May cai nay hay nha !
U*’ng dung de lam gi the dai ca Long ?
tqlong đã nói
Công cụ xác suất mà :-)
H.T.D. đã nói
Long,
Co ket qua nao lien quan den how tight are those bounds? (or was any of them proven to be strict bound ?).
Thanks
tqlong đã nói
Các bất đẳng thức này chặt vì có phân bố để dấu bằng xảy ra.