跳轉到內容

演算法實現/模擬/蒙提霍爾問題/有用性

來自華夏公益教科書
Clipboard

待辦事項
本文件是草稿。目前的內容還不錯,但需要進行邏輯上的整理。例如,缺少對主題的適當介紹。


第三個版本:是對先前版本的修改,對主持人開啟一扇門和玩家進行第二次選擇進行了建模,與第一個版本的方式相同。儘管先前版本不是正式的、適當的或完整的模型,但它在計算方面具有相同的效果,因為我們可以檢查“win += 1 if choice2 == car”這一行與“win += 1 if choice1 != car”相同,因此 choice2 資訊不必要。

事實上,在第一次選擇之後,對於一個切換玩家來說,遊戲的結果就已經決定了。這意味著完整的模型(第一個、第四個和這個版本)完全沒有必要(甚至簡潔):如果玩家最初選擇了正確的門,那麼在切換之後他一定會輸(因為他離開了正確的門);如果他選擇了錯誤的門,那麼在切換之後他一定會贏(因為正確的門是唯一可以切換到的門——另一扇門是由主持人開啟的)。由於我們在檢查第一次選擇之後已經有了當前遊戲的結果,我們不需要透過顯式地模擬其他事件來人工地再次計算它:這將是多餘的。

所有這些都意味著蒙提霍爾問題的適當、完整的模型可以抽象成一個更簡潔和更簡單的形式。完整的模型僅僅成為最簡單模型的一個例項。第五個版本實現了這樣一個最簡單的抽象,而第二個和第四個版本則作為中間簡化形式。第一個和第三個版本雖然是對場景的適當描述,但在良好的、非冗餘抽象方面的計算效率不高。事實上,所有版本從第一個到第四個的重構都導致了第五個版本,因為所有版本都是等價的,只是抽象和冗餘程度不同。

另一種表達中間模型與完整模型之間差異的方式是,完整模型從玩家的角度進行模擬:他只有在每局遊戲結束時才能知道他最初的選擇是否正確。但是,我們可以利用主持人的角度進行更簡潔(儘管是抽象的,即不再具體描述原始場景)的模擬:我們可以利用我們可以檢查第一次選擇是否正確的事實,這樣我們就可以提前知道結果,而不必執行任何額外的步驟。這在下面的第四個例子中可能更清楚。

實際上,如果我們認為蒙提霍爾問題可以簡化為簡單地檢查多次從三個元素中取出兩個元素並將其與預期元素進行比較的成功率,那麼我們可以得出結論,從第一個到第四個的所有版本在某種程度上都是冗餘的,即使它們是完全或正確地對問題進行建模。即使是最簡單的情況,我們也可以推斷出,重複和隨機性越多,結果越傾向於接近 2/3。從這個角度來看,任何對蒙提霍爾問題的計算機模擬都是毫無意義的。計算機模擬被用於所有可能的狀態的完整列舉是禁止的或不可能的,[1] 這在蒙提霍爾問題中並非如此。

注意:演算法不能簡化為一個簡單的“列印 2/3”的原因是,輸出取決於遊戲進行的次數以及正確門或玩家選擇的隨機性。例如,對於只有 10 局遊戲,成功率不太可能在模擬的所有執行中保持在 2/3。

完整的、適當的模型

wins = 0
car = 1
many times do
    choice1 = rand(1..3)     
    host = (1, 2, 3) - (car, choice1)
    choice2 = (1, 2, 3) - (host, choice1)    
    if choice2 == car   
        wins += 1  
end

部分模型(主持人的視角)

wins = 0
car = 1 
many times do
    choice = rand(1..3)
    if choice != car    
        wins += 1
end

抽象模型

wins = 0
many times do
    if rand(1..3) in 1..2
        win+= 1 
end

Ruby 實現

car = wins = 0
many = 100000
 
many.times do
    choice1 = rand(3)
    host_opts = [0, 1, 2] - [choice1, car]
    choice2 = [0, 1, 2] - [choice1, host_opts.first]
    wins += 1 if choice2 == [car] 
end
 
puts "#{(wins * 100) / many}%"

car = wins = 0
many = 1000 * 1000
 
many.times do |game|
    progress = ((game + 1) * 100) / many
    print("\b\b\b#{progress}%") 
    choice = rand(3) 
    wins += 1 unless choice == car    
end
 
puts "#{(wins * 100) / many}%"

many, wins = 1000 * 1000, 0
many.times { wins+= 1 if [0, 1].include? rand(3) }
puts "#{(wins * 100) / many}%"

參考文獻

[編輯 | 編輯原始碼]
華夏公益教科書