桃花長(zhǎng)相依
2019-08-30 17:11:14
著名的Fisher-Yates shuffle算法可用于隨機(jī)置換長(zhǎng)度為N的陣列A:For k = 1 to N Pick a random integer j from k to N Swap A[k] and A[j]我一遍又一遍地告訴我的一個(gè)常見錯(cuò)誤是:For k = 1 to N Pick a random integer j from 1 to N Swap A[k] and A[j]也就是說,不是從k到N選擇一個(gè)隨機(jī)整數(shù),而是從1到N中選擇一個(gè)隨機(jī)整數(shù)。如果你犯了這個(gè)錯(cuò)誤怎么辦?我知道由此產(chǎn)生的排列不是均勻分布的,但我不知道對(duì)于最終的分布有什么保證。特別是,有沒有人有關(guān)于元素最終位置的概率分布的表達(dá)式?
3 回答

慕沐林林
TA貢獻(xiàn)2016條經(jīng)驗(yàn) 獲得超9個(gè)贊
讓我們說吧
a = 1/N
b = 1-a
B i(k)是第th個(gè)元素
i
交換后的概率矩陣k
。即問題的答案“ 交換k
后的位置是i
什么?”。例如B 0(3)=(0 0 1 0 ... 0)
和B 1(3)=(a 0 b 0 ... 0)
。你想要的是每個(gè)k的B N(k)。K i是一個(gè)NxN矩陣,在第i列和第i行中有1,在其他地方為零,例如:
我我是單位矩陣,但是與該元素X = Y = I歸零。例如,對(duì)于i = 2:
一個(gè)我是
然后,
但是因?yàn)锽 N(k = 1..N)形成單位矩陣,所以任何給定元素i最后都在位置j的概率由矩陣的矩陣元素(i,j)給出:
例如,對(duì)于N = 4:
作為N = 500的圖表(顏色等級(jí)為100 *概率):
所有N> 2的模式都是相同的:
第k個(gè)元素最可能的結(jié)束位置是k-1。
的至少可能的終止位置為k為?<N * LN(2) ,位置1否則
添加回答
舉報(bào)
0/150
提交
取消