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

จากวิกิพีเดีย สารานุกรมเสรี
Jump to navigation Jump to search

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

รูปทั่วไป[แก้]

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

โดยที่

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

การพิสูจน์[แก้]

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

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

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

ตามต้องการ

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

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

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

ใจความ[แก้]

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

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

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

การพิสูจน์[แก้]

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

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

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

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

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

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

ตามต้องการ

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

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

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

ตามต้องการ

รูปแบบอื่น ๆ[แก้]

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

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

และ สำหรับ

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