ขอบเขตเชอร์นอฟ
จากวิกิพีเดีย สารานุกรมเสรี
ในทฤษฎีความน่าจะเป็น ขอบเขตเชอร์นอฟ เป็นกลุ่มของข้อความทางคณิตศาสตร์ที่ให้ขอบเขตบนของส่วนปลายของการกระจายความน่าจะเป็น ชื่อของอสมการนั้นตั้งเพื่อเป็นเกียรติแก่ เฮอร์แมน เชอร์นอฟ นักคณิตศาสตร์ สถิติ และฟิสิกส์ ชาวอเมริกัน ขอบเขตเชอร์นอฟใช้ข้อมูลจากโมเมนต์ทั้งหมดของตัวแปรสุ่ม ดังนั้นโดยทั่วไปแล้วจึงให้ขอบเขตที่กระชับกว่าอสมการของมาร์คอฟ (ในรูปพื้นฐาน) และอสมการของเชบิเชฟมาก
สารบัญ |
[แก้] รูปทั่วไป
ให้ X เป็นตัวแปรสุ่มใดๆ แล้ว
โดยที่
คือ ฟังก์ชันกำเนิดโมเมนต์ (moment generating function)
[แก้] การพิสูจน์
สำหรับค่าคงที่บวก
ใดๆ
เป็นฟังก์ชันเพิ่มที่มีค่าบวกเสมอ ดังนั้น
ก็ต่อเมื่อ 
เมื่อมอง
เป็นตัวแปรสุ่มและใช้อสมการของมาร์คอฟ เราได้ว่า
เนื่องจากข้อความข้างต้นเป็นจริงสำหรับทุกๆ จำนวนจริงบวก
มันจึงเป็นจริงสำหรับ
ที่ทำให้
มีค่าต่ำสุดด้วย เพราะฉะนั้น
ตามต้องการ
[แก้] ขอบเขตเชอร์นอฟของการทดลองแบบปัวซอง
ในส่วนนี้จะกล่าวถึงการหาขอบเขตเชอร์นอฟในกรณีที่ที่ตัวแปรสุ่มอันเป็นผลบวกของการทดลองแบบปัวซองซึ่งเป็นอิสระแก่กัน กรณีพิเศษของขอบเขตเชอร์นอฟแบบนี้ถูกใช้อย่างแพร่หลายในการวิเคราะห์อัลกอริทึมแบบสุ่ม โดยเฉพาะในการพิสูจน์ว่าอัลกอริทึมแบบสุ่มหนึ่งๆ จะทำงานได้ดีด้วยความน่าจะเป็นสูง สาเหตุที่ขอบเขตเชอร์นอฟเป็นเทคนิคที่เหมาะสมต่อการวิเคราะห์อัลกอริทึมแบบสุ่มนั้น อาจเพราะว่า โดยทั่วไปเราสามารถมองอัลกอริทึมแบบสุ่มว่า เป็นอัลกอริทึมที่ใช้การโยนเหรียญที่เป็นอิสระต่อกันหลาย ๆ ครั้งในการตัดสินใจ
ขอบเขตของเชอร์นอฟในกรณีนี้นั้นไม่สมมาตร ดังนั้นในการใช้งานจะมีขอบเขตทั้งของ ส่วนปลายด้านบน ซึ่งจะใช้สำหรับกรณีที่ต้องการหาขอบเขตบนในกรณีที่ตัวแปรสุ่มมีค่ามากกว่าค่าคาดหมาย และ ส่วนปลายด้านล่าง ในกรณีที่พิจารณาเหตุการณ์ที่ตัวแปรสุ่มมีค่าน้อยกว่าค่าคาดหมาย
[แก้] ใจความ
ให้
เป็นจำนวนเต็มบวก และ
สำหรับจำนวน
เป็นการทดลองแบบปัวซองที่เป็นอิสระแก่กันโดยที่
และ
กำหนด
และให้
และ
เป็นจำนวนจริงใดๆ ที่มีค่ามากกว่า 0 แล้ว:
1. (ส่วนปลายด้านบน)
2. (ส่วนปลายด้านล่าง) เมื่อ 
[แก้] การพิสูจน์
เราเริ่มจากการพิสูจน์ส่วนปลายด้านบน จากรูปทั่วไป
พิจารณา
เราได้ว่า
เนื่องจากตัวแปรสุ่ม
,
,
,
เป็นอิสระแก่กัน เราได้ว่า
เพราะว่า
สำหรับจำนวนจริงบวก
ทุกจำนวน เราได้ว่า
เนื่องจาก
ดังนั้น
กำหนดฟังก์ชัน
เราได้ว่า
และ 
สมมติให้
เราได้ว่า
และ
เพราะฉะนั้น
จึงมีค่าต่ำสุดสัมบูรณ์ที่
เราจึงได้ว่า
ตามต้องการ
สำหรับส่วนปลายด้านล่างนั้น เราเริ่มจากสังเกตว่า
ก็ต่อเมื่อ
เมื่อใช้รูปทั่วไปของขอบเขตเชอร์นอฟ ได้ว่า
เมื่อใช้การให้เหตุผลแบบเดียวกับการพิสูจน์ส่วนปลายด้านบน เราได้ว่า
ค่าต่ำสุดของฟังก์ชันทางด้านขวามือของอสมการอยู่ที่
ฉะนั้น
ตามต้องการ
[แก้] รูปแบบอื่น ๆ
รูปแบบทั้งสองข้างต้นเป็นรูปแบบที่ให้ขอบเขตที่แน่นที่สุดของขอบเขตเชอร์นอฟ อย่างไรก็ตาม รูปแบบทั้งสามแบบด้านล่างที่อาจมีเงื่อนไขเพิ่มเติม มักนำไปใช้ได้สะดวกกว่า
1. (ส่วนปลายด้านบน) ถ้า 
และ สำหรับ 
2. (ส่วนปลายด้านล่าง) ถ้า 
![\Pr[X \geq a] \ \leq \ \inf_{t > 0} e^{-ta} \mathcal{M}_X(t)](../../../math/a/3/6/a367690b7ad26afe28cae5ef8b546406.png)
![\Pr[X \geq a] = \Pr[e^{tX} \geq e^{ta}] \leq \frac{\mathrm{E}[e^{tX}]}{e^{ta}} = e^{-ta}\mathcal{M}_X(t)](../../../math/8/7/8/8781469076a7e423834fb8e380b09b81.png)
![\Pr[X \geq a] \leq \inf_{t > 0} e^{-ta}\mathcal{M}_X(t)](../../../math/6/1/c/61c17f527094d025721bad914a36fafd.png)
![\Pr[X > (1+\delta)\mu] < \left( \frac{e^\delta}{(1+\delta)^{1+\delta}} \right)^\mu](../../../math/6/1/2/612fceb2e931d590084fe9091e4de60a.png)
![\Pr[X > (1-\delta)\mu] < \left( \frac{e^\delta}{(1-\delta)^{1-\delta}} \right)^\mu](../../../math/f/3/a/f3aa62003c0af8e63a75c70ea5edd084.png)
![\Pr[X > (1+\delta)\mu] < \inf_{t > 0} e^{-t(1+\delta)\mu}\mathcal{M}_X(t)](../../../math/5/4/b/54b25b1d1d9f309c04afabe77d3c85ce.png)
![\mathcal{M}_X(t) = \mathrm{E}[\prod_{i=1}^n e^{tX_i}] = \prod_{i=1}^n \mathrm{E}[e^{tX_i}] = \prod_{i=1}^n (p_ie^t + (1-p_i)) = \prod_{i=1}^n (1 + p_i(e^t - 1))](../../../math/4/8/e/48e6db2e17b05ec2c7bfd876f8e56203.png)


![\Pr[X > (1+\delta)\mu] < \inf_{t > 0} e^{-t(1+\delta)\mu}\mathcal{M}_X(t) < \inf_{t > 0} f(t)^\mu = f(\ln(1+\delta))^\mu = \left( \frac{e^\delta}{(1+\delta)^{1+\delta}} \right)^\mu](../../../math/c/6/c/c6c6d20acf792184450d867a83a37856.png)
![\Pr[X < (1-\delta)\mu] < \inf_{t > 0} e^{(1-\delta)\mu}\mathrm{E}[e^{-tX}]](../../../math/4/3/a/43a97dfbb87b14f9a95b7dfaf5c4371a.png)
![\Pr[X < (1-\delta)\mu] < \inf_{t > 0} \left( \frac{e^{e^{-t}-1}}{e^{-t(1-\delta)}} \right)^\mu](../../../math/b/a/d/bad3c02453bf578f7209dc9f1727904b.png)
![\Pr[X < (1-\delta)\mu] < \left( \frac{e^\delta}{(1-\delta)^{1-\delta}} \right)^\mu](../../../math/f/a/f/fafabcc442239ab87b8773823662c8f0.png)
![\Pr[X > (1+\delta)\mu] < e^{-\mu\delta^2/4}](../../../math/7/0/7/7079bccd3dd56b2dda99374d7978f0f8.png)
![\Pr[X > (1+\delta)\mu] < 2^{-(1+\delta)\mu}](../../../math/c/3/a/c3a07b58cd3af6607608c1951ec5dc89.png)
![\Pr[X < (1-\delta)\mu] < e^{-\mu\delta^2/2}](../../../math/c/6/9/c69f97ac79306b04a7692617ae91c5db.png)

