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

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

รูปทั่วไป 
ให้  เป็นตัวแปรสุ่มใดๆ แล้ว
 
โดยที่
  คือ ฟังก์ชันกำเนิดโมเมนต์ (moment generating function)

การพิสูจน์ 

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

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

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

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

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

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

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

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

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

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

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

1. (ส่วนปลายด้านบน) ถ้า 
 
และ สำหรับ 
 
2. (ส่วนปลายด้านล่าง) ถ้า 
 

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