ในทางสถิติและฟิสิกส์เชิงสถิติ อั ลกอริทึมเมโทรโพลิส-เฮสติงส์ (Metropolis –Hastings algorithm ) เป็น วิธีการ มาร์คอฟเชน มอนเตคาร์โล (Markov chain Monte Carlo : MCMC) สำหรับการสร้างลำดับตัวอย่างสุ่มจากฟังก์ชันความน่าจะเป็นที่ไม่สามารถสุ่มตัวอย่างโดยตรงได้ วิธีการนี้จะเพิ่มตัวอย่างใหม่ลงในลำดับในสองขั้นตอน: ขั้นแรกจะเสนอตัวอย่างใหม่โดยอิงจากตัวอย่างก่อนหน้า จากนั้นตัวอย่างที่เสนอจะถูกเพิ่มลงในลำดับหรือถูกปฏิเสธ ขึ้นอยู่กับค่าของฟังก์ชันความน่าจะเป็น ณ จุดนั้น ลำดับที่ได้สามารถนำไปใช้ในการประมาณฟังก์ชันความน่าจะเป็น (เช่น การสร้างฮิสโตแกรม ) หรือในการคำนวณค่าอินทิกรัล (เช่นค่าคาดหวัง )

โดยทั่วไปแล้ว อัลกอริทึม Metropolis–Hastings และ MCMC อื่นๆ มักใช้สำหรับการสุ่มตัวอย่างจากข้อมูลที่มีการกระจายหลายมิติ โดยเฉพาะอย่างยิ่งเมื่อจำนวนมิติสูง สำหรับข้อมูลที่มีการกระจายมิติเดียว มักจะมีวิธีการอื่นๆ (เช่นการสุ่มตัวอย่างแบบปฏิเสธปรับตัว ) ที่สามารถให้ตัวอย่างที่เป็นอิสระจากการกระจายได้โดยตรง และวิธีการเหล่านี้จะปราศจากปัญหาของ ตัวอย่าง ที่มีความสัมพันธ์กันเองซึ่งเป็นปัญหาที่พบได้ในวิธีการ MCMC

อัลกอริทึมนี้ตั้งชื่อตามนิโคลัส เมโทรโพลิสผู้ร่วมเขียนคนแรกของบทความในปี 1953 เรื่อง " การคำนวณสมการสถานะด้วยเครื่องคำนวณความเร็วสูง"ร่วมกับอาริอานนา ดับเบิลยู. โรเซนบลูธ , มาร์แชล โรเซนบลูธ , ออกัสตา เอช. เทลเลอร์และเอ็ดเวิร์ด เทลเลอร์เป็นเวลาหลายปีที่อัลกอริทึมนี้เป็นที่รู้จักกันในชื่ออัลกอริทึมเมโทรโพลิส [ ^{1 ] [ 2 ] บทความ}ดังกล่าวเสนออัลกอริทึมสำหรับกรณีของการแจกแจงข้อเสนอแบบสมมาตร แต่ในปี 1970 ดับเบิลยู.เค. เฮสติงส์ได้ขยายไปสู่กรณีทั่วไปมากขึ้น^{[ 3 ]}ในที่สุดวิธีการทั่วไปก็ถูกระบุด้วยทั้งสองชื่อ แม้ว่าการใช้คำว่า "อัลกอริทึมเมโทรโพลิส-เฮสติงส์" ครั้งแรกจะไม่ชัดเจนก็ตาม

มีข้อโต้แย้งบางประการเกี่ยวกับการให้เครดิตในการพัฒนาอัลกอริทึม Metropolis Metropolis ซึ่งคุ้นเคยกับแง่มุมการคำนวณของวิธีการนี้ ได้บัญญัติศัพท์คำว่า "Monte Carlo" ในบทความก่อนหน้านี้ร่วมกับStanisław Ulamและเป็นผู้นำกลุ่มในแผนกทฤษฎีที่ออกแบบและสร้าง คอมพิวเตอร์ MANIAC Iที่ใช้ในการทดลองในปี 1952 อย่างไรก็ตาม ก่อนปี 2003 ไม่มีบันทึกรายละเอียดเกี่ยวกับการพัฒนาอัลกอริทึม ไม่นานก่อนที่เขาจะเสียชีวิตMarshall Rosenbluthได้เข้าร่วมการประชุมในปี 2003 ที่ LANL เพื่อรำลึกถึงครบรอบ 50 ปีของการตีพิมพ์ในปี 1953 ในการประชุมนี้ Rosenbluth ได้อธิบายอัลกอริทึมและการพัฒนาในงานนำเสนอชื่อ "Genesis of the Monte Carlo Algorithm for Statistical Mechanics" ^{[ 4 ]} Gubernatis ได้ชี้แจงประวัติศาสตร์เพิ่มเติมในบทความวารสารปี 2005 ^{[ 5 ]}ซึ่งเล่าถึงการประชุมครบรอบ 50 ปี โรเซนบลูธชี้แจงอย่างชัดเจนว่าเขาและภรรยาของเขา อาริอันนา เป็นผู้ลงมือทำงาน และเมโทรโพลิสไม่ได้มีส่วนร่วมในการพัฒนาใดๆ นอกจากการจัดหาเวลาใช้งานคอมพิวเตอร์

สิ่งนี้ขัดแย้งกับบันทึกของเอ็ดเวิร์ด เทลเลอร์ ซึ่งระบุในบันทึกความทรงจำของเขาว่าผู้เขียนบทความปี 1953 ทั้งห้าคนทำงานร่วมกันเป็นเวลา "หลายวัน (และหลายคืน)" ^{[ 6 ]}ในทางตรงกันข้าม บันทึกโดยละเอียดของโรเซนบลูธให้เครดิตเทลเลอร์กับข้อเสนอแนะที่สำคัญแต่แรกเริ่มในการ "ใช้ประโยชน์จากกลศาสตร์เชิงสถิติและหาค่าเฉลี่ยของกลุ่มแทนที่จะปฏิบัติตามจลนศาสตร์ โดยละเอียด " โรเซนบลูธกล่าวว่าสิ่งนี้ทำให้เขาเริ่มคิดเกี่ยวกับแนวทางมอนเตคาร์โลแบบทั่วไป ซึ่งเป็นหัวข้อที่เขากล่าวว่าเขาได้พูดคุยกับจอห์น ฟอน นอยมันน์ บ่อยครั้ง อาริอานนา โรเซนบลูธเล่า (ให้กูเบอร์นาติสฟังในปี 2003) ว่าออกัสตา เทลเลอร์เริ่มต้นงานคอมพิวเตอร์ แต่ตัวอาริอานนาเองรับช่วงต่อและเขียนโค้ดตั้งแต่ต้น ในประวัติศาสตร์ปากเปล่าที่บันทึกไว้ไม่นานก่อนที่เขาจะเสียชีวิต^{[ 7 ]}โรเซนบลูธให้เครดิตเทลเลอร์อีกครั้งว่าเป็นผู้ตั้งปัญหาดั้งเดิม ตัวเขาเองเป็นผู้แก้ปัญหา และอาริอานนาเป็นผู้เขียนโปรแกรมคอมพิวเตอร์

อัลกอริทึม Metropolis–Hastings สามารถสุ่มตัวอย่างจากฟังก์ชันความน่าจะเป็น ใดๆ ก็ได้ ที่มีความหนาแน่นของความน่าจะเป็น โดยมีเงื่อนไขว่าเรารู้ฟังก์ชันที่แปรผันตรงกับความหนาแน่นและสามารถคำนวณค่าของได้ ข้อกำหนดที่ว่าจะต้องแปรผันตรงกับความหนาแน่นเท่านั้น ไม่ใช่เท่ากับความหนาแน่นอย่างแน่นอน ทำให้อัลกอริทึม Metropolis–Hastings มีประโยชน์อย่างยิ่ง เพราะช่วยขจัดความจำเป็นในการคำนวณค่าตัวประกอบการทำให้เป็นมาตรฐานของความหนาแน่น ซึ่งมักทำได้ยากมากในทางปฏิบัติ ${\displaystyle P(x)}$${\displaystyle f(x)}$${\displaystyle P}$${\displaystyle f(x)}$${\displaystyle f(x)}$

อัลกอริทึม Metropolis–Hastings สร้างลำดับของค่าตัวอย่างในลักษณะที่ว่า เมื่อสร้างค่าตัวอย่างมากขึ้นเรื่อยๆ การกระจายของค่าก็จะยิ่งใกล้เคียงกับการกระจายที่ต้องการมากขึ้น ค่าตัวอย่างเหล่านี้ถูกสร้างขึ้นซ้ำๆ ในลักษณะที่ว่า การกระจายของค่าตัวอย่างถัดไปขึ้นอยู่กับค่าตัวอย่างปัจจุบันเท่านั้น ซึ่งทำให้ลำดับของค่าตัวอย่างเป็นลูกโซ่ Markovโดยเฉพาะอย่างยิ่ง ในแต่ละรอบการทำงาน อัลกอริทึมจะเสนอค่าตัวอย่างที่เป็นไปได้สำหรับค่าตัวอย่างถัดไปโดยอิงจากค่าตัวอย่างปัจจุบัน จากนั้น ด้วยความน่าจะเป็นบางอย่าง ค่าตัวอย่างที่เป็นไปได้นั้นจะถูกยอมรับ ซึ่งในกรณีนี้ ค่าตัวอย่างที่เป็นไปได้จะถูกนำไปใช้ในรอบการทำงานถัดไป หรือถูกปฏิเสธ ซึ่งในกรณีนี้ ค่าตัวอย่างที่เป็นไปได้จะถูกทิ้ง และค่าปัจจุบันจะถูกนำกลับมาใช้ใหม่ในรอบการทำงานถัดไป ความน่าจะเป็นของการยอมรับจะถูกกำหนดโดยการเปรียบเทียบค่าของฟังก์ชันของค่าตัวอย่างปัจจุบันและค่าตัวอย่างที่เป็นไปได้กับการกระจายที่ต้องการ ${\displaystyle f(x)}$

วิธีการที่ใช้ในการเสนอผู้สมัครใหม่นั้น มีลักษณะเฉพาะด้วยการกระจายความน่าจะเป็น(บางครั้งเขียนว่า) ของตัวอย่างที่เสนอใหม่โดยพิจารณาจากตัวอย่างก่อนหน้าสิ่งนี้เรียกว่าความหนาแน่นของการเสนอฟังก์ชันการเสนอหรือการกระจายแบบกระโดดโดยทั่วไปแล้ว มักเลือกใช้การกระจายแบบเกาส์เซียนที่มีจุดศูนย์กลางอยู่ที่เพื่อให้จุดที่อยู่ใกล้มีโอกาสถูกเลือกในลำดับถัดไปมากกว่า ทำให้ลำดับของตัวอย่างกลายเป็นการเดินสุ่มแบบเกาส์เซียนในบทความต้นฉบับโดย Metropolis et al. (1953) ได้เสนอให้ใช้การกระจายแบบเอกรูปที่มีขอบเขตจำกัดที่ระยะห่างสูงสุดจาก นอกจากนี้ยังสามารถใช้ฟังก์ชันการเสนอที่ซับซ้อนกว่าได้ เช่น ฟังก์ชันของHamiltonian Monte Carlo , Langevin Monte CarloหรือCrank–Nicolson แบบปรับสภาพล่วงหน้า ${\displaystyle g(x\mid y)}$${\displaystyle Q(x\mid y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle g(x\mid y)}$${\displaystyle y}$${\displaystyle y}$${\displaystyle g(x\mid y)}$${\displaystyle y}$

เพื่อเป็นการยกตัวอย่าง จะมีการอธิบายอัลกอริทึมเมโทรโพลิส ซึ่งเป็นกรณีพิเศษของอัลกอริทึมเมโทรโพลิส-เฮสติงส์ โดยที่ฟังก์ชันเสนอมีความสมมาตร ไว้ด้านล่างนี้

อัลกอริทึมเมโทรโพลิส (การกระจายข้อเสนอแบบสมมาตร)

ให้เป็นฟังก์ชันที่แปรผันตรงกับฟังก์ชันความหนาแน่นความน่าจะเป็นที่ต้องการ(หรือเรียกอีกอย่างว่าการแจกแจงเป้าหมาย) ^{[ a ]}${\displaystyle f(x)}$${\displaystyle P(x)}$

1. การเริ่มต้น: เลือกจุดใดจุดหนึ่งเป็นข้อมูลสังเกตแรกในตัวอย่าง และเลือกฟังก์ชันเสนอแนะในส่วนนี้ ถือว่าฟังก์ชันเสนอแนะมีความสมมาตร กล่าว คือต้องเป็นไปตามเงื่อนไข${\displaystyle x_{t}}$${\displaystyle g(x\mid y)}$${\displaystyle g}$${\displaystyle g(x\mid y)=g(y\mid x)}$
2. สำหรับแต่ละรอบการทำซ้ำt :
   • เสนอชื่อผู้สมัครสำหรับตัวอย่างถัดไปโดยเลือกจากชุดข้อมูลที่มีอยู่${\displaystyle x'}$${\displaystyle g(x'\mid x_{t})}$
   • คำนวณอัตราส่วนการยอมรับ ซึ่งจะใช้ในการตัดสินใจว่าจะยอมรับหรือปฏิเสธผู้สมัคร^{[ b ]}เนื่องจากfเป็นสัดส่วนกับความหนาแน่นของPเราจึงได้ว่า.${\displaystyle \alpha =f(x')/f(x_{t})}$${\displaystyle \alpha =f(x')/f(x_{t})=P(x')/P(x_{t})}$
   • ยอมรับหรือปฏิเสธ :
     • สร้างเลขสุ่มแบบสม่ำเสมอ${\displaystyle u\in [0,1]}$
     • ถ้าเป็นเช่นนั้นให้ยอมรับผู้สมัครโดยการตั้งค่า${\displaystyle u\leq \alpha }$${\displaystyle x_{t+1}=x'}$
     • ถ้าเป็นเช่นนั้นให้ปฏิเสธผู้สมัครรายนั้นและกำหนดค่าใหม่แทน${\displaystyle u>\alpha }$${\displaystyle x_{t+1}=x_{t}}$

อัลกอริทึมนี้ทำงานโดยการพยายามเคลื่อนที่ไปรอบๆพื้นที่ตัวอย่างแบบสุ่มบางครั้งยอมรับการเคลื่อนที่ และบางครั้งคงอยู่ที่เดิม อัตราการคงอยู่ที่จุดใดจุดหนึ่งจะเป็นสัดส่วนกับจำนวนรอบที่ใช้ไปกับจุดนั้นโดยอัลกอริทึม โปรดทราบว่าอัตราการยอมรับบ่งชี้ว่าตัวอย่างใหม่ที่เสนอมีความน่าจะเป็นมากน้อยเพียงใดเมื่อเทียบกับตัวอย่างปัจจุบัน ตามการแจกแจงที่มีความหนาแน่นเป็นถ้าเราพยายามเคลื่อนที่ไปยังจุดที่มีความน่าจะเป็นมากกว่าจุดที่มีอยู่ (เช่น จุดในบริเวณที่มีความหนาแน่นสูงกว่า ซึ่งสอดคล้องกับ) เราจะยอมรับการเคลื่อนที่เสมอ อย่างไรก็ตาม ถ้าเราพยายามเคลื่อนที่ไปยังจุดที่มีความน่าจะเป็นน้อยกว่า บางครั้งเราจะปฏิเสธการเคลื่อนที่ และยิ่งความน่าจะเป็นลดลงมากเท่าใด โอกาสที่เราจะปฏิเสธจุดใหม่ก็จะยิ่งมากขึ้นเท่านั้น ดังนั้น เราจึงมักจะอยู่ใน (และส่งคืนตัวอย่างจำนวนมากจาก) บริเวณที่มีความหนาแน่นสูงของในขณะที่ไปเยี่ยมชมบริเวณที่มีความหนาแน่นต่ำเป็นครั้งคราวเท่านั้น โดยสัญชาตญาณแล้ว นี่คือเหตุผลที่อัลกอริทึมนี้ทำงานได้และส่งคืนตัวอย่างที่สอดคล้องกับการแจกแจงที่ต้องการด้วยความหนาแน่น ${\displaystyle P(x)}$${\displaystyle x}$${\displaystyle \alpha }$${\displaystyle P(x)}$${\displaystyle P(x)}$${\displaystyle \alpha >1\geq u}$${\displaystyle P(x)}$${\displaystyle P(x)}$

เมื่อเปรียบเทียบกับอัลกอริทึมอย่างadaptive rejection sampling ^{[ 8 ]}ที่สร้างตัวอย่างอิสระจากการกระจายโดยตรง Metropolis–Hastings และอัลกอริทึม MCMC อื่นๆ มีข้อเสียหลายประการ:

• ตัวอย่างเหล่านี้มีความสัมพันธ์กันเองแม้ว่าในระยะยาวแล้วจะแสดงผลได้อย่างถูกต้อง แต่ชุดตัวอย่างที่อยู่ใกล้เคียงกันจะมีความสัมพันธ์กันและไม่สะท้อนการกระจายตัวอย่างถูกต้อง ซึ่งหมายความว่าขนาดตัวอย่างที่มีประสิทธิภาพอาจต่ำกว่าจำนวนตัวอย่างที่เก็บมาจริงอย่างมาก ส่งผลให้เกิดข้อผิดพลาดขนาดใหญ่${\displaystyle P(x)}$
• แม้ว่าในที่สุดห่วงโซ่ Markov จะลู่เข้าสู่การกระจายที่ต้องการ แต่ตัวอย่างเริ่มต้นอาจมีการกระจายที่แตกต่างกันมาก โดยเฉพาะอย่างยิ่งหากจุดเริ่มต้นอยู่ในบริเวณที่มีความหนาแน่นต่ำ ส่งผลให้โดยทั่วไปจำเป็นต้องมีช่วงการเผาไหม้^{[ 9 ]}ซึ่งจะมีการทิ้งตัวอย่างเริ่มต้นจำนวนหนึ่ง

ในทางกลับกัน วิธี การสุ่มตัวอย่างแบบปฏิเสธ อย่างง่ายส่วนใหญ่ ประสบปัญหา " คำสาปแห่งมิติ " ซึ่งความน่าจะเป็นของการปฏิเสธจะเพิ่มขึ้นแบบทวีคูณตามจำนวนมิติ วิธี Metropolis–Hastings และวิธีการ MCMC อื่นๆ ไม่มีปัญหาดังกล่าวในระดับนั้น และด้วยเหตุนี้จึงมักเป็นวิธีแก้ปัญหาเดียวที่มีอยู่เมื่อจำนวนมิติของการกระจายที่จะสุ่มตัวอย่างมีมาก ส่งผลให้วิธีการ MCMC มักเป็นวิธีการที่เลือกใช้สำหรับการสร้างตัวอย่างจากแบบจำลอง Bayesian แบบลำดับชั้นและแบบจำลองทางสถิติที่มีมิติสูงอื่นๆ ที่ใช้กันในปัจจุบันในหลายสาขาวิชา

ใน การแจกแจง แบบหลายตัวแปรอัลกอริทึม Metropolis–Hastings แบบคลาสสิกดังที่อธิบายไว้ข้างต้นเกี่ยวข้องกับการเลือกจุดตัวอย่างหลายมิติใหม่ เมื่อจำนวนมิติสูง การหาการแจกแจงแบบกระโดดที่เหมาะสมที่จะใช้อาจเป็นเรื่องยาก เนื่องจากมิติแต่ละมิติมีพฤติกรรมที่แตกต่างกันมาก และความกว้างของการกระโดด (ดูข้างต้น) ต้อง "พอดี" สำหรับทุกมิติพร้อมกันเพื่อหลีกเลี่ยงการผสมที่ช้าเกินไป แนวทางอื่นที่มักจะได้ผลดีกว่าในสถานการณ์ดังกล่าว เรียกว่าการสุ่มตัวอย่างแบบ Gibbsเกี่ยวข้องกับการเลือกตัวอย่างใหม่สำหรับแต่ละมิติแยกจากกัน แทนที่จะเลือกตัวอย่างสำหรับทุกมิติพร้อมกัน ด้วยวิธีนี้ ปัญหาของการสุ่มตัวอย่างจากพื้นที่ที่มีมิติสูงจะลดลงเหลือเพียงชุดของปัญหาในการสุ่มตัวอย่างจากมิติขนาดเล็ก^{[ 10 ]}วิธีนี้ใช้ได้ผลดีเป็นพิเศษเมื่อการแจกแจงแบบหลายตัวแปรประกอบด้วยชุดของตัวแปรสุ่ม แต่ละตัวซึ่งแต่ละตัวแปรขึ้นอยู่กับตัวแปรอื่นเพียงไม่กี่ตัวเท่านั้น เช่นเดียวกับใน แบบจำลองลำดับชั้นทั่วไปส่วนใหญ่จากนั้นตัวแปรแต่ละตัวจะถูกสุ่มตัวอย่างทีละตัว โดยแต่ละตัวแปรจะขึ้นอยู่กับค่าล่าสุดของตัวแปรอื่นๆ ทั้งหมด สามารถใช้อัลกอริธึมต่างๆ ในการเลือกตัวอย่างแต่ละตัวเหล่านี้ได้ ขึ้นอยู่กับรูปแบบที่แน่นอนของการกระจายแบบหลายตัวแปร: บางความเป็นไปได้ ได้แก่วิธีการสุ่มตัวอย่างแบบปฏิเสธที่ปรับตัวได้^{[ 8 ]}อัลกอริธึมการสุ่มตัวอย่างแบบ Metropolis ที่ปฏิเสธที่ปรับตัวได้^{[ 11 ]}ขั้นตอน Metropolis–Hastings แบบมิติเดียวอย่างง่าย หรือการสุ่มตัวอย่างแบบแบ่งส่วน

จุดประสงค์ของอัลกอริทึม Metropolis–Hastings คือการสร้างชุดสถานะตามการกระจายที่ต้องการเพื่อให้บรรลุเป้าหมายนี้ อัลกอริทึมจะใช้กระบวนการ Markovซึ่งเข้าถึงการกระจายสถานะคงที่ที่ไม่ซ้ำกันในเชิงอะซิมโท ติก โดยที่^{[ 12 ]}${\displaystyle P(x)}$${\displaystyle \pi (x)}$${\displaystyle \pi (x)=P(x)}$

กระบวนการมาร์คอฟได้รับการกำหนดอย่างเป็นเอกลักษณ์โดยความน่าจะเป็นของการเปลี่ยนสถานะซึ่งเป็นความน่าจะเป็นของการเปลี่ยนสถานะจากสถานะที่กำหนดใดๆไปยังสถานะที่กำหนดอื่นๆโดยมีการกระจายสถานะคงที่ที่ไม่ซ้ำกันเมื่อตรงตามเงื่อนไขสองประการต่อไปนี้: ^{[ 12 ]}${\displaystyle P(x'\mid x)}$${\displaystyle x}$${\displaystyle x'}$${\displaystyle \pi (x)}$

1. การมีอยู่ของการกระจายแบบคงที่ : จะต้องมีการกระจายแบบคงที่เงื่อนไขที่เพียงพอแต่ไม่จำเป็นคือสมดุลโดยละเอียดซึ่งกำหนดให้การเปลี่ยนสถานะแต่ละครั้งสามารถย้อนกลับได้: สำหรับทุกคู่ของสถานะความน่าจะเป็นที่จะอยู่ในสถานะและเปลี่ยนไปเป็นสถานะจะต้องเท่ากับความน่าจะเป็นที่จะอยู่ในสถานะและเปลี่ยนไปเป็นสถานะ${\displaystyle \pi (x)}$${\displaystyle x\to x'}$${\displaystyle x,x'}$${\displaystyle x}$${\displaystyle x'}$${\displaystyle x'}$${\displaystyle x}$${\displaystyle \pi (x)P(x'\mid x)=\pi (x')P(x\mid x')}$
2. ความเป็นเอกลักษณ์ของการกระจายสถานะคงที่ : การกระจายสถานะคงที่ต้องมีเอกลักษณ์ สิ่งนี้รับประกันโดยคุณสมบัติเออร์โกดิกของกระบวนการมาร์คอฟ ซึ่งกำหนดให้ทุกสถานะต้อง (1) ไม่เป็นคาบ – ระบบจะไม่กลับไปยังสถานะเดิมในช่วงเวลาคงที่ และ (2) เป็นการเกิดซ้ำเชิงบวก – จำนวนขั้นตอนที่คาดหวังสำหรับการกลับไปยังสถานะเดิมมีค่าจำกัด${\displaystyle \pi (x)}$

อัลกอริทึม Metropolis–Hastings เกี่ยวข้องกับการออกแบบกระบวนการ Markov (โดยการสร้างความน่าจะเป็นของการเปลี่ยนสถานะ) ที่ตรงตามเงื่อนไขสองข้อข้างต้น โดยที่การกระจายสถานะคงที่ของกระบวนการนั้นถูกเลือกให้เป็น การได้มาซึ่งอัลกอริทึมเริ่มต้นด้วยเงื่อนไขของความสมดุลโดยละเอียด : ${\displaystyle \pi (x)}$${\displaystyle P(x)}$

${\displaystyle P(x'\mid x)P(x)=P(x\mid x')P(x'),}$

ซึ่งถูกเขียนใหม่เป็น

${\displaystyle {\frac {P(x'\mid x)}{P(x\mid x')}}={\frac {P(x')}{P(x)}}.}$

แนวทางคือการแยกการเปลี่ยนสถานะออกเป็นสองขั้นตอนย่อย ได้แก่ การเสนอและการยอมรับ-ปฏิเสธ การแจกแจงการเสนอคือความน่าจะเป็นแบบมีเงื่อนไขของการเสนอสถานะเมื่อกำหนดและการแจกแจงการยอมรับคือความน่าจะเป็นที่จะยอมรับสถานะที่เสนอความน่าจะเป็นของการเปลี่ยนสถานะสามารถเขียนได้เป็นผลคูณของการแจกแจงทั้งสอง: ${\displaystyle g(x'\mid x)}$${\displaystyle x'}$${\displaystyle x}$${\displaystyle A(x',x)}$${\displaystyle x'}$

${\displaystyle P(x'\mid x)=g(x'\mid x)A(x',x).}$

เมื่อแทนความสัมพันธ์นี้ลงในสมการก่อนหน้า เราจะได้

${\displaystyle {\frac {A(x',x)}{A(x,x')}}={\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}.}$

ขั้นตอนต่อไปในการหาค่าคือการเลือกอัตราการยอมรับที่ตรงตามเงื่อนไขข้างต้น ตัวเลือกที่นิยมใช้กันอย่างหนึ่งคือตัวเลือกแบบเมโทรโพลิส:

${\displaystyle A(x',x)=\min \left(1,{\frac {P(x')}{P(x)}}{\frac {g(x\mid x')}{g(x'\mid x)}}\right).}$

สำหรับอัตราส่วนการยอมรับของเมืองใหญ่แห่งนี้ไม่ว่าจะเป็นแบบใดแบบหนึ่ง เงื่อนไขก็เป็นไปตามที่กำหนด ${\displaystyle A}$${\displaystyle A(x',x)=1}$${\displaystyle A(x,x')=1}$

ดังนั้นอัลกอริทึม Metropolis–Hastings สามารถเขียนได้ดังนี้:

1. เริ่มต้น
   1. เลือกสถานะเริ่มต้น${\displaystyle x_{0}}$
   2. ชุด.${\displaystyle t=0}$
2. ย้ำ
   1. สร้างสถานะผู้สมัครแบบสุ่มตาม.${\displaystyle x'}$${\displaystyle g(x'\mid x_{t})}$
   2. คำนวณความน่าจะเป็นในการยอมรับ${\displaystyle A(x',x_{t})=\min \left(1,{\frac {P(x')}{P(x_{t})}}{\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}\right)}$
   3. ยอมรับหรือปฏิเสธ :
      1. สร้างเลขสุ่มแบบสม่ำเสมอ${\displaystyle u\in [0,1]}$
      2. ถ้าเป็นเช่นนั้นให้ยอมรับสถานะใหม่และตั้งค่า;${\displaystyle u\leq A(x',x_{t})}$${\displaystyle x_{t+1}=x'}$
      3. ถ้าเป็นเช่นนั้นให้ปฏิเสธสถานะใหม่ และคัดลอกสถานะเดิมไปข้างหน้า${\displaystyle u>A(x',x_{t})}$${\displaystyle x_{t+1}=x_{t}}$
   4. เพิ่มค่า : ตั้งค่า.${\displaystyle t=t+1}$

หากตรงตามเงื่อนไขที่กำหนด การกระจายเชิงประจักษ์ของสถานะที่บันทึกไว้จะเข้าใกล้จำนวนการวนซ้ำ ( ) ที่จำเป็นในการประมาณค่าอย่างมีประสิทธิภาพขึ้นอยู่กับจำนวนปัจจัย รวมถึงความสัมพันธ์ระหว่างและการกระจายข้อเสนอ และความแม่นยำในการประมาณค่าที่ต้องการ^{[ 13 ]}สำหรับการกระจายบนปริภูมิสถานะแบบไม่ต่อเนื่อง จะต้องมีขนาดใกล้เคียงกับ เวลา สหสัมพันธ์อัตโนมัติของกระบวนการมาร์คอฟ^{[ 14 ]}บัญชีที่เข้าถึงได้ของทฤษฎีการบรรจบกันสำหรับ Metropolis–Hastings มีอยู่ใน^{[ 15 ]}${\displaystyle x_{0},\ldots ,x_{T}}$${\displaystyle P(x)}$${\displaystyle T}$${\displaystyle P(x)}$${\displaystyle P(x)}$

สิ่งสำคัญที่ควรสังเกตคือ ในปัญหาทั่วไปนั้น ไม่ชัดเจนว่าควรใช้การแจกแจงแบบใด หรือจำนวนรอบการทำซ้ำที่จำเป็นสำหรับการประมาณค่าที่เหมาะสมคือเท่าใด ทั้งสองอย่างเป็นพารามิเตอร์อิสระของวิธีการ ซึ่งต้องปรับให้เข้ากับปัญหาเฉพาะที่กำลังพิจารณาอยู่ ${\displaystyle g(x'\mid x)}$

การใช้งานทั่วไปของอัลกอริทึม Metropolis–Hastings คือการคำนวณอินทิกรัล โดยเฉพาะอย่างยิ่ง พิจารณาปริภูมิและฟังก์ชันการกระจายความน่าจะเป็นเหนือ, อัลกอริทึม Metropolis–Hastings สามารถประมาณค่าอินทิกรัลในรูปแบบของ ${\displaystyle \Omega \subset \mathbb {R} }$${\displaystyle P(x)}$${\displaystyle \Omega }$${\displaystyle x\in \Omega }$

${\displaystyle P(E)=\int _{\Omega }A(x)P(x)\,dx,}$

โดยที่เป็นฟังก์ชันที่สนใจ (ซึ่งสามารถวัดได้) ${\displaystyle A(x)}$

ตัวอย่างเช่น พิจารณาสถิติ และฟังก์ชันความน่าจะเป็นของมันซึ่งเป็นการแจกแจงแบบมาร์จินัลสมมติว่าเป้าหมายคือการประมาณค่าสำหรับบนส่วนหางของ การ แจกแจง ในทางคณิตศาสตร์สามารถเขียนได้เป็น ${\displaystyle E(x)}$${\displaystyle P(E)}$${\displaystyle P(E)}$${\displaystyle E}$${\displaystyle P(E)}$${\displaystyle P(E)}$

${\displaystyle P(E)=\int _{\Omega }P(E\mid x)P(x)\,dx=\int _{\Omega }\delta {\big (}E-E(x){\big )}P(x)\,dx=E{\big (}P(E\mid X){\big )}}$

ดังนั้น การประมาณค่าจึงสามารถทำได้โดยการประมาณค่าที่คาดหวังของฟังก์ชันตัวบ่งชี้ซึ่งมีค่าเป็น 1 เมื่อและเป็นศูนย์ในกรณีอื่น ๆ เนื่องจากอยู่ที่ส่วนท้ายของความน่าจะเป็นที่จะสุ่มได้สถานะที่มี อยู่ที่ส่วนท้ายของจึงเป็นสัดส่วนกับซึ่งมีค่าน้อยตามนิยาม อัลกอริทึม Metropolis–Hastings สามารถนำมาใช้ในที่นี้เพื่อสุ่มสถานะ (ที่หายาก) ที่มีโอกาสเกิดขึ้นมากกว่า และเพิ่มจำนวนตัวอย่างที่ใช้ในการประมาณค่าที่ส่วนท้ายได้ เช่น สามารถทำได้โดยการใช้การแจกแจงการสุ่มตัวอย่างเพื่อสนับสนุนสถานะเหล่านั้น (เช่น ที่มี) ${\displaystyle P(E)}$${\displaystyle A_{E}(x)\equiv \mathbf {1} _{E}(x)}$${\displaystyle E(x)\in [E,E+\Delta E]}$${\displaystyle E}$${\displaystyle P(E)}$${\displaystyle x}$${\displaystyle E(x)}$${\displaystyle P(E)}$${\displaystyle P(E)}$${\displaystyle P(E)}$${\displaystyle \pi (x)}$${\displaystyle \pi (x)\propto e^{aE}}$${\displaystyle a>0}$

สมมติว่าค่าล่าสุดที่สุ่มมาคือ. เพื่อปฏิบัติตามอัลกอริทึม Metropolis–Hastings ต่อไปเราจะสุ่มสถานะข้อเสนอใหม่ด้วยความหนาแน่นของความน่าจะเป็นและคำนวณค่า ${\displaystyle x_{t}}$${\displaystyle x'}$${\displaystyle g(x'\mid x_{t})}$

${\displaystyle a=a_{1}a_{2},}$

ที่ไหน

${\displaystyle a_{1}={\frac {P(x')}{P(x_{t})}}}$

คืออัตราส่วนความน่าจะเป็น (เช่น ความน่าจะเป็นภายหลังแบบเบย์เซียน) ระหว่างตัวอย่างที่เสนอและตัวอย่างก่อนหน้าและ ${\displaystyle x'}$${\displaystyle x_{t}}$

${\displaystyle a_{2}={\frac {g(x_{t}\mid x')}{g(x'\mid x_{t})}}}$

คืออัตราส่วนของความหนาแน่นของการเสนอในสองทิศทาง (จากไปและในทางกลับกัน) ซึ่งจะมีค่าเท่ากับ 1 ถ้าความหนาแน่นของการเสนอมีความสมมาตร จากนั้นสถานะใหม่จะถูกเลือกตามกฎต่อไปนี้ ${\displaystyle x_{t}}$${\displaystyle x'}$${\displaystyle x_{t+1}}$

ถ้า${\displaystyle a\geq 1{:}}$

${\displaystyle x_{t+1}=x',}$

อื่น:

${\displaystyle x_{t+1}={\begin{cases}x'&{\text{with probability }}a,\\x_{t}&{\text{with probability }}1-a.\end{cases}}}$

ห่วงโซ่มาร์คอฟเริ่มต้นจากค่าเริ่มต้นที่กำหนดขึ้นเองและอัลกอริทึมจะทำงานซ้ำหลายรอบจนกว่าสถานะเริ่มต้นนี้จะ "ถูกลืม" ตัวอย่างที่ถูกทิ้งเหล่านี้เรียกว่าช่วงเผาไหม้ (burn-in ) ชุดค่าที่ยอมรับได้ที่เหลืออยู่จะแสดงถึงตัวอย่าง จาก 1 การแจกแจง${\displaystyle x_{0}}$${\displaystyle x}$${\displaystyle P(x)}$

อัลกอริทึมจะทำงานได้ดีที่สุดหากความหนาแน่นของข้อเสนอตรงกับรูปร่างของการกระจายเป้าหมายซึ่งการสุ่มตัวอย่างโดยตรงทำได้ยาก นั่นคือ หาก ใช้ความหนาแน่นของข้อเสนอแบบเกาส์เซียน พารามิเตอร์ความแปรปรวน จะต้องได้รับการปรับแต่งในช่วงระยะเวลาการเผาไหม้ โดยปกติจะทำได้โดยการคำนวณอัตราการยอมรับซึ่งเป็นเศษส่วนของตัวอย่างที่เสนอที่ได้รับการยอมรับในหน้าต่างของตัวอย่างสุดท้าย อัตราการยอมรับที่ต้องการขึ้นอยู่กับการกระจายเป้าหมาย อย่างไรก็ตาม ได้มีการแสดงให้เห็นในทางทฤษฎีแล้วว่าอัตราการยอมรับในอุดมคติสำหรับการกระจายแบบเกาส์เซียนหนึ่งมิติอยู่ที่ประมาณ 50% ลดลงเหลือประมาณ 23% สำหรับการกระจายเป้าหมายแบบเกาส์เซียนหลายมิติ^{[ 16 ]}แนวทางเหล่านี้สามารถใช้ได้ผลดีเมื่อสุ่มตัวอย่างจากเบย์เซียนโพสเทอริออร์ที่สม่ำเสมอเพียงพอ เนื่องจากมักจะเป็นไปตามการกระจายแบบปกติหลายตัวแปรดังที่สามารถสร้างได้โดยใช้ทฤษฎีบทของเบิร์นสไตน์-ฟอน มิเซส^{[ 17 ]}${\displaystyle P(x)}$${\displaystyle g(x'\mid x_{t})\approx P(x')}$${\displaystyle g}$${\displaystyle \sigma ^{2}}$${\displaystyle N}$${\displaystyle N}$

ถ้าค่า เล็กเกินไปการผสมผสานในห่วงโซ่จะเกิดขึ้นช้า (กล่าวคือ อัตราการยอมรับจะสูง แต่ตัวอย่างที่ต่อเนื่องกันจะเคลื่อนที่ไปรอบๆ พื้นที่อย่างช้าๆ และห่วงโซ่จะลู่เข้าสู่ค่า อย่างช้าๆ) ในทางกลับกัน ถ้าค่า ใหญ่เกินไป อัตราการยอมรับจะต่ำมาก เพราะข้อเสนอมีแนวโน้มที่จะตกอยู่ในบริเวณที่มีความหนาแน่นของความน่าจะเป็นต่ำกว่ามาก ดังนั้นค่าจะมีขนาดเล็กมาก และห่วงโซ่ก็จะลู่เข้าสู่ค่า ช้ามากเช่นกัน โดยทั่วไปแล้ว เราจะปรับการกระจายของข้อเสนอเพื่อให้ขั้นตอนวิธีรับตัวอย่างประมาณ 30% ของตัวอย่างทั้งหมด ซึ่งสอดคล้องกับการประมาณการทางทฤษฎีที่กล่าวถึงในย่อหน้าก่อนหน้า ${\displaystyle \sigma ^{2}}$${\displaystyle P(x)}$${\displaystyle \sigma ^{2}}$${\displaystyle a_{1}}$

MCMC สามารถใช้เพื่อสุ่มตัวอย่างจาก ความน่า จะเป็นภายหลังของแบบจำลองทางสถิติความน่าจะเป็นในการยอมรับกำหนดโดย: โดยที่คือความน่าจะเป็นแบบมี เงื่อนไข คือ ความหนาแน่น ของความน่าจะเป็นก่อนหน้าและคือความน่าจะเป็นที่เสนอ (แบบมีเงื่อนไข) ${\displaystyle P_{acc}(\theta _{i}\to \theta ^{*})=\min \left(1,{\frac {{\mathcal {L}}(y|\theta ^{*})P(\theta ^{*})}{{\mathcal {L}}(y|\theta _{i})P(\theta _{i})}}{\frac {Q(\theta _{i}|\theta ^{*})}{Q(\theta ^{*}|\theta _{i})}}\right),}$${\displaystyle {\mathcal {L}}}$${\displaystyle P(\theta )}$${\displaystyle Q}$

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

• Berg, Bernd A (ตุลาคม 2547). การจำลองแบบมอนเตคาร์โลลูกโซ่มาร์คอฟและการวิเคราะห์ทางสถิติ: ด้วยรหัส Fortran บนเว็บ World Scientific . doi : 10.1142 /5602 . ISBN 978-981-238-935-0.
• Chib, Siddhartha; Greenberg, Edward (พฤศจิกายน 1995). "การทำความเข้าใจอัลกอริทึม Metropolis-Hastings" The American Statistician . 49 (4): 327. doi : 10.2307/2684568 .
• Minh, David DL; Minh, Do Le (Paul) (2015-02-07). "การทำความเข้าใจอัลกอริทึม Hastings"การสื่อสารทางสถิติ - การจำลองและการคำนวณ 44 ( 2): 332– 349. arXiv : 1408.4438 . doi : 10.1080/03610918.2013.777455 . ISSN  0361-0918 .
• Bolstad, William M. (2010). ทำความเข้าใจสถิติเบย์เซียนเชิงคำนวณ . ชุดหนังสือสถิติเชิงคำนวณของ Wiley. โฮโบเคน, นิวเจอร์ซีย์: Wiley. ISBN 978-0-470-04609-8.