著名的Fisher-Yates shuffle算法可用于隨機置換長度為N的陣列A：For k = 1 to N Pick a random integer j from k to N Swap A[k] and A[j]我一遍又一遍地告訴我的一個常見錯誤是：For k = 1 to N Pick a random integer j from 1 to N Swap A[k] and A[j]也就是說，不是從k到N選擇一個隨機整數，而是從1到N中選擇一個隨機整數。如果你犯了這個錯誤怎么辦？我知道由此產生的排列不是均勻分布的，但我不知道對于最終的分布有什么保證。特別是，有沒有人有關于元素最終位置的概率分布的表達式？
3 回答
慕沐林林
TA貢獻2016條經驗 獲得超9個贊
讓我們說吧
a = 1/Nb = 1-aB i（k）是第th個元素
i交換后的概率矩陣k。即問題的答案“ 交換k后的位置是i什么？”。例如B 0（3）=(0 0 1 0 ... 0)和B 1（3）=(a 0 b 0 ... 0)。你想要的是每個k的B N（k）。K i是一個NxN矩陣，在第i列和第i行中有1，在其他地方為零，例如：
我我是單位矩陣，但是與該元素X = Y = I歸零。例如，對于i = 2：
一個我是
然后，
但是因為B N（k = 1..N）形成單位矩陣，所以任何給定元素i最后都在位置j的概率由矩陣的矩陣元素（i，j）給出：
例如，對于N = 4：
作為N = 500的圖表（顏色等級為100 *概率）：
所有N> 2的模式都是相同的：
第k個元素最可能的結束位置是k-1。
的至少可能的終止位置為k為?<N * LN（2） ，位置1否則
添加回答
舉報
0/150
提交
取消