算法基础-随机过程

未婚夫问题

假如现在有n个求婚者,被分别标记为1,2,3…N,她们将按顺序被你面试,你每次都必须选择接受或不接受,一旦你接受了其中一个,那么就无法面试后面的人.因此你必须在无法面试后面的人的情况下选出当下最优者.

由于无法预知这些求婚者的平均情况,所以我们必须先面试前k个人,从第k+1个人开始,一旦发现更优者就立即选择她.

这个问题中有三个主要的关键变量

顾名思义,最优点就是最佳求婚者出现的位置,我们的最终目标是找到最优点,如果不能,那就尽可能让找到最优点的概率最大

在停止点 k 之前的所有求婚者都将被拒绝,而她们之间的最优者将被作为面试之后的求婚者的标准,如果发现比她们之间的最优者更优的人,就立即接受她

在最优点 x 之前的最佳求婚者出现的位置就是次优点.我们希望次优点 λ 出现在停止点 k 之前,而最优点 x 出现在 k 之后

当最优点 x 出现在停止点 k 之前时,计算没有意义,因为最优点已经被排除了

当最优点 x 出现在停止点 k 之后时,总共有(n-k)个情况,由于 x 出现的位置是随机的,总共有 n 个位置,所以所有情况发生的概率都是 $\frac 1n$

只有次优点 λ 出现在前 k 个位置时,我们才能准确地找到最优点 x ,而次优点出现在前k个位置的概率为 $\frac{k}{x-1}$

因此我们可以计算出找到最佳求婚者的概率

P=\sum\limits_{x=k+1}^{n}\frac 1n \cdot \frac k{x-1}=\frac kn \sum\limits_{x=k}^{n-1}\frac 1x

我们可以使用定积分得到 $P$ 的上下界

\int_k^n\frac{dx}{x} \leq \sum\limits_{x=k}^{n-1}\frac 1x \leq \int_{k-1}^{n-1}\frac {dx}x

这两个定积分非常简单,因此这里直接给出结果

\frac kn \cdot \ln \frac nk \leq P \leq \frac kn \cdot \ln \frac{n-1}{k-1}

如果希望 $P$ 尽可能大,则需要 $P$ 的下界尽可能大,于是我们对 $k$ 求导并令导数为0

\frac{dP}{dk}=\frac{\ln \frac nk-1}{n}=0

解方程,得 $k=\frac ne$

显然当 $k=\frac ne$ 时, $P$ 取到最大值 $36.8\%$

因此对于任意的n,只需要将前 $36.8\%$ 的数据作为参考,就能以最大概率在之后选出最优解

如果想要验证上面的问题,就需要用到随机排列的数组.

均匀随机排列是指产生1~n的每一种排列的概率完全相同,即产生某一种排列的概率为全排列的倒数

给定序列[1,2,3, … ,n],通过将这些数字随机地变换以使数组随机化,从而达到均匀随机排列.优先级数组就是一种得到均匀随机排列得方法

对数组A,给定另一个数组P,在P中随机地生成一个大范围整数,并根据P[i]的大小来调整A[i]的位置.例如A=[1,2,3,4,5],而P=[13,62,6,19,52],那么调整后的序列就是[2,5,4,1,3]

但是这种方法有一个缺陷,即必须确保数组P的每一项都唯一,幸运的是,你只需要扩大随机数范围就可以尽可能保证不出现重复

该方法代码较为简单,故不做演示

设 $E_i$ 表示第 i 个元素被分配到第 i 个位置,则每个元素都被分配到自己对应的位置的概率为

P=\bigcap\limits_{i=1}^nP(E_i)

显然当 $i = 1$ 时, $E_1=\frac 1n$ ,因为总共有n个元素.当 i ≥ 2 时,

P(E_i)=P\left(E_i|\bigcap\limits_{k=1}^{i-1}E_k\right)

所以,在前 i-1 个元素的位置都已经确定的情况下, $P(E_i)=\frac{1}{n-i+1}$ ,于是我们得到

P=\bigcap\limits_{i=1}^{n}P(E_i)=\prod\limits_{i=1}^{n}\frac 1i=\frac 1{n!}

所以,使用优先级数组方法获得等同排列的概率恰好为全排列的倒数

实际上,对于数组A的任意一个随机排列S,只需要修改一下E的定义,我们都可以使用上述方法证明出 A[i] 恰好被分配到 S 数组中的指定位置 j 的概率为 $\frac 1{n!}$