如何证明数组乱序的随机性能？

对于任意数组,数组中元素个数n >= 2，n为自然数。

如果可以证明经过这个算法将数组乱序，数组中每个元素出现在 n 个位置任意一个位置的概率都是 1/n,即可以说明随机性良好。

2.知识剖析

数组乱序以及证明

1.如何实现数组乱序

2.如何证明某个给定命题在整个（或者局部）自然数范围内成立

如何实现数组乱序

Fisher–Yates Shuffle

关于数组乱序，正确的解法应该是 Fisher–Yates Shuffle。

实现原理：遍历数组元素，将其与之前的任意元素交换。

如何证明某个给定命题在整个（或者局部）自然数范围内成立

数学归纳法

数学归纳法（Mathematical Induction, MI）是一种数学证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立。

最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步：

1.证明当n= 1时命题成立。

2.假设n=m时命题成立，那么可以推导出在n=m+1时命题也成立。（m代表任意自然数）

3.常见问题

常见的概率计算?

相互独立事件与互斥事件的区别和联系?

4.解决方案

常见的概率计算?

定理：设A、B是互不相容事件（AB=φ），则：P（A∪B）=P（A）+P（B）

条件概率：已知事件B出现的条件下A出现的概率，称为条件概率，记作：P(A|B) 条件概率计算公式： 当P(A)>0，P(B|A)=P(AB)/P(A) 当P(B)>0，P(A|B)=P(AB)/P(B)

乘法公式 P(AB)=P(A)×P(B|A)=P(B)×P(A|B)

相互独立事件

相互独立事件: 事件A(或B)是否发生对事件B(A)发生的概率没有影响，这样的两个事件叫做相互独立事件。

相互独立事件同时发生的概率P(A*B) =P(A) *P(B)

互斥事件

互斥事件:指的是不可能同时发生的两个事件。

例如：事件A和B的交集为空，A与B就是互斥事件，也叫互不相容事件。也可叙述为：不可能同时发生的事件。

如A∩B为不可能事件（A∩B=Φ），那么称事件A与事件B互斥，其含义是：事件A与事件B在任何一次试验中不会同时发生。

相互独立事件与互斥事件的区别和联系?

区别∶ 相互独立事件之间的发生互不影响，但可能会同时发生。 互斥事件是不可能同时发生的事件，即交集为零，但可能会产生相互影响。

联系∶ 相互独立事件可能是互斥事件也可能不是互斥事件，而互斥事件一定不是独立事件。

5.编码实战

关于数组乱序的一个小例子

6.扩展思考

如何使用数学归纳法证明数组乱序的随机性

证明：数组中元素个数n >= 2，n为自然数,经过该算法将数组乱序，数组中每个元素出现在 n 个位置任意一个位置的概率都是 1/n.

1.当n=2时,根据算法，显然有 1/2 的概率两个数交换，有 1/2 的概率两个数不交换，因此对 n = 2 的情况，元素出现在每个位置的概率都是 1/2，满足随机性要求。

2、假设n=m时，算法的随机性符合要求。事件C:当数组中有m个元素时，元素出现的每个位置。P(C)=1/m

事件A:元素出现在末尾位置。 P(A)=1/(m+1)

事件B:元素出现在非末尾位置。A、B为相互对立事件,P(B)=1-P(A)=m/(m+1)

在元素出现在非末尾位置的条件下，元素出现在其他m个位置的概率。P(BC)

根据概率计算的乘法法则P(AB)=P(A)×P(B|A)=P(B)×P(A|B)

P(BC)==P(B)×P(C|B)=P(C)×P(B|C)

事件B和事件C为相互独立事件

P(C|B)=P(C),P(B|C)=P(B)

综上所述,P(BC)=P(B)×P(C)=[m/(m+1)]×[1/m]=1/(m+1)

即可证明n=m+1

结论：对于任意大于等于2的自然数n，算法随机性均符合要求。

7.参考文献

鸣谢

感谢大家观看

BY : 田迪生