ขอบเขตเชอร์นอฟ

แม่แบบ:ต้องการอ้างอิง ขอบเขตเชอร์นอฟ (แม่แบบ:Langx) ตั้งตามชื่อของ เฮอร์มาน เชอร์นอฟ (Herman Chernoff) ในทฤษฎีความน่าจะเป็น จะเป็นกลุ่มของข้อความทางคณิตศาสตร์ที่ให้ขอบเขตบนของส่วนปลายของการกระจายความน่าจะเป็น ชื่อของอสมการนั้นตั้งเพื่อเป็นเกียรติแก่ เฮอร์แมน เชอร์นอฟ นักคณิตศาสตร์ สถิติ และฟิสิกส์ ชาวอเมริกัน ขอบเขตเชอร์นอฟใช้ข้อมูลจากโมเมนต์ทั้งหมดของตัวแปรสุ่ม ดังนั้นโดยทั่วไปแล้วจึงให้ขอบเขตที่กระชับกว่าอสมการของมาร์คอฟ (ในรูปพื้นฐาน) และอสมการของเชบิเชฟมาก

รูปทั่วไป

ให้ $X$ เป็นตัวแปรสุ่มใด ๆ แล้ว

$\mathrm{Pr}[X\ge a]\le \underset{t>0}{\inf }{e}^{-ta}{ℳ}_X(t)$

โดยที่

${ℳ}_X(t)=\mathrm{E}[e^{tX}]$ คือ ฟังก์ชันก่อกำเนิดโมเมนต์ (moment generating function)

การพิสูจน์

สำหรับค่าคงที่บวก $t$ ใด ๆ $e^{tx}$ เป็นฟังก์ชันเพิ่มที่มีค่าบวกเสมอ ดังนั้น $X\ge a$ ก็ต่อเมื่อ $e^{tX}\ge e^{ta}$

เมื่อมอง $e^{tX}$ เป็นตัวแปรสุ่มและใช้อสมการของมาร์คอฟ เราได้ว่า

$\mathrm{Pr}[X\ge a]=\mathrm{Pr}[e^{tX}\ge e^{ta}]\le \frac{\mathrm{E}[e^{tX}]}{e^{ta}}=e^{-ta}{ℳ}_X(t)$

เนื่องจากข้อความข้างต้นเป็นจริงสำหรับทุก ๆ จำนวนจริงบวก $t$ มันจึงเป็นจริงสำหรับ $t$ ที่ทำให้ $e^{-ta}{ℳ}_X(t)$ มีค่าต่ำสุดด้วย เพราะฉะนั้น

$\mathrm{Pr}[X\ge a]\le \underset{t>0}{\inf }{e}^{-ta}{ℳ}_X(t)$

ตามต้องการ

ขอบเขตเชอร์นอฟของการทดลองแบบปัวซง

ในส่วนนี้จะกล่าวถึงการหาขอบเขตเชอร์นอฟในกรณีที่ที่ตัวแปรสุ่มอันเป็นผลบวกของการทดลองแบบปัวซงซึ่งเป็นอิสระแก่กัน กรณีพิเศษของขอบเขตเชอร์นอฟแบบนี้ถูกใช้อย่างแพร่หลายในการวิเคราะห์ขั้นตอนวิธีแบบสุ่ม โดยเฉพาะในการพิสูจน์ว่าขั้นตอนวิธีแบบสุ่มหนึ่ง ๆ จะทำงานได้ดีด้วยความน่าจะเป็นสูง สาเหตุที่ขอบเขตเชอร์นอฟเป็นเทคนิคที่เหมาะสมต่อการวิเคราะห์ขั้นตอนวิธีแบบสุ่มนั้น อาจเพราะว่า โดยทั่วไปเราสามารถมองขั้นตอนวิธีแบบสุ่มว่า เป็นขั้นตอนวิธีที่ใช้การโยนเหรียญที่เป็นอิสระต่อกันหลาย ๆ ครั้งในการตัดสินใจ

ขอบเขตของเชอร์นอฟในกรณีนี้นั้นไม่สมมาตร ดังนั้นในการใช้งานจะมีขอบเขตทั้งของ ส่วนปลายด้านบน ซึ่งจะใช้สำหรับกรณีที่ต้องการหาขอบเขตบนในกรณีที่ตัวแปรสุ่มมีค่ามากกว่าค่าคาดหมาย และ ส่วนปลายด้านล่าง ในกรณีที่พิจารณาเหตุการณ์ที่ตัวแปรสุ่มมีค่าน้อยกว่าค่าคาดหมาย

ใจความ

ให้ $n$ เป็นจำนวนเต็มบวก และ $X_i$ สำหรับจำนวน $1\le i\le n$ เป็นการทดลองแบบปัวซงที่เป็นอิสระแก่กันโดยที่ $\mathrm{Pr}[X_i=1]=p_i$ และ $0<p_i<1$ กำหนด $X=\sum _{i=1}^n{X}_i$ และให้ $\mu =\mathrm{E}[X]$ และ $\delta$ เป็นจำนวนจริงใด ๆ ที่มีค่ามากกว่า 0 แล้ว:

1. (ส่วนปลายด้านบน)

$\mathrm{Pr}[X>(1+\delta )\mu ]<{\left(\frac{e^{\delta }}{(1+\delta {)}^{1+\delta }}\right)}^{\mu }$

2. (ส่วนปลายด้านล่าง) เมื่อ $0<\delta \le 1$

$\mathrm{Pr}[X>(1-\delta )\mu ]<{\left(\frac{e^{\delta }}{(1-\delta {)}^{1-\delta }}\right)}^{\mu }$

การพิสูจน์

เราเริ่มจากการพิสูจน์ส่วนปลายด้านบน จากรูปทั่วไป

$\mathrm{Pr}[X>(1+\delta )\mu ]<\underset{t>0}{\inf }{e}^{-t(1+\delta )\mu }{ℳ}_X(t)$

พิจารณา ${ℳ}_X(t)=\mathrm{E}[e^{tX}]$ เราได้ว่า $e^{tX}=e^{t{X}_1+\cdots +t{X}_n}=\prod _{i=1}^n{e}^{t{X}_i}$ เนื่องจากตัวแปรสุ่ม $X_1$, $X_2$, $\dots$, $X_n$ เป็นอิสระแก่กัน เราได้ว่า

${ℳ}_X(t)=\mathrm{E}[\prod _{i=1}^n{e}^{t{X}_i}]=\prod _{i=1}^n\mathrm{E}[e^{t{X}_i}]=\prod _{i=1}^n(p_i{e}^t+(1-p_i))=\prod _{i=1}^n(1+p_i(e^t-1))$

เพราะว่า $1+x<e^x$ สำหรับจำนวนจริงบวก $x$ ทุกจำนวน เราได้ว่า

${ℳ}_X(t)=\prod _{i=1}^n(1+p_i(e^t-1))<\prod _{i=1}^n{e}^{p_i(e^t-1)}=e^{(e^t-1)(p_1+\cdots +p_n)}=e^{(e^t-1)\mu }$

เนื่องจาก $p_1+\cdots +p_n=\mathrm{E}[X_1]+\cdots +\mathrm{E}[X_n]=\mathrm{E}[X_1+\cdots +X_n]=\mathrm{E}[X]=\mu$ ดังนั้น

$e^{-t(1+\delta )\mu }{ℳ}_X(t)<\frac{e^{(e^t-1)\mu }}{e^{t(1+\delta )\mu }}={\left(\frac{e^{e^t-1}}{e^{t(1+\delta )}}\right)}^{\mu }=(e^{e^t-t\delta -t-1}{)}^{\mu }$

กำหนดฟังก์ชัน $f(t)=e^{e^t-t\delta -t-1}$ เราได้ว่า $f^{\prime }(t)=(e^t-\delta -1)f(t)$ และ $f^{″}(t)=((e^t-\delta -1{)}^2+e^t)f(t)$

สมมติให้ $f^{\prime }(t)=0$ เราได้ว่า $t=\ln (1+\delta )$ และ $f^{″}(t)=((1+\delta {)}^2+1+\delta )f(\ln (1+\delta ))>0$ เพราะฉะนั้น $f(t)$ จึงมีค่าต่ำสุดสัมบูรณ์ที่ $t=\ln (1+\delta )$ เราจึงได้ว่า

$\mathrm{Pr}[X>(1+\delta )\mu ]<\underset{t>0}{\inf }{e}^{-t(1+\delta )\mu }{ℳ}_X(t)<\underset{t>0}{\inf }f(t{)}^{\mu }=f(\ln (1+\delta ){)}^{\mu }={\left(\frac{e^{\delta }}{(1+\delta {)}^{1+\delta }}\right)}^{\mu }$

ตามต้องการ

สำหรับส่วนปลายด้านล่างนั้น เราเริ่มจากสังเกตว่า $X<(1-\delta )\mu$ ก็ต่อเมื่อ $-X>-(1-\delta )\mu$ เมื่อใช้รูปทั่วไปของขอบเขตเชอร์นอฟ ได้ว่า

$\mathrm{Pr}[X<(1-\delta )\mu ]<\underset{t>0}{\inf }{e}^{(1-\delta )\mu }\mathrm{E}[e^{-tX}]$

เมื่อใช้การให้เหตุผลแบบเดียวกับการพิสูจน์ส่วนปลายด้านบน เราได้ว่า

$\mathrm{Pr}[X<(1-\delta )\mu ]<\underset{t>0}{\inf }{\left(\frac{e^{e^{-t}-1}}{e^{-t(1-\delta )}}\right)}^{\mu }$

ค่าต่ำสุดของฟังก์ชันทางด้านขวามือของอสมการอยู่ที่ $t=\ln (1/(1-\delta ))$ ฉะนั้น

$\mathrm{Pr}[X<(1-\delta )\mu ]<{\left(\frac{e^{\delta }}{(1-\delta {)}^{1-\delta }}\right)}^{\mu }$

ตามต้องการ

รูปแบบอื่น ๆ

รูปแบบทั้งสองข้างต้นเป็นรูปแบบที่ให้ขอบเขตที่แน่นที่สุดของขอบเขตเชอร์นอฟ อย่างไรก็ตาม รูปแบบทั้งสามแบบด้านล่างที่อาจมีเงื่อนไขเพิ่มเติม มักนำไปใช้ได้สะดวกกว่า

1. (ส่วนปลายด้านบน) ถ้า $0<t<2e-1$

$\mathrm{Pr}[X>(1+\delta )\mu ]<e^{-\mu {\delta }^2/4}$

และ สำหรับ $\delta >2e-1$

$\mathrm{Pr}[X>(1+\delta )\mu ]<2^{-(1+\delta )\mu }$

2. (ส่วนปลายด้านล่าง) ถ้า $0<\delta \le 1$

$\mathrm{Pr}[X<(1-\delta )\mu ]<e^{-\mu {\delta }^2/2}$