การแจกแจงคงที่และการเป็นเออร์กอดิก

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

Definition

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

Scope

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

Core questions

• ลูกโซ่มาร์คอฟมีคุณสมบัติการแจกแจงคงที่ที่เป็นเอกลักษณ์เมื่อใด?
• ภายใต้เงื่อนไขใดที่การแจกแจงของลูกโซ่จะลู่เข้าสู่การแจกแจงคงที่นั้น?
• สมดุลละเอียดคืออะไร และการผันกลับได้ทำให้การหาการแจกแจงคงที่ง่ายขึ้นได้อย่างไร?
• ค่าเฉลี่ยตามเวลาในระยะยาวเกี่ยวข้องกับค่าเฉลี่ยภายใต้การแจกแจงคงที่อย่างไร?

Key concepts

• การแจกแจงคงที่
• การไม่สามารถลดทอนได้และการไม่เป็นคาบ
• สมดุลละเอียด
• ทฤษฎีบทเออร์กอดิก
• เวลาการผสม

Key theories

การมีอยู่ ความเป็นเอกลักษณ์ และการลู่เข้าสู่สถานะคงที่

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

ทฤษฎีบทเออร์กอดิกของลูกโซ่มาร์คอฟ

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

สมดุลละเอียดและการผันกลับได้

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

Clinical relevance

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

History

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

Key figures

• Andrey Markov
• Nicholas Metropolis
• Wilfred Keith Hastings
• Sean Meyn

Seminal works

• norris1997

Frequently asked questions

ลูกโซ่มาร์คอฟทุกชนิดลู่เข้าสู่การแจกแจงคงที่หรือไม่?

ไม่ การลู่เข้าต้องอาศัยเงื่อนไขต่างๆ เช่น การไม่สามารถลดทอนได้ การกลับมาซ้ำเชิงบวก และการไม่เป็นคาบ ลูกโซ่ที่เป็นคาบอาจวนซ้ำโดยไม่เข้าสู่สถานะคงที่ และลูกโซ่ชั่วคราวหรือลูกโซ่ที่มีการกลับมาซ้ำเป็นศูนย์อาจไม่มีการแจกแจงคงที่เลย

เหตุใดการผันกลับได้จึงมีประโยชน์ในทางปฏิบัติ?

การผันกลับได้ผ่านสมดุลละเอียดให้สมการง่ายๆ ที่การแจกแจงคงที่ที่คาดว่าจะต้องเป็นไปตามนั้น ซึ่งทำให้การตรวจสอบการแจกแจงคงที่ทำได้ง่าย และยังเป็นหลักการออกแบบเบื้องหลังอัลกอริทึม Metropolis-Hastings และอัลกอริทึม Markov chain Monte Carlo อื่นๆ อีกมากมาย