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

着名的Fisher-Yates shufflealgorithm可以用来随机排列长度为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中选取一个随机整数。

如果你犯了这个错误会怎么样? 我知道由此产生的排列不是均匀分布的,但是我不知道什么样的结果会是什么保证。 特别是,有没有人有一个概率分布在元素的最终位置的expression?

实证方法。

让我们在Mathematica中实现错误的algorithm:

 p = 10; (* Range *) s = {} For[l = 1, l <= 30000, l++, (*Iterations*) a = Range[p]; For[k = 1, k <= p, k++, i = RandomInteger[{1, p}]; temp = a[[k]]; a[[k]] = a[[i]]; a[[i]] = temp ]; AppendTo[s, a]; ] 

现在得到每个整数在每个位置的次数:

 r = SortBy[#, #[[1]] &] & /@ Tally /@ Transpose[s] 

让我们在结果数组中取三个位置,并绘制每个整数在该位置的频率分布:

对于位置1,频率分布是:

在这里输入图像描述

对于位置5(中)

在这里输入图像描述

而对于位置10(最后):

在这里输入图像描述

在这里您可以将所有位置的分布绘制在一起:

在这里输入图像描述

在这里你有更好的统计超过8个职位:

在这里输入图像描述

一些观察:

  • 对于所有位置,“1”的概率是相同的(1 / n)。
  • 概率matrix相对于大的反对angular线是对称的
  • 所以,最后一位数字的概率也是一致的(1 / n)

你可以看到从同一点(第一个属性)和最后一个水平线(第三个属性)开始的所有行的属性。

第二个属性可以从以下matrix表示示例中看出,其中行是位置,列是占有者编号,颜色代表实验概率:

在这里输入图像描述

对于100x100matrix:

在这里输入图像描述

编辑

为了好玩,我计算了第二个对angular元素的精确公式(第一个是1 / n)。 其余的可以完成,但是这是很多工作。

 h[n_] := (n-1)/n^2 + (n-1)^(n-2) n^(-n) 

从n = 3到6validation的值({8 / 27,57 / 256,564 / 3125,7105 / 46656})

编辑

在@wnoise的答案中稍作一般的显式计算,我们可以得到更多的信息。

用p [n]代替1 / n,所以计算保持不被评估,例如对于n = 7的matrix的第一部分(点击查看更大的图像)。

在这里输入图像描述

在与其他n值的结果进行比较之后,让我们确定matrix中的一些已知整数序列:

 {{ 1/n, 1/n , ...}, {... .., A007318, ....}, {... .., ... ..., ..}, ... ...., {A129687, ... ... ... ... ... ... ..}, {A131084, A028326 ... ... ... ... ..}, {A028326, A131084 , A129687 ... ....}} 

你可以在奇妙的http://oeis.org/上find这些序列(在某些情况下有不同的符号);

解决一般问题比较困难,但我希望这是一个开始

你提到的“常见错误”是随意转换的洗牌。 这个问题在Diaconis和Shahshahani 的随机置换生成随机排列(1981)中有详细的研究 。 他们对停工时间和趋同性进行了全面的分析。 如果您无法获得该文件的链接,请给我发一封电子邮件,我可以向您转发一份副本。 这实际上是一个有趣的阅读(与大多数Persi Diaconis的论文一样)。

如果数组有重复的条目,则问题稍有不同。 作为一个无耻的插件,这个更一般的问题是由我自己,Diaconis和Soundararajan在Riffle Shuffling(2011)的“经验法则”附录B中讨论的 。

我们说

  • a = 1/N
  • b = 1-a
  • B i (k)是第i个元素交换后的概率matrix。 即对于“ i换掉后在哪里?”这个问题的答案。 例如B 0 (3)= (0 0 1 0 ... 0)和B 1 (3)= (a 0 b 0 ... 0) 。 你想要的是每N个 B(k)。
  • K i是一个NxNmatrix,在第i列和第i行中为1,在其他地方为零,例如:

kappa_2

  • 我是单位matrix,但元素x = y = i归零。 例如,对于i = 2:

I_2

Ai = bIi + aKi

然后,

B_N

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

解矩阵

例如,对于N = 4:

B_4

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

B_500

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

  • 第k个元素最可能的结束位置 是k-1
  • 对于k <N * ln(2)最不可能的结束位置是k ,否则位置1

我知道我之前看过这个问题

“ 为什么这个简单的洗牌algorithm产生有偏见的结果呢?有什么简单的原因? ”在答案中有很多好东西,特别是在“编码恐怖”中杰夫·阿特伍德的博客链接。

正如你可能已经猜到的那样,根据@belisarius的回答,确切的分配高度依赖于要洗牌的要素数量。 这里是阿特伍德6层甲板的情节:

在这里输入图像描述

多么可爱的问题! 我希望我有一个完整的答案。

Fisher-Yates很好分析,因为一旦它决定了第一个元素,它就离开它。 有偏见的人可以反复交换一个元素进出任何地方。

我们可以用与马尔可夫链相同的方式来分析这一点,通过描述作为随机转移matrix的线性作用于概率分布的行为。 大多数元素都是孤立的,对angular线通常是(n-1)/ n。 在通过k时,当他们不被孤立时,它们与元素k交换(或者如果元素k是随机元素)。 这是行或列k中的1 /(n-1)。 行和列k中的元素也是1 /(n-1)。 当k从1到n时,将这些matrix相乘是很容易的。

我们知道最后一个地方的元素原本就是在任何地方,因为最后一个地方和其他地方的地方相同。 同样,第一个元素将被放置在任何地方。 这种对称性是因为转置颠倒了matrix乘法的顺序。 事实上,matrix在行i与列(n + 1 – i)相同的意义上是对称的。 除此之外,这些数字并没有显示出太多明显的模式。 这些确切的解决scheme确实与belisarius运行的模拟结果一致:在第i个时隙中,获得j的概率随着jboost到i而下降,在i-1时达到最低值,然后跳跃到i的最高值,直到j达到n。

在Mathematica中,我生成了每一步

  step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]] 

(我没有在任何地方find它,但是使用了第一个匹配规则。)最终的转换matrix可以用下面的公式计算:

 Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]] 

ListDensityPlot是一个有用的可视化工具。

编辑(belisarius)

只是一个确认。 下面的代码给出了与@ Eelvex的答案相同的matrix:

 step[k_, n_] := Normal[SparseArray[{{k, i_} -> (1/n), {j_, k} -> (1/n), {i_, i_} -> ((n - 1)/n)}, {n, n}]]; r[n_, s_] := Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]; Last@Table[r[4, i], {i, 1, 4}] // MatrixForm 

关于Fisher-Yates shuffle的维基百科页面有一个在这种情况下会发生什么的描述和例子。

你可以使用随机matrix来计算分布。 让matrixA(i,j)描述原来在位置i的卡片结束于位置j的概率。 那么第k个交换有一个由Ak(i,j) = 1/N给出的matrixAk Ak(i,j) = 1/N如果i == k或者j == k ,(位置k中的卡片可以在任何地方结束,任何卡片都可以结束于位置k (N-1)/ N),所有其他元素将保持在相同的位置,并且所有其他元素为零Ak(i,i) = (N - 1)/N等于概率), Ak(i,i) = (N - 1)/N (N-1)/ N 。

然后完整的混洗的结果由matrixAN ... A1的乘积给出。

我希望你正在寻找一个概率的代数描述; 你可以通过扩展上面的matrix产品来获得一个,但是我想它会相当复杂!

更新:我刚刚发现了上面的wnoise的等效答案! 糟糕!

我进一步研究了这一点,结果发现这个分布已经被详细研究了。 感兴趣的原因是因为这个“破碎的”algorithm已经(或已经)在RSA芯片系统中使用了。

在半随机转换中 ,Elchanan Mossel,Yuval Peres和Alistair Sinclair研究了这个和更普遍的洗牌类。 这篇论文的结果似乎是,为了实现近乎随机的分配,需要log(n)破碎的洗牌。

三个伪随机洗牌Aequationes Mathematicae ,22,1981,268-292)的偏见中,Ethan Bolker和David Robbins分析了这个洗牌,并且确定一遍之后的总均匀距离为1,表明它不是很好随机的。 他们也给予asympotic分析。

最后,Laurent Saloff-Coste和Jessica Zuniga发现了他们研究非均匀马尔可夫链的一个很好的上界。

这个问题是乞求一个交互式的视觉matrix图分析破碎洗牌提到。 这样的工具是在页面上它会随机? – 为什么随机比较是坏的迈克·博斯托克。

博斯托克汇集了一个分析随机比较的优秀工具。 在该页面的下拉列表中,selectnaïveswap(随机随机)以查看破碎的algorithm及其生成的模式。

他的页面是信息性的,因为它可以让人看到逻辑上的改变对洗牌数据的直接影响。 例如:

这个使用非均匀和非常偏向的混洗的matrix图是使用一个简单的交换(我们从“1到N”中select)用这样的代码生成的:

 function shuffle(array) { var n = array.length, i = -1, j; while (++i < n) { j = Math.floor(Math.random() * n); t = array[j]; array[j] = array[i]; array[i] = t; } } 

有偏见的洗牌

但是,如果我们实现一个无偏置的随机播放,我们可以从“k到N”中select一个这样的图表:

在这里输入图像描述

分配是统一的,并且由代码产生,例如:

 function FisherYatesDurstenfeldKnuthshuffle( array ) { var pickIndex, arrayPosition = array.length; while( --arrayPosition ) { pickIndex = Math.floor( Math.random() * ( arrayPosition + 1 ) ); array[ pickIndex ] = [ array[ arrayPosition ], array[ arrayPosition ] = array[ pickIndex ] ][ 0 ]; } } 

迄今为止所给出的优秀答案都集中在分配上,但你也问“如果你犯这个错误会发生什么?” – 这是我还没有看到的答案,所以我会解释一下:

Knuth-Fisher-Yates shufflealgorithm从n个元素中选出1个,然后从n-1个剩余元素中选出1个,等等。

您可以使用两个数组a1和a2来实现它,您可以从a1中移除一个元素并将其插入到a2中,但是该algorithm可以实现(也就是说,它只需要一个数组),如下所述(Google:“ Shuffling Algorithms Fisher-Yates DataGenetics“)。

如果不删除元素,可以随机select它们,从而产生偏向的随机性。 这正是你所描述的第二个例子。 第一个例子是Knuth-Fisher-Yatesalgorithm,它使用一个从k到N的游标variables,它记住哪些元素已经被使用了,因此避免了多次拾取元素。