證明未限制隨機交換範圍的 Knuth Shuffle 亂序為不均勻的

2015-01-06 置頂文章

1066
0
演算法
2015-01-07

摘要:證明隨機範圍未限制的 Knuth Shuffle 為不均勻的

上次證明了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

錯誤的 Knuth Shuffle 偽碼，未限制隨機交換範圍，隨機範圍一直為0~N

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

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

上次有提到，何謂亂得均勻？

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

這兩點是從微觀──從位置或物件的觀點來看亂序這件事。

對於序列，亂得均勻可以有另一種巨觀定義：

只要序列內所有元素均視為不同，無論一個序列初始狀況如何，經過亂序演算法後，序列成為任何一種排列方式之機率都一樣，則該亂序演算法為均勻的。

對於N個長度的序列，其排列種類為 N!。

舉個例，{1 2 3}這個集合，所有排列方式有 3! = 6種，如下

{1 2 3}, {1 3 2}, {2 1 3}, {2 3 1}, {3 1 2}, {3 2 1}

不管拿哪個去實行均勻的亂序演算法，得到上面六個結果的機率均為 1 / 6。

這個巨觀觀點來證明不成立十分好用。

接下來要提另一個東西，叫做算法的窮舉可能性。其實這名字我亂取的，應該有更正確的名字才對。

演算法內，任何會導致輸出結果改變的有限狀態改變之窮舉。

以正確的Knuth Shuffle來看：

總共進行 N 次的交換
第 i 次交換，隨機可取得的數字為 i 個整數(i~N-1)，取得的數會導致結果改變
狀態窮舉為 N * (N-1) * (N-2)*...*1 = N!

一樣舉個實例好了，{1 2 3}這個集合拿來跑正確的Knuth Shuffle：

共跑 3 次
第一次，隨機範圍為 {0 1 2}共 3個可能性
第二次，隨機範圍為 {1 2}共 2個可能性
第三次，隨機範圍為 {2}共 1個可能性

窮舉可能性為 P = 3x2x1 = 3! = 6，由於大前提是隨機數是均勻的，故這6種可能性出現的機會是相同的。

若可能性沒辦法平均分配給所有可能出現的結果，那結果的機率就不是均勻的。

我在這篇沒有要證明Knuth Shuffle是否均勻，所以上面只是描述這樣的觀念。

在現實中好像不太容易舉例來表述這樣的概念...

好吧，回到頭來看看錯誤的Knuth Shuffle：

共跑 N 次
每一次，隨機範圍均為 {0~N-1}共N個可能性

窮舉過程狀態為 Q = N^N 種。

但長度為N的序列只有 R = N! 種結果狀態。

Q 種過程狀態要能均勻導致 R 種結果狀態。

kR = Q, k∈ℕ (正整數)

k = Q / R

k =N^N / N!

若 N^N 不是 N! 的倍數 ⇒ 不可能均勻

又，根據伯特蘭-切比雪夫定理，對於所有大於1的整數N，存在一個質數P，符合 N < P < 2N

故，N>2 時，N! 內必定有一質數P > N/2，

而此質數 P 必定不是N的因數，亦不會是 N^N 的因數。

故，N>2 時，N^N不可能為N!的倍數。

由次證明，序列長度大於2以後，隨機範圍錯誤的Knuth Shuffle就不是均勻的。

很神奇吧？感覺用了很奇怪的方式，證明了一個算法的錯誤。

回首頁