阿里笔试编程题-相亲的次数问题

Expection of Dating Problem (From Alibaba)

作者 Leon Dong 日期 2017-05-28
阿里笔试编程题-相亲的次数问题

问题描述

一个未婚男青年要和N个女孩相亲,由于他不记录已经相亲过的女孩,而是每一次随机从这N个女孩中挑选一个进行相亲。由于相亲的女孩可能是已经相亲过的,那么现在的问题就是他平均要相亲多少次,才能将所有的女孩都相亲一遍(期望)。

问题分析

其实呢,这道题只是一道披着编程外表的数学题。他就是要求男孩相亲次数的期望。假设用随机变量$X$表示男孩按上述方式相亲完所有女孩的所需要的次数,那么题目要求的就是$E(X)$,数学上叫做随机变量的期望。

对于离散的随机变量$X$来说,要求他的期望$E(X)$的一般方法就是根据定义来求。也就是说,计算出$X$的每一个可能的取值$x_i$以及对应的概率$p_i$,接下来我们就可以得到它的期望为
$$
E(X) = \sum_{i} {x_i \cdot p_i}
$$
我们可以尝试以这个方式去求得上个问题的期望。首先,我们需要分析出变量$X$所有可能的取值范围。要相亲完N个女孩,考虑最好的情况,这个未婚男青年每次随机挑选到的刚好就是他还没有相亲的,那么他相亲的次数至少也为$N$。然而,这个男青年最多需要多少次,也就是说随机变量$X$的最大值可能是多少?通过简单的分析就可以知道,变量$X$的最大取值是趋于正无穷的,也就是说为了求得期望,我们可能要求一个数学级数,即$E(X) = \sum_{i=N}^{\infty} {i\cdot p_i}$。

先不说这个级数如何求取的问题,这样求解期望的最大问题在于每一个值$i$对应的概率$p_i$是非常难求的。举个例子来说,N个女孩,男青年总共用了$2N$次完成相亲的概率$p_{2N}$是多少?这里面的可能性太多了,就算你能求出来共有$M$中可能,那么$p_{2N} = M / N^{2N}$,这里的运算很容易就溢出了,计算结果根本无法保证精确性。

问题求解

为了正确的解决这个问题,我们需要利用期望函数$E$的线性性质来解决该问题。简单的来说,如果有一个随机变量$X = w_1 Y_1 + w_2 Y_2$,那么$E(X) = w_1E(Y_1) + w_2E(Y_2)$,其中$w_1,w_2$是常数。值得一提的是,这里面我们不需要变量$Y_1$和$Y_2$是相互独立的,哪怕他们相关期望的线性性质也依旧成立。

所以,我们将上面的随机变量$X$进行拆分。首先定义随机变量$Y_i$代表当已经相亲的人数有$i-1$人时,每次随机选一个人相亲,相亲到一个没相亲过的人所需要的次数,所以我们就有了如下的关系
$$
X = Y_1 +Y_2 + … + Y_N
$$
仔细体味一下上面的关系,它是为什么成立的,在这你就不具体分析了。

有了这个公式之后,接下来的问题就是如何求随机变量$Y_i$的期望了。对于随机变量$Y_i$,我们可以分析出他的取值的可能性为$[1,\infty]$,这意味着求取$Y_i$的期望是一样要算级数。不过算级数可以通过数学工具,重点是在这种情况下,$Y_i$的每一种取值$y$对应的概率$p_y$很好求得。

当已经相亲的人数有$i-1$人时,每次随机选一个人相亲,那么选出没有相亲过的人的概率即为$\frac{N-i+1}{N}$,选出相亲过的人的概率为$\frac{i-1}{N}$,令
$$
p = \frac{N-i+1}{N},q = \frac{i-1}{N}
$$
那么这就是一个二项分布,且$y$对应的概率$p_y= q^{y-1}\cdot p$。也就是说前$y-1$次都选的是已经相亲过的,第$y$次选到了一个没有相亲过的。

根据以上的推导,我们可以得到
$$
E(Y_i) = \sum_{y = 1}^{\infty} y\cdot q^{y-1}\cdot p
$$
为了求得该级数的值其实很简单,利用高中的知识就足够了。首先在公式的两边同时乘以$q$,我们得到
$$
qE(Y_i) = \sum_{y = 1}^{\infty} (y-1)\cdot q^{y-1}\cdot p
$$
将上面两个式子相减,得到
$$
(1-q)E(Y_i) = p \cdot \sum_{y = 1}^{\infty} q^{y-1} = p \frac{1 \cdot (1-q^{\infty})}{1-q} = \frac{p}{1-q}
$$
所以我们可以得到
$$
E(Y_i) = \frac{p}{(1-q)^2} = \frac{1}{p}
$$

所以,到此时,我们就可以很轻松的求得$X$的期望
$$
E(X) = E(Y_1) +E(Y_2) + … +E(Y_N)= \frac{1}{\frac{N}{N}} + \frac{1}{\frac{N-1}{N}} + \frac{1}{\frac{N-2}{N}} + … +\frac{1}{\frac{1}{N}}
$$
接下来就是变成求一下上面这个公式的值了,基本上C语言10行以内就解决了,求出来的结果精度较高且不会溢出。


Please Indicate the Source When Reproduce
转载请注明出处