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

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

 รูปทั่วไป 
ให้  เป็นตัวแปรสุ่มใด ๆ แล้ว

โดยที่
  คือ ฟังก์ชันก่อกำเนิดโมเมนต์ (moment generating function)

 การพิสูจน์ 

สำหรับค่าคงที่บวก  ใด ๆ  เป็นฟังก์ชันเพิ่มที่มีค่าบวกเสมอ ดังนั้น  ก็ต่อเมื่อ 

เมื่อมอง  เป็นตัวแปรสุ่มและใช้อสมการของมาร์คอฟ เราได้ว่า

เนื่องจากข้อความข้างต้นเป็นจริงสำหรับทุก ๆ จำนวนจริงบวก  มันจึงเป็นจริงสำหรับ  ที่ทำให้  มีค่าต่ำสุดด้วย เพราะฉะนั้น

ตามต้องการ

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

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

 ใจความ 
ให้  เป็นจำนวนเต็มบวก และ  สำหรับจำนวน  เป็นการทดลองแบบปัวซงที่เป็นอิสระแก่กันโดยที่  และ  กำหนด  และให้  และ  เป็นจำนวนจริงใด ๆ ที่มีค่ามากกว่า 0 แล้ว:

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

2. (ส่วนปลายด้านล่าง) เมื่อ 


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

พิจารณา  เราได้ว่า  เนื่องจากตัวแปรสุ่ม , , ,  เป็นอิสระแก่กัน เราได้ว่า

เพราะว่า  สำหรับจำนวนจริงบวก  ทุกจำนวน เราได้ว่า

เนื่องจาก  ดังนั้น


กำหนดฟังก์ชัน  เราได้ว่า  และ 

สมมติให้  เราได้ว่า  และ  เพราะฉะนั้น  จึงมีค่าต่ำสุดสัมบูรณ์ที่  เราจึงได้ว่า

ตามต้องการ

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

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

ค่าต่ำสุดของฟังก์ชันทางด้านขวามือของอสมการอยู่ที่  ฉะนั้น

ตามต้องการ

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

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

และ สำหรับ 

2. (ส่วนปลายด้านล่าง) ถ้า 


หมวดหมู่:ทฤษฎีความน่าจะเป็น
หมวดหมู่:อสมการ