The Monty Hall Problem

Puzzle

1

Python

43

Monty

1

Vu Nhat Minh viết ngày 22/01/2017

Có một bài toán khá hay mình muốn chia sẻ, gọi là The Monty Hall Problem. Đây là bài toán rất nổi tiếng khi học về xác suất thống kê, còn được gọi là The Car-Goat Problem, tên thân thương là Dê và Siêu Xe

33.3% cơ hội đổi đời

Monty Hall là một game show truyền hình hấp dẫn của Mỹ. Người dẫn chương trình, gọi là Monty, giới thiệu bạn với 3 cánh cửa, đằng sau 1 trong 3 cánh cửa là một phần thưởng cực kỳ hấp dẫn, ví dụ như, 1 con siêu xe Lamborghini chẳng hạn.

Tuy vậy đằng sau mỗi cánh cửa còn lại là... 1 chú dê

Sau khi bạn chọn, Monty sẽ làm chương trình thú vị hơn bằng cách ... mở 1 trong 2 cánh cửa còn lại. Sau cánh cửa anh ta mở ra là 1 em dê.

Monty luôn luôn có thể làm được hành động trên, bạn đã nghĩ ra được tại sao rồi phải không? Câu trả lời là vì luôn có 2/3 cánh cửa là dê, và 2 cánh cửa mà bạn không chọn chắc chắn có >= 1 cánh cửa như thế.

Bây giờ, Monty cho bạn 1 cơ hội chọn lại. Bạn có thể giữ nguyên cánh cửa ban đầu, hoặc chọn lại cánh cửa chưa bị mở còn lại. Câu hỏi là

Có nên thay đổi quyết định ban đầu hay không?

50% cơ hội hay 66.7% cơ hội ?

Lúc đầu đọc bài này mình nghĩ, giờ có 2 cửa, thật sự mình không biết Lamborghini ở đâu, nên xác suất hiển nhiên là 50%, và có thay đổi hay không cũng không quan trọng.

Nhưng thật ra câu trả lời là, nếu chọn lại cánh cửa mới xác suất đổi đời sẽ lên tới 66.7%

Thật khó tin phải không? Mình sẽ viết code để chứng minh mệnh đề trên nhé

Chứng minh bằng code

Đầu tiên giả sử 3 cánh cửa được đánh số 1,2 và 3. Trong đó 1 cánh cửa dẫn đến cơ hội sở hữu Lamborghini của chúng ta.

prizeDoor = random.randint(1,3)

Khởi đầu game show, mình sẽ chọn 1 trong 3 cánh cửa một cách ngẫu nhiên

chooseDoor = random.randint(1,3)

Tiếp theo là phần thú vị, Monty bước lên và nhẹ nhàng mở 1 trong 2 cánh cửa còn lại, và đằng sau đó là chú dê thần thánh. Để giả lập sự kiện này cần 1 vòng while loop vô hạn, bắt máy tính chọn đến khi nào thoả mãn 2 điều kiện:

• Cánh cửa mở ra không phải là cánh cửa dẫn đến Lamborghini
• Cánh cửa mở ra không phải là cánh cửa mình chọn ban đầu.

while 1:
  openDoor = random.randint(1,3)
  if (openDoor != prizeDoor) and (openDoor != chooseDoor):
    break

Bây giờ đến thời khắc quyết định: mình có cơ hội chọn lại cánh cửa mới hoặc giữ nguyên lựa chọn ban đầu. Để giả lập hành động chọn lại mình sẽ dùng 1 vòng while vô hạn nữa, cánh cửa chọn lại cũng thoả mãn 2 điều kiện

• Cảnh cửa chọn lại không phải là cánh cửa Monty vừa mở ra
• Cánh cửa chọn lại không phải là cánh cửa ban đầu đã chọn.

while 1:
  changeMind = random.randint(1,3)
  if (changeMind != openDoor) and (changeMind != chooseDoor):
    break

Và cuối cùng là màn đo kết quả. Không giống như đời thật, mình có thể "chơi thử" 1000 lần và xem liệu quyết định thay đổi lựa chọn có xác suất đổi đời cao hơn quyết định ban đầu hay không

import random

originalChance = 0
changeMindChance = 0

for i in range(1000):
  # ... Game show code
  if chooseDoor == prizeDoor:
    originalChance+=1
  if changeMind == prizeDoor:
    changeMindChance+=1

print(originalChance)
print(changeMindChance)
# 311 <- OriginalChange
# 689 <- changeMindChance

Rõ ràng rồi, không còn gì phải xoắn nữa

Giải thích bằng xác suất thống kê

Giải thích ngắn gọn: cảnh cửa đầu tiên bạn đã chọn có xác suất trúng là 33.3%, và xác suất đó không thay đổi khi có thêm các điều kiện khác. Khi Monty loại đi 1 cánh cửa trống, xác suất của cánh cửa còn lại sẽ "nhảy" lên 100% - 33.3% = 66.7%.

Nếu thử refactoring đoạn code trên thì bạn sẽ nhận ra mệnh đề rất hiển nhiên. Đoạn code gameshow có thể lược bỏ và viết lại ngắn gọn như dưới đây. Lưu ý là chooseDoor và prizeDoor là 2 biến đã được lựa chọn từ đầu, và xác suất trúng luôn có thể tính chỉ dựa trên 2 biến đó

for i in range(1000):
  prizeDoor = random.randint(1,3)
  chooseDoor = random.randint(1,3)
  if chooseDoor == prizeDoor:
    originalChance+=1
  else:
    changeMindChance+=1

Dưới đây là cây sự kiện theo wikipedia. Nếu bạn muốn tìm hiểu thêm thì có thể đọc về xác suất có điều kiện, và cách triển khai công thức xác suất để chứng minh bài toán Monty Hall ở wikipedia

Have fun