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

ขอบเขตเชอร์นอฟ (Chernoff bound) ตั้งตามชื่อของ เฮอร์มาน เชอร์นอฟ (Herman Chernoff) ในทฤษฎีความน่าจะเป็น จะเป็นกลุ่มของข้อความทางคณิตศาสตร์ที่ให้ขอบเขตบนของส่วนปลายของการกระจายความน่าจะเป็น ชื่อของอสมการนั้นตั้งเพื่อเป็นเกียรติแก่ เฮอร์แมน เชอร์นอฟ นักคณิตศาสตร์ สถิติ และฟิสิกส์ ชาวอเมริกัน ขอบเขตเชอร์นอฟใช้ข้อมูลจากโมเมนต์ทั้งหมดของตัวแปรสุ่ม ดังนั้นโดยทั่วไปแล้วจึงให้ขอบเขตที่กระชับกว่าอสมการของมาร์คอฟ (ในรูปพื้นฐาน) และอสมการของเชบิเชฟมาก
== รูปทั่วไป ==
ให้ X เป็นตัวแปรสุ่มใดๆ แล้ว
\Pr[X \geq a] \ \leq \ \inf_{t > 0} e^{-ta} \mathcal{M}_X(t)
โดยที่
\mathcal{M}_X(t)= \mathrm{E}[e^{tX}] \quad  คือ ฟังก์ชันกำเนิดโมเมนต์ (moment generating function)
=== การพิสูจน์ ===
สำหรับค่าคงที่บวก t \, ใดๆ e^{tx} \, เป็นฟังก์ชันเพิ่มที่มีค่าบวกเสมอ ดังนั้น X \geq a ก็ต่อเมื่อ e^{tX} \geq e^{ta}
เมื่อมอง e^{tX} \, เป็นตัวแปรสุ่มและใช้อสมการของมาร์คอฟ เราได้ว่า
\Pr[X \geq a] = \Pr[e^{tX} \geq e^{ta}] \leq \frac{\mathrm{E}[e^{tX}]}{e^{ta}} = e^{-ta}\mathcal{M}_X(t)
เนื่องจากข้อความข้างต้นเป็นจริงสำหรับทุกๆ จำนวนจริงบวก t \, มันจึงเป็นจริงสำหรับ t \, ที่ทำให้ e^{-ta}\mathcal{M}_X(t)\, มีค่าต่ำสุดด้วย เพราะฉะนั้น
\Pr[X \geq a] \leq \inf_{t > 0} e^{-ta}\mathcal{M}_X(t)
ตามต้องการ
== ขอบเขตเชอร์นอฟของการทดลองแบบปัวซอง ==
ในส่วนนี้จะกล่าวถึงการหาขอบเขตเชอร์นอฟในกรณีที่ที่ตัวแปรสุ่มอันเป็นผลบวกของการทดลองแบบปัวซองซึ่งเป็นอิสระแก่กัน กรณีพิเศษของขอบเขตเชอร์นอฟแบบนี้ถูกใช้อย่างแพร่หลายในการวิเคราะห์ขั้นตอนวิธีแบบสุ่ม โดยเฉพาะในการพิสูจน์ว่าขั้นตอนวิธีแบบสุ่มหนึ่งๆ จะทำงานได้ดีด้วยความน่าจะเป็นสูง สาเหตุที่ขอบเขตเชอร์นอฟเป็นเทคนิคที่เหมาะสมต่อการวิเคราะห์ขั้นตอนวิธีแบบสุ่มนั้น อาจเพราะว่า โดยทั่วไปเราสามารถมองขั้นตอนวิธีแบบสุ่มว่า เป็นขั้นตอนวิธีที่ใช้การโยนเหรียญที่เป็นอิสระต่อกันหลาย ๆ ครั้งในการตัดสินใจ
ขอบเขตของเชอร์นอฟในกรณีนี้นั้นไม่สมมาตร ดังนั้นในการใช้งานจะมีขอบเขตทั้งของ ส่วนปลายด้านบน ซึ่งจะใช้สำหรับกรณีที่ต้องการหาขอบเขตบนในกรณีที่ตัวแปรสุ่มมีค่ามากกว่าค่าคาดหมาย และ ส่วนปลายด้านล่าง ในกรณีที่พิจารณาเหตุการณ์ที่ตัวแปรสุ่มมีค่าน้อยกว่าค่าคาดหมาย
=== ใจความ ===
ให้ n \, เป็นจำนวนเต็มบวก และ X_i \, สำหรับจำนวน 1 \leq i \leq n เป็นการทดลองแบบปัวซองที่เป็นอิสระแก่กันโดยที่ \Pr[X_i = 1] = p_i และ 0  กำหนด X = \sum_{i=1}^n X_i และให้ \mu = \mathrm{E}[X]\, และ \delta \, เป็นจำนวนจริงใดๆ ที่มีค่ามากกว่า 0 แล้ว:
1. (ส่วนปลายด้านบน)
: \Pr[X > (1+\delta)\mu] 
2. (ส่วนปลายด้านล่าง) เมื่อ 0 
: \Pr[X > (1-\delta)\mu] 
=== การพิสูจน์ ===
เราเริ่มจากการพิสูจน์ส่วนปลายด้านบน จากรูปทั่วไป
\Pr[X > (1+\delta)\mu]  0} e^{-t(1+\delta)\mu}\mathcal{M}_X(t)
พิจารณา \mathcal{M}_X(t) = \mathrm{E}[e^{tX}] \, เราได้ว่า e^{tX} = e^{tX_1 + \cdots + tX_n} = \prod_{i=1}^n e^{tX_i} เนื่องจากตัวแปรสุ่ม X_1 \,, X_2 \,, \ldots, X_n \, เป็นอิสระแก่กัน เราได้ว่า
\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))
เพราะว่า 1+x  สำหรับจำนวนจริงบวก x \, ทุกจำนวน เราได้ว่า
\mathcal{M}_X(t) = \prod_{i=1}^n (1 + p_i(e^t - 1)) 
เนื่องจาก 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}\mathcal{M}_X(t) 
กำหนดฟังก์ชัน f(t) = e^{e^t - t\delta - t - 1}\, เราได้ว่า f'(t) =(e^t - \delta - 1)f(t)\,  และ f(t) = ((e^t - \delta - 1)^2 + e^t)f(t)\,
สมมติให้ f'(t) = 0\, เราได้ว่า t = \ln(1+\delta)\, และ f(t) = ((1+\delta)^2 + 1 + \delta)f(\ln(1+\delta)) > 0\, เพราะฉะนั้น f(t) \, จึงมีค่าต่ำสุดสัมบูรณ์ที่ t = \ln(1+\delta) \, เราจึงได้ว่า
\Pr[X > (1+\delta)\mu]  0} e^{-t(1+\delta)\mu}\mathcal{M}_X(t)  0} f(t)^\mu = f(\ln(1+\delta))^\mu = \left( \frac{e^\delta}{(1+\delta)^{1+\delta}} \right)^\mu
ตามต้องการ
สำหรับส่วนปลายด้านล่างนั้น เราเริ่มจากสังเกตว่า X  ก็ต่อเมื่อ -X > -(1-\delta)\mu \, เมื่อใช้รูปทั่วไปของขอบเขตเชอร์นอฟ ได้ว่า
\Pr[X  0} e^{(1-\delta)\mu}\mathrm{E}[e^{-tX}]
เมื่อใช้การให้เหตุผลแบบเดียวกับการพิสูจน์ส่วนปลายด้านบน เราได้ว่า
\Pr[X  0} \left( \frac{e^{e^{-t}-1}}{e^{-t(1-\delta)}} \right)^\mu
ค่าต่ำสุดของฟังก์ชันทางด้านขวามือของอสมการอยู่ที่ t = \ln(1/(1-\delta)) \, ฉะนั้น
\Pr[X 
ตามต้องการ
=== รูปแบบอื่น ๆ ===
รูปแบบทั้งสองข้างต้นเป็นรูปแบบที่ให้ขอบเขตที่แน่นที่สุดของขอบเขตเชอร์นอฟ อย่างไรก็ตาม รูปแบบทั้งสามแบบด้านล่างที่อาจมีเงื่อนไขเพิ่มเติม มักนำไปใช้ได้สะดวกกว่า
1. (ส่วนปลายด้านบน) ถ้า 0 
: \Pr[X > (1+\delta)\mu] 
และ สำหรับ \delta > 2e-1\,
: \Pr[X > (1+\delta)\mu] 
2. (ส่วนปลายด้านล่าง) ถ้า 0
: \Pr[X 
ทฤษฎีความน่าจะเป็น
อสมการ