基础概率题

圆内随机选取一点¶

在半径为1的圆中随机选取一点

在[0, 2pi)间随机选取一个角度，然后在[0, R]中选取一个长度，即可以确定一个点。选长度的时候，选取的概率要和离圆心的距离成正比

链接是按长度选取点的很好的思路，推导分三步

如何在一个平行四边形内随机选一点? 两条边AB和AC上各选一点E和F，然后构造平行四边形AEFG，G即为随机选取的在平行四边形之内的点
如何在一个等腰三角形内随机选取一点? 先在平行四边形内选取一点，如果超过对角线，返回与对角线对称点即可
确定角度后，如何按长度概率返回点? 确定角度后，可以看做在一个很窄的三角形内选取一点，这时两条边平行，选取点位置就是两次选取[0, 1]内随机值之和，超过1再折回即可。可以这么想，将一个平行四边形ABCD的AB和AC边(AB=AC)捏在一起，就成了一个 $2\times|AB|$ 长的直条

Python代码如下

from random import *
import math

def randPointInCircle():
    theta = random() * 2 * math.pi
    l = random() + random()
    l = l if l <= 1 else 2 - l
    return (l * math.cos(theta), l * math.sin(theta))

三段组三角形¶

一根木棒，截成三截，组成三角形的概率是多少

答案: ¼

几何概率，第一次截长度a下来，第二次截b，剩下 $c=1-a-b$ ，则所有可能为 $a+b=1$ 的线围成的左下角三角形，面积为½。同时组成三角形要求为

$max(b,c)-min(b, c) < a < b + c=l-a$

第一次截的位置必须在(0, l/2)内，设第一次截x，第二次在剩下的中点截一定可以，而从中点偏移d，两段差则为2d，有 $2d<x$ ，所以第二次只能在x长的区域内选点，即为 $a+b=l$ 和x轴围成的区域，重叠部分为⅛的三角形，故概率为¼

抛色子期望¶

答案: 6

抛一个六面的色子，连续抛直到抛到6为止，问期望的抛的次数是多少

设期望为x，则有

$x=\frac{1}{6}+\frac{5}{6}\times(1+X)$

$X=6$

涂球期望时间¶

一个木桶里面有M个白球，每分钟从桶中随机取出一个球涂成红色（无论白或红都涂红）再放回，问将桶中球全部涂红的期望时间是多少

答案: $\frac{M}{1}+\frac{M}{2}+...+\frac{M}{M}$

设有N个红球时涂球时间为 $T_N$ ，则有

$T_N=\frac{N}{M}(1 + T_N)+\frac{M-N}{M}(1+T_{N-1})$

$T_N=\frac{M}{M-N}+T_{N-1}$

又有 $T_0=0$ ，故

$T_M=\frac{M}{1}+\frac{M}{2}+...+\frac{M}{M}$

宝剑升级期望¶

你有一把宝剑。每使用一个宝石，有50%的概率会成功让宝剑升一级，50%的概率会失败。如果宝剑的级数大于等于5的话，那么失败会使得宝剑降1级。如果宝剑的级数小于5的话，失败没有效果。问题是：期望用多少个宝石可以让一把1级的宝剑升到9级

答案: 36次

$a[i]$ 表示从第i-1级升到第i级期望使用的宝石数量

当 $i\le5$ 时，因为不会降级，则期望的数量均为2，即 $a[2] = a[3] = a[4] = a[5] = 2$
当 $i>5$ 时，因为会降级，成功时一个宝石就够了，不成功时需要倒退一级，需要先使用 $a[i-1]$ 个宝石先回到 $i-1$ 级，再使用 $a[i]$ 个宝石升到第 $i$ 级，即 $a[i] = \frac{1}{2} + (1 + a[i-1] + a[i]) \times \frac{1}{2}$ 。即 $a[i] = a[i-1] + 2$

可知， $a[6]= 4, a[7] = 6, a[8] = 8, a[9] = 10$

则1级到9级需要的宝石数为 $a[2]+…+a[9] = 36$

抛硬币吃苹果¶

有一苹果，两个人抛硬币来决定谁吃这个苹果，先抛到正面者吃。问先抛这吃到苹果的概率是多少

答案: $\frac{2}{3}$

设为 $x$

$x=\frac{1}{2}+\frac{1}{2}(1-x)$

$x=\frac{2}{3}$

选球游戏¶

有50个红色弹球和50个蓝色弹球，分配在两个罐子里，随机选出一个罐子然后从里面随机选出一个弹球，怎么给出红色弹球最大的选中机会? 在你的计划里，得到红球的几率是多少

答案: 一个放一个红球，一个放49个红球和50个蓝球

$\frac{R_1}{R_1+B_1}+\frac{R2}{R2+B2}$

重点是上式中两项要么都是 $\frac{1}{2}$ ，要么一个大于 $\frac{1}{2}$ ，一个小于 $\frac{1}{2}$

前者，结果为 $\frac{1}{2}$

后者，大于 $\frac{1}{2}$ 的最大可能为 $\frac{1}{2}$ ，小于 $\frac{1}{2}$ 最大为 $\frac{49}{99}$ ，恰巧两者都可以实现，故最大概率为

$(1+\frac{49}{99})/2=0.7475$

12个球称3次找重量不一样¶

有一架天平和12个球，其中一个球重量和其它不一样，

分成三堆，称两堆 $A_1A_2A_3A_4$ 和 $B_1B_2B_3B_4$

如果一样，那说明 $C_1C_2C_3C_4$ 里有球重量不一样，称 $C_1$ 和 $C_2$
- 一样重，称 $C_1$ 和 $C_3$ ，如果不一样重， $C_3$ 是不一样的球，一样重，则 $C_4$ 是
- 不一样重，称 $C_1$ 和 $C_3$ ，一样重， $C_2$ 是不一样的球，不一样重， $C_1$ 是
不一样重，不失普遍性，设 $A_1A_2A_3A_4$ 更重，称 $A_1B_2B_3B_4$ 和 $B_1C_2C_3C_4$
- 如果 $A_1B_2B_3B_4$ 重，要么 $A_1$ 重，要么 $B_1$ 轻，称 $A_1$ 和 $C_1$ 即可
- 一样重，说明 $A_2A_3A_4$ 中一个重，称 $A_2$ 和 $A_3$ 即可
- $B_1C_2C_3C_4$ 重，说明 $B_2B_3B_4$ 中有一个轻，称 $B_2$ 和 $B_3$ 即可

秘书选择问题 Secretary Problem¶

要聘请一名秘书，有 n 个应聘者。每次面试一人，面试后就要及时决定是否聘他，如果当时决定不聘他，他便不会回来。面试后总能清楚了解应聘者的合适程度，并能和之前的每个人做比较。问什么样的策略，才使最佳人选被选中的概率最大

思路是，先用前一部分candidate作为观测批，不选择这批中任何人呢，然后根据这部分的观测结果在之后做出选择

比较经典的方法是，前k个人一定拒绝，然后之后遇到比这k个人都好的candidate时选择此人，否则就选最后一个

以下是推导过程，第 $i>k$ 个人是最佳的人的概率是 $\frac{1}{n}$ ，能选到他的情况即前面 $i-1$ 个人的最好candidate出现在前 $k$ 个人里，概率是 $\frac{k}{i-1}$ ，总共概率是

$\sum_{i=k+1}^{n}\frac{1}{n}\times \frac{k}{i-1}=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$

当n趋于无穷时，可以近似等于下式

$\frac{k}{n}\sum_{i=k}^{n}\frac{1}{i}=\frac{k}{n}\sum_{i=k}^{n}\frac{n}{i}\times\frac{1}{n}$

这里可以转成积分，使 $t=\frac{i}{n}$ ，则 $dt=\frac{1}{n}$

上式等于

$\frac{k}{n}\int_{i=k/n}^1\frac{1}{t}dt=-\frac{k}{n}ln(\frac{k}{n})$

记 $x=\frac{k}{n}$ ，即为 $-xlnx$

上式求导，为 $-(lnx+1)$ ，当 $x=\frac{1}{e}$ 时等于0，取最大值

故以上问题解法就是前1/e的canddidate直接淘汰，之后发现有优于前1/e的candidate即录用