Math Quiz 1

问题一 集卡片

有n张卡片，每次等概率随机获取1张，问期望多少张卡片可以将所有卡片集齐？
Ans
$$ \frac{n}{n}+\frac{n}{n-1}+\frac{n}{n-2}+.….+\frac{n}{1}= \sum^n_{i=1}{\frac{n}{i}}$$
注：离散随机变量的一切可能值与其对应的概率P的乘积之和称为数学期望

问题二 随机数生成器

你有一个不均匀的随机数生成器，0的概率为p，1的概率为1-p，p未知。
设计一个算法，用这个不均匀的随机数生成器生成一个均匀的随机数生成器，即生成0和1的概率均为$\frac{1}{2}$。
Ans
我们每次用不均匀的随机数生成器依次生成2个数，如果是00和11，我们忽略，然后继续生成2个数，直到生成01和10为止。
如果生成01，我们输出0；如果生成10，我们输出1。这两种情况概率均为p(1-p)

问题三 完全信息的结婚问题

有n次找男友的机会，每个男友给你的满意度是1,2,…,m中等概率随机的一个数
你从1到n换男友，只有成为男友才能知道男友给你的满意度，换了男友后不能再找回来
那你可以再任意的时候选择和当前的男友结婚，该男友的满意度就是你最终的辛福指数。
假设你足够渣，求你期望能获得的辛福指数。
$$n,m≤10^7$$
Ans
令$f_i$表示你还有i次找女友的机会时的期望幸福指数
$f_1=\frac{1+m}{2}$
$f_i=\frac{\sum^m_{i=1}max({f_{i-1},i})}{m}$
选择i，继续碰运气，选择$f_{i-1}$，结婚; 时间复杂度O(n)。

问题四 不完全信息的结婚问题

有n次找男友的机会，每个男友给你的满意度未知（但是满足随机分布）
你从1到n换男友，只有成为男友才能知道男友给你的满意度，换了男友后不能再找回来
那你可以再任意的时候选择和当前的男友结婚，该男友的满意度就是你最终的辛福指数。
你需要采用一种策略，使得你找到最好的男友结婚的概率最大。
Ans
n=3时的最优策略？
第一个男友先pass，当第二个男友比第一个要好时，选择结婚；反之选择下一个。
一共有6种情况：

123 没找到
132 找到
213 找到
231 找到
312 没找到
321 没找到

概率为$\frac{1}{2}$
策略：先观察前k个男友，然后全部分手。对剩下的女友如果比前k个女友都好，就结婚。
$$ P(k)= \frac{1}{n}+\frac{1}{n}\times\frac{k}{k+1}+\frac{1}{n}\times\frac{k}{k+2}+…+\frac{1}{n}\times\frac{k}{n-1}=\frac{k}{n}\sum^{n-1}_{i=k}\frac{1}{i} $$

令$k=\frac{k}{n}$,得$P(k)=\frac{k}{n}\sum^{n-1}_{i=k}\frac{1}{i}=x\int^1_x\frac{1}{x}dt=-xlnx$

$P’(k)=-(1+lnx)=0$,有$x=\frac{1}{e}=37$%

此时，$P(k)=-\frac{1}{e}ln\frac{1}{e}=\frac{1}{e}=37$%

最佳策略：先观察37%的男友，然后全部分手，接下来，一旦遇到一个比前面男友都要好的，直接结婚。如果你找男友的时期时15-35岁，那么22之前就是观察期，不要结婚，接下来遇到更好的直接结婚。

问题五 最大间距

有n个乱序数$\alpha_1,…,\alpha_n$，求排序之后，相邻元素之间的最大差值
$n≤10^7,1≤\alpha_1,…,\alpha_n≤10^{18}$
要求O(n)
Ans
把n个数放在n+1个桶里，其中最小值min放在第1个桶，最大值max放在第n+1个桶，每个桶都负责放$gap=\frac{max-min}{n+1}$范围的数字
根据鸽笼原理，必然有一个空桶。同一个桶内的差值必然小于gap，而间隔一个空桶的差值必然大于gap，故我们不用考虑一个桶内的差值，只需要考虑不同桶之间的差值。
记录每个桶中的最大值和最小值，遍历桶，依次用当前桶的最小值减去上一个非空桶的最大值判断即可。