| 職老:囚徒問題的第三個解釋--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左右的時候就宣布,嘿嘿。 這樣的辦法肯定更有笑,但如何找到最佳的分組和負責天數,下次再談。 |
|
![]() |
![]() |
| 實用資訊 | |
|
|
| 一周點擊熱帖 | 更多>> |
| 一周回復熱帖 |
| 歷史上的今天:回復熱帖 |
| 2008: | 【FLASH動畫塗鴉】鉛筆模仿國畫——聆 | |
| 2008: | 西西里檸檬: 太古遺音--孔子和《文王操 | |
| 2007: | 古文翻譯,嘿嘿,準備打印出來教育下一 | |
| 2007: | 華人音樂家系列: 李雲迪 | |
| 2006: | 我國白酒的起源 | |
| 2006: | 想說愛你;並不是件容易的事 | |
| 2005: | 塗香天女 | |
| 2005: | 放鬆心情的方法 | |
| 2004: | 【海外片段】流水- 祝各位節日快樂 | |
| 2004: | 背對生活 | |




