第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全,請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問題,去搜搜看,總會(huì)有你想問的

你從這個(gè)破碎的隨機(jī)洗牌中得到了什么分布?

你從這個(gè)破碎的隨機(jī)洗牌中得到了什么分布?

著名的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

  • 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)。

  • i是一個(gè)NxN矩陣,在第i列和第i行中有1,在其他地方為零,例如:

https://img1.sycdn.imooc.com//5d68e8c40001438001950121.jpg

  • 是單位矩陣,但是與該元素X = Y = I歸零。例如,對(duì)于i = 2:

https://img1.sycdn.imooc.com//5d68e8c60001378d01040088.jpg

  • 一個(gè)

https://img1.sycdn.imooc.com//5d68e8ca0001628c01140016.jpg

然后,

https://img1.sycdn.imooc.com//5d68e8cc00015e9e02110019.jpg

但是因?yàn)锽 N(k = 1..N)形成單位矩陣,所以任何給定元素i最后都在位置j的概率由矩陣的矩陣元素(i,j)給出:

https://img1.sycdn.imooc.com//5d68e8ce0001252601430016.jpg

例如,對(duì)于N = 4:

https://img1.sycdn.imooc.com//5d68e8d1000150fc01470089.jpg

作為N = 500的圖表(顏色等級(jí)為100 *概率):

https://img1.sycdn.imooc.com//5d68e8d30001308a04800480.jpg

所有N> 2的模式都是相同的:

  • 第k個(gè)元素最可能的結(jié)束位置是k-1。

  • 至少可能的終止位置為k?<N * LN(2) ,位置1否則


查看完整回答
反對(duì) 回復(fù) 2019-08-30
  • 3 回答
  • 0 關(guān)注
  • 720 瀏覽
慕課專欄
更多

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購(gòu)課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)