ดูต้นฉบับสำหรับ ขอบเขตเชอร์นอฟ

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

== รูปทั่วไป ==
ให้ <math>X</math> เป็นตัวแปรสุ่มใด ๆ แล้ว
: <math>\Pr[X \geq a] \ \leq \ \inf_{t > 0} e^{-ta} \mathcal{M}_X(t)</math>
โดยที่
: <math>\mathcal{M}_X(t)= \mathrm{E}[e^{tX}] \quad </math> คือ [[ฟังก์ชันก่อกำเนิดโมเมนต์]] (moment generating function)

=== การพิสูจน์ ===

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

เมื่อมอง <math>e^{tX} \,</math> เป็นตัวแปรสุ่มและใช้อสมการของมาร์คอฟ เราได้ว่า
: <math>\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>
เนื่องจากข้อความข้างต้นเป็นจริงสำหรับทุก ๆ จำนวนจริงบวก <math>t \,</math> มันจึงเป็นจริงสำหรับ <math>t \,</math> ที่ทำให้ <math>e^{-ta}\mathcal{M}_X(t)\,</math> มีค่าต่ำสุดด้วย เพราะฉะนั้น
: <math>\Pr[X \geq a] \leq \inf_{t > 0} e^{-ta}\mathcal{M}_X(t)</math>
ตามต้องการ

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

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

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

1. (ส่วนปลายด้านบน)
:: <math>\Pr[X > (1+\delta)\mu] < \left( \frac{e^\delta}{(1+\delta)^{1+\delta}} \right)^\mu</math>
2. (ส่วนปลายด้านล่าง) เมื่อ <math>0 < \delta \leq 1</math>
:: <math>\Pr[X > (1-\delta)\mu] < \left( \frac{e^\delta}{(1-\delta)^{1-\delta}} \right)^\mu</math>

=== การพิสูจน์ ===
เราเริ่มจากการพิสูจน์ส่วนปลายด้านบน จากรูปทั่วไป
: <math>\Pr[X > (1+\delta)\mu] < \inf_{t > 0} e^{-t(1+\delta)\mu}\mathcal{M}_X(t)</math>
พิจารณา <math>\mathcal{M}_X(t) = \mathrm{E}[e^{tX}] \,</math> เราได้ว่า <math>e^{tX} = e^{tX_1 + \cdots + tX_n} = \prod_{i=1}^n e^{tX_i}</math> เนื่องจากตัวแปรสุ่ม <math>X_1 \,</math>, <math>X_2 \,</math>, <math>\ldots</math>, <math>X_n \,</math> เป็นอิสระแก่กัน เราได้ว่า
: <math>\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>
เพราะว่า <math>1+x < e^x \,</math> สำหรับจำนวนจริงบวก <math>x \,</math> ทุกจำนวน เราได้ว่า
: <math>\mathcal{M}_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}</math>
เนื่องจาก <math>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</math> ดังนั้น
: <math>e^{-t(1+\delta)\mu}\mathcal{M}_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</math>

กำหนดฟังก์ชัน <math>f(t) = e^{e^t - t\delta - t - 1}\,</math> เราได้ว่า <math>f'(t) =(e^t - \delta - 1)f(t)\, </math> และ <math>f''(t) = ((e^t - \delta - 1)^2 + e^t)f(t)\,</math>

สมมติให้ <math>f'(t) = 0\,</math> เราได้ว่า <math>t = \ln(1+\delta)\,</math> และ <math>f''(t) = ((1+\delta)^2 + 1 + \delta)f(\ln(1+\delta)) > 0\,</math> เพราะฉะนั้น <math>f(t) \,</math> จึงมี[[ค่าต่ำสุดสัมบูรณ์]]ที่ <math>t = \ln(1+\delta) \,</math> เราจึงได้ว่า
: <math>\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>
ตามต้องการ

สำหรับส่วนปลายด้านล่างนั้น เราเริ่มจากสังเกตว่า <math>X < (1-\delta)\mu \,</math> ก็ต่อเมื่อ <math>-X > -(1-\delta)\mu \,</math> เมื่อใช้รูปทั่วไปของขอบเขตเชอร์นอฟ ได้ว่า
: <math>\Pr[X < (1-\delta)\mu] < \inf_{t > 0} e^{(1-\delta)\mu}\mathrm{E}[e^{-tX}]</math>
เมื่อใช้การให้เหตุผลแบบเดียวกับการพิสูจน์ส่วนปลายด้านบน เราได้ว่า
: <math>\Pr[X < (1-\delta)\mu] < \inf_{t > 0} \left( \frac{e^{e^{-t}-1}}{e^{-t(1-\delta)}} \right)^\mu</math>
ค่าต่ำสุดของฟังก์ชันทางด้านขวามือของอสมการอยู่ที่ <math>t = \ln(1/(1-\delta)) \,</math> ฉะนั้น
: <math>\Pr[X < (1-\delta)\mu] < \left( \frac{e^\delta}{(1-\delta)^{1-\delta}} \right)^\mu</math>
ตามต้องการ

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

1. (ส่วนปลายด้านบน) ถ้า <math>0 < t < 2e-1 \,</math>
:: <math>\Pr[X > (1+\delta)\mu] < e^{-\mu\delta^2/4}</math>
และ สำหรับ <math>\delta > 2e-1\,</math>
:: <math>\Pr[X > (1+\delta)\mu] < 2^{-(1+\delta)\mu}</math>
2. (ส่วนปลายด้านล่าง) ถ้า <math>0<\delta\leq 1</math>
:: <math>\Pr[X < (1-\delta)\mu] < e^{-\mu\delta^2/2}</math>

[[หมวดหมู่:ทฤษฎีความน่าจะเป็น]]
[[หมวดหมู่:อสมการ]]
{{โครงคณิตศาสตร์}}