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

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

ทฤษฎีการคำนวณ

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

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

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

ปริพันธ์

ตัวอย่างการใช้วิธีมอนเตการ์โล เพื่อประมาณค่า π เมื่อสุ่มวาง 30,000 จุด ค่าประมาณของ π ที่ได้มีความผิดพลาดน้อยกว่า 0.07% จากค่าจริง

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

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

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

$I=\int _{0}^{1}\dotsi \int _{0}^{1}f(x_{1},x_{2},\dotsc ,x_{n})dx_{1}\dotsm dx_{n}$

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

$X_{i,j},\quad 1\leq i\leq n,1\leq j\leq N$

แล้วให้

$I_{N}={\frac {1}{N}}\sum _{j}f(X_{1,j},X_{2,j},\dotsc ,X_{n,j})$

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

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

บทความหลัก: การเรียนรู้แบบเสริมกำลัง

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

สถิติศาสตร์

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