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

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

ใจความ

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

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

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

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

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

การพิสูจน์

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

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

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

M X ( t ) = E [ ∏ i = 1 n e t X i ] = ∏ i = 1 n E [ e t X i ] = ∏ i = 1 n ( p i e t + ( 1 − p i ) ) = ∏ i = 1 n ( 1 + p i ( e t − 1 ) ) {\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))}

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

M X ( t ) = ∏ i = 1 n ( 1 + p i ( e t − 1 ) ) < ∏ i = 1 n e p i ( e t − 1 ) = e ( e t − 1 ) ( p 1 + ⋯ + p n ) = e ( e t − 1 ) μ {\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 }}

เนื่องจาก p 1 + ⋯ + p n = E [ X 1 ] + ⋯ + E [ X n ] = E [ X 1 + ⋯ + X n ] = E [ X ] = μ {\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 } ดังนั้น

e − t ( 1 + δ ) μ M X ( t ) < e ( e t − 1 ) μ e t ( 1 + δ ) μ = ( e e t − 1 e t ( 1 + δ ) ) μ = ( e e t − t δ − t − 1 ) μ {\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 }}

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

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

Pr [ X > ( 1 + δ ) μ ] < inf t > 0 e − t ( 1 + δ ) μ M X ( t ) < inf t > 0 f ( t ) μ = f ( ln ⁡ ( 1 + δ ) ) μ = ( e δ ( 1 + δ ) 1 + δ ) μ {\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 }}

ตามต้องการ

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

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

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

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

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

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

ตามต้องการ

รูปแบบอื่น ๆ

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

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

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

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

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

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

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