วิธีมอนเตการ์โล

วิธีมอนเตการ์โล (Monte Carlo method, MC) เป็นชื่อเรียกวิธีการที่ใช้เลขสุ่มในการทำการจำลองหรือการวิเคราะห์เชิงตัวเลข เดิมทีมีที่มาจากการที่สตานิสวัฟ มาร์ชิน อูลัมคิดวิธีเพื่อที่จะค้นหารูปแบบของการเคลื่อนวนของนิวตรอนภายในสสาร และได้รับการตั้งชื่อนี้โดยจอห์น ฟอน นอยมันน์ โดยที่มาของชื่อมาจากชื่อเขตมอนเตการ์โลของโมนาโกซึ่งมีชื่อเสียงเรื่องกาสิโน

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

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

ทฤษฎีความซับซ้อนในการคำนวณ กำหนด ประเภทความซับซ้อนของปัญหาต่าง ๆ ที่สามารถจำลองได้ด้วยเครื่องทัวริงเชิงความน่าจะเป็น และแก้โดยใช้วิธีมอนเตการ์โล ตัวอย่างทั่วไป ได้แก่ RP, BPP และ PP ด้วยการอธิบายความสัมพันธ์ระหว่างประเภทเหล่านี้กับ P และ NP ช่วงของปัญหาที่สามารถแก้ไขได้โดยอัลกอริธึมที่มีการสุ่มเช่นวิธีมอนเตการ์โลจะขยาย (P ≠ BPP) หรือไม่ หรือจะเพียงแค่ลดลำดับเวลาพหุนามของปัญหาที่สามารถแก้ไขได้ด้วยขั้นตอนวิธีเชิงกำหนด (คือ P=BPP หรือไม่) นี่เป็นหนึ่งในคำถามสำคัญใน ทฤษฎีความซับซ้อนในการคำนวณ ปัจจุบันเรารู้ว่า NP ⊂ PP และ RP ⊆ NP แต่ไม่ทราบความสัมพันธ์ระหว่าง BPP และ NP

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

นอกจากนี้ เมื่อใช้ความน่าจะเป็นนี้ ก็จะสามารถหาคำตอบโดยประมาณของ ปริพันธ์ (พื้นที่) ได้ พื้นที่ S ของพื้นที่ R สามารถประมาณได้เป็น S = pT โดยการสุ่มวางจุดภายในพื้นที่ของพื้นที่ T ที่รวมพื้นที่ R ด้วย และค้นหาความน่าจะเป็นที่ p ตกภายในพื้นที่ R โดยใช้วิธีมอนเตการ์โล

n- อินทิกรัลพับ



คำนวณโดยใช้วิธีมอนเตการ์โลที่มีขนาดตัวอย่างเป็น N โดยสร้างตัวเลขสุ่มชุด n × N ที่มีค่าระหว่าง 0 ถึง 1



แล้วให้



จะได้ I N เป็นค่าประมาณของอินทิกรัล การแทนที่ตัวเลขสุ่มแบบสม่ำเสมอด้วยลำดับการกระจายแบบสม่ำเสมอยิ่งส่งผลให้เกิดวิธีเสมือนมอนเตการ์โล

 การเรียนรู้แบบเสริมกำลัง 

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

 สถิติศาสตร์ 
วิธีบูตสแตรป เป็นหนึ่งในวิธีมอนเตการ์โลซึ่งใช้ในทางสถิติศาสตร์

 อ้างอิง 

หมวดหมู่:วิทยาศาสตร์เชิงคำนวณ
หมวดหมู่:ฟิสิกส์เชิงคำนวณ
หมวดหมู่:กลศาสตร์เชิงสถิติ
หมวดหมู่:ขั้นตอนวิธีแบบสุ่ม
หมวดหมู่:วิธีมอนเตการ์โล