为了账号安全,请及时绑定邮箱和手机立即绑定

你从这个破碎的随机洗牌中得到了什么分布?

你从这个破碎的随机洗牌中得到了什么分布?

桃花长相依 2019-08-30 17:11:14
着名的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/N

  • b = 1-a

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

  • i是一个NxN矩阵,在第i列和第i行中有1,在其他地方为零,例如:

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

  • 是单位矩阵,但是与该元素X = Y = I归零。例如,对于i = 2:

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

  • 一个

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

然后,

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

但是因为B N(k = 1..N)形成单位矩阵,所以任何给定元素i最后都在位置j的概率由矩阵的矩阵元素(i,j)给出:

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

例如,对于N = 4:

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

作为N = 500的图表(颜色等级为100 *概率):

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

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

  • 第k个元素最可能的结束位置是k-1

  • 至少可能的终止位置为kķ<N * LN(2) ,位置1否则


查看完整回答
反对 回复 2019-08-30
  • 3 回答
  • 0 关注
  • 621 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信