試證明 Knuth Shuffle 為均勻的

2015-01-02 置頂文章

1940
0
演算法
2015-01-06

證明 Knuth Shuffle

Knuth Shuffle 偽碼

Shuffle an array A, length is N (0-based)

  For i = 0 to N-1
      r = Random between i and N  (include i, exclude N)
      exchange A[i], A[r]
　Loop

簡單來說，就是

1. 從第一個位置開始，走訪

2. 從該位置(含)以後的位置中，隨機挑一個。

3. 交換走訪到的位置、與挑中位置內的元素。

4. 進入下一個位置，重複直到歷遍所有位置。

重點在於第二點，請注意隨機挑選的範圍，被挑中的元素就固定在挑中他的位置上了，不會參加之後的挑選。

這個的C#實作，點部落很多篇文章，我就不特別著墨了。

當初想出這個洗牌法時，興高采烈地發在部落格上(yahoo部落格、已收)

經前輩點醒，這個算法是有名的Knuth Shuffle。

之後就用得理所當然，卻沒想過這算法是否真的是對的。

今天就來探討一下，這個演算法是否成立。

一個洗牌動作，除了打亂，更要亂得均勻。

何謂亂得均勻？

任一張牌，落在任何位置的機率均相等。
任一位置，放置每一張牌的機率均相等。

這兩點其實是同一件事。所以只需要證明其中一點，即可證明演算法成立。

證明的方法不只一個，這邊我用數學歸納法來證明。

命題：

長度 N 的陣列A，陣列位置為 {L₁,L₂,L₃,…,L_n}，初始狀態的內部元素為{E₁,E₂,E₃,…,E_n}

定義 P(i,j) = 實行Knuth Shuffle後，E_j位於 L_i的機率。

證明任意 i、j 組合，P(i,j) = 1 / N。

∀_i=1~n∀_j=1~nP(i,j) =1 / N

N = 1 時， A = {1}，P_N(1, 1) = 1 = 1/N 成立。

1. 假設 N = m 時，∀_i=1~m∀_j=1~mP(i , j)= 1 / m = P_m成立。

N = m+1 時：

2. 任意位置L_i，放置的E_m+1機率為 P(i, m+1), 1 ≤ i ≤ m+1

(到L₁~L_i-1均沒有選中E_m+1做交換) * (L_i時選中E_m+1做交換)

因為被選中、放到前面的元素，並不在下一次的隨機範圍內，所以若在L₁~L_i-1之中就選到E_m+1，則E_m+1就不可能被L_i選到。

L_i取亂數選擇元素時，可隨機選擇的元素會剩下(m+2-i)個，

選中某元素的機率為1/(m-i+2)，沒選中的機率為(m-i+1) /(m-i+2)

(到L₁~L_i-1均沒有選中E_m+1做交換) =

[m /(m+1)] * [(m-1) /m] * ... * [(m-i+3) /(m-i+4)] * [(m-i+2) /(m-i+3)]

可以觀察得，前項的分子會等於後項的分母，故可簡化，只留第一項的分母與最後一項的分子。

= (m-i+2) / (m+1)

又

(L_i時選中E_m+1做交換) = 1/(m-i+2)

故

任意位置L_i，放置的E_m+1機率

= (到L₁~L_i-1均沒有選中E_m+1做交換) * (L_i時選中E_m+1做交換)

= [(m-i+2) / (m+1)] * [1/(m-i+2)]

= 1 / (m+1)

∀_i=1~m+1P(i, m+1) = 1 / (m + 1)

3. 位置L_i，1 ≤ i ≤ m ；放置元素E_j，1 ≤ j≤ m 的機率

= 位置L_i，不放置的E_m+1的機率

= 1 – P(i, m+1)

又 P(i, m+1)已在2. 證明為 1 / (m+1)

1 – P(i, m+1)

= 1 – [1 / (m+1)] = m / (m+1)

在這個部分事件下，L_i所能放置的元素為{E₁,E₂,E₃,…,E_m}，

注意到了沒？這時和我們假設母體和N = m 時的狀況一致，P_m = 1 / m 。

1/m是局部事件的機率，要算出整體機率要乘上母體發生的機率。

所以可以這樣：

位置L_i，1 ≤ i ≤ m ；放置元素E_j，1 ≤ j≤ m 的機率

= ( 位置L_i，不放置的E_m+1的機率 ) * (排除 E_m+1 時， L_i放置元素E_j 的機率 )

= [m / (m+1)] * P_m= [m / (m+1)] * 1 / m

= 1 / (m+1)

∀_i=1~m∀_j=1~mP(i, j) = 1 / (m + 1)

這部分的機率若難以理解，可以這樣想：

我們有一副52張，不含鬼牌的撲克牌，抽到任何數字的機率均是 4/52。

這時我們加入2張鬼牌，我們知道，抽到鬼牌的機率是2/54。

在加入鬼牌的狀況下，抽到任何數字的機率

= (加入鬼牌後，沒抽到鬼牌的機率) * (沒有鬼牌時抽到任何數字的機率)

= (1 - 2/54) * (4/52) = (52/54) * (4/52)

= 4 / 54

4. 位置L_m+1，放置元素的E_i機率 P(m+1, j), 1 ≤ j ≤ m

= 元素 E_i 不放於 (L₁~L_m) 的機率

= 1 - ( 元素 E_i 放於 (L₁~L_m) 的機率和)

= 1 –[ ∑_k=1~m P(k, j ) ]

由3. 之證明， ∀_k=1~mP(k, j) = 1 / (m + 1) , 1 ≤ j ≤ m

故 ∑_k=1~m P(k, j ) = m * [1/(m+1)] = m /(m+1)

1 –[ ∑_k=1~m P(k, j ) ]

= 1 - m /(m+1)

= 1 / (m + 1)

∀_j=1~mP(m+1, j) = 1 / (m + 1)

5. 總結

2. ∀_i=1~m+1P(i, m+1) = 1 / (m + 1)

3. ∀_i=1~m∀_j=1~mP(i, j) = 1 / (m + 1)

4. ∀_j=1~mP(m+1, j) = 1 / (m + 1)

以上三點合併

= ∀_i=1~m+1∀_j=1~m+1P(i , j)= 1 / (m+1)

故得以以數學歸納法證明命題成立。

回首頁