設萬維讀者為首頁 廣告服務 聯繫我們 關於萬維
簡體 繁體 手機版
分類廣告
版主:紅樹林
萬維讀者網 > 五 味 齋 > 帖子
職老:囚徒問題的第三個解釋--LUCKY囚徒機制
送交者: 職老 2009年12月20日12:32:06 於 [五 味 齋] 發送悄悄話

我在前兩次解釋中首先探討了囚徒問題的數學模型和可行性分析,當然,我們其實是假設這是一個純數學模型的,也就是說,不考慮囚徒的年齡和健康狀況的純數學模型,所以假設其玄正性存在。

那麼,如果我們親手解決這個問題的關鍵是什麼內?

其實問題的關鍵有兩個。關鍵A,讓囚徒能夠向下一位表達自己是第一次放風,還是第N次放風,這裡N>=2;

關鍵B,任何一個囚徒每次放風能知道上面X位囚徒被放過風的次數,也就是說第M次放風的X囚徒能知道M次以內被第一次放風囚徒的數目A,當這個數目A累積到100的時候,他就可以宣布了。當然這個X囚徒本身就是隨機的,可能是100個囚徒中的任何一位。

這樣,我們就不難看出,這個囚徒問題其實包括了兩個不同的分布概率,一個叫做:被抽概率,或者說放風概率;另外一個叫做:信號傳遞概率,也就是說,囚徒必須想辦法知道別的囚徒放風的情況,而且不只知道上一位囚徒的,而且還要知道上S位囚徒的。

這樣我們會發現一個難點,第M次放風的囚徒從條件上很難知道他被第M放風前S位囚徒的情況,雖然似乎他們可以開會約定一些所謂的組織分布,但其實很難座到有笑的信號傳遞,因為他們手裡面的可作為信號傳第的條件只有那盞燈。而這盞燈似乎首先要做到關鍵A的作用,然後能部分完成關鍵B的功能。

所以,如果按照不打破遊戲規則的條件,囚徒只能遵循一種叫做:LUCKY囚徒的機制完成這項任務。

1)燈是關鍵A的主要功能。囚徒必須假設燈開為第一次放風,燈關為第N次放風,N>=2。

具體操作如下:囚徒只要是第一次放風,如果看到燈開着,就維持該燈開着;如果看到燈關着,就開燈。

如果囚徒是第N次放風,就保持關着或者把開着的關上。

這樣燈本身就只傳遞唯一一個信息:前面一位是第一次或者第N次。

2)每位囚徒在牢房裡面建立一個記錄系統,比如用指甲在鋼牆上劃道道,記錄每次被第N次放風后,看到燈開着--前面一位肯定是第一次被放風的。當這個記錄數目n(包括該囚徒自己第一次被放風的)=100的時候,就宣布可以了。當然,任何一個囚徒都可以宣布,只要他牆上的n=100的時候,別人的牆上的可能是1-99任何一個數目。

這樣我們看到,國王的遊戲規則,不但提供了放風機會,而且提供了所謂的信號傳遞機會,也就是說第N次被抽到提供了一種傳遞記錄前面被第一次抽風的機會,當然,N=2是最佳的結果。

這樣,囚徒們就存在兩個相關卻獨自存在的分布:

1)被抽放風分布,簡稱:抽風分布,這個機率是不變的,第一次和第N次都是一樣,為1/100

2)傳遞分布,這個機率是改變的,可以是100%,也可以是零蛋。

那麼,讓我來首先先簡單的分析一下前10輪被抽和囚徒記錄的結果吧(只分析部分)

(1)10個囚徒都被第一次抽中,這個分布可以說是最佳被抽分布,但同時也是最差傳遞分布之一,因為囚徒只知道自己被抽和上一個被抽的情況,牆上最多記錄2道(第一個囚徒一道)

(2)一個囚徒被抽10次,這個分布可以說是最差被抽和被分布情況;

(3)10個囚徒中有個最LUCKY的傢伙,他被第2,4,6,8,10反覆被抽放風5次,這樣,他就可以記錄6個道道了。這個是最佳的抽風和傳遞分布

(4)其他的情況介於這些分布之間

 

這樣我們看來,如果囚徒按照一般的規律進行,當某個囚徒發現自己牆上的道道是100而宣布遊戲結束的時候,其它的囚徒應該是1-99的正態分布,也就是大約一共記錄了5500次的第一次被抽。如果按照10%幸運程度計算的話,總體被抽次數就是這個數目的10倍,大約55000天,也就是150年以上;如果按照5%可信度計算,就是110000天,也就是300年。

 

當然,如果存在一個LUCKY的囚徒,也就是這個囚徒被反覆的交叉被抽中,比如剛才說的2,4,6,8,10,12,。。。。。,大約201天,他的牆上就是100個道道了,這樣大家就粗去了,嘿嘿。

這個機制就叫做:LUCKY囚徒機制。

 

所以,按照抽風機率和傳遞機率以外的第三個總體分布而言,囚徒的被放出的機率可能是201天到大約300年,估計是T分布,嘿嘿。

其實,按照不破壞遊戲規則和不讓國王懷疑的前蹄下,可以內定一個LUCKY囚徒,讓他畫累積的道道,其它的囚徒畫道道記錄開始後的天數。單數1,3,5,7。。。的時候,抽到自己自己就粗去,雙數天的時候,被抽到就對監獄長說:俺不想粗去,讓LUCKY囚徒出去(比如說他身體不好,需要愛心什麼什麼的,嘿嘿),這樣,雖然不能201天就粗去(因為非LUCKY囚徒有可能被N次抽到)。

當然,也可以把100個囚徒分成10組,每組構建一個LUCKY囚徒,以防止國王生氣,但必須規定好每組只負責10天,輪流交替,當其中一組LUCKY囚徒牆上的道道為100的時候,宣布解放,嘿嘿。當然,冒險的話也可以是N=30左右的時候就宣布,嘿嘿。

這樣的辦法肯定更有笑,但如何找到最佳的分組和負責天數,下次再談。

 

0%(0)
標 題 (必選項):
內 容 (選填項):
實用資訊
回國機票$360起 | 商務艙省$200 | 全球最佳航空公司出爐:海航獲五星
海外華人福利!在線看陳建斌《三叉戟》熱血歸回 豪情築夢 高清免費看 無地區限制