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

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

รูปทั่วไป

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

${\displaystyle \Pr[X\geq a]\ \leq \ \inf _{t>0}e^{-ta}{\mathcal {M}}_{X}(t)}$ 

โดยที่

${\displaystyle {\mathcal {M}}_{X}(t)=\mathrm {E} [e^{tX}]\quad }$  คือ ฟังก์ชันกำเนิดโมเมนต์ (moment generating function)

การพิสูจน์

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

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

${\displaystyle \Pr[X\geq a]=\Pr[e^{tX}\geq e^{ta}]\leq {\frac {\mathrm {E} [e^{tX}]}{e^{ta}}}=e^{-ta}{\mathcal {M}}_{X}(t)}$ 

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

${\displaystyle \Pr[X\geq a]\leq \inf _{t>0}e^{-ta}{\mathcal {M}}_{X}(t)}$ 

ตามต้องการ

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

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

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

ใจความ

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

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

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

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

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

การพิสูจน์

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

${\displaystyle \Pr[X>(1+\delta )\mu ]<\inf _{t>0}e^{-t(1+\delta )\mu }{\mathcal {M}}_{X}(t)}$ 

พิจารณา ${\displaystyle {\mathcal {M}}_{X}(t)=\mathrm {E} [e^{tX}]\,}$  เราได้ว่า ${\displaystyle e^{tX}=e^{tX_{1}+\cdots +tX_{n}}=\prod _{i=1}^{n}e^{tX_{i}}}$  เนื่องจากตัวแปรสุ่ม ${\displaystyle X_{1}\,}$ , ${\displaystyle X_{2}\,}$ , ${\displaystyle \ldots }$ , ${\displaystyle X_{n}\,}$  เป็นอิสระแก่กัน เราได้ว่า

${\displaystyle {\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_{i}e^{t}+(1-p_{i}))=\prod _{i=1}^{n}(1+p_{i}(e^{t}-1))}$ 

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

${\displaystyle {\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 }}$ 

เนื่องจาก ${\displaystyle 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 }$  ดังนั้น

${\displaystyle 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 }}$ 

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

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

${\displaystyle \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 }}$ 

ตามต้องการ

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

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

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

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

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

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

ตามต้องการ

รูปแบบอื่น ๆ

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

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

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

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

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

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

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