一. 几何

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

• 方法1: 在x轴[-1,1]，y轴[-1,1]的正方形随机选取一点，如果此点在圆内，则即为所求的点。如果不在圆内，则重新随机直到选到了为止。
• 方法2: 从[0, 2*pi)随机选取一个角度，再在这个方向的半径上随机选取一个点。但半径上的点不能均匀选取，选取的概率要和离圆心的距离成正比，这样才能保证随机点在圆内是均匀分布的。

二. 概率

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

• 设第一段截 x，第二段截 y，第三段 1 - x - y。考虑所有可能的截法。
• 可能的截法中必须保证三条边都是正数且小于原来边长，则有0 < x < 1，0 < y < 1，0 < 1 - x - y < 1，画图可知，(x,y)必须在单位正方形的左下角的半个直角三角形里，面积为1/2。
• 然后考虑能形成三角形的截法。首先要满足刚才的三个条件0 < x < 1，0 < y < 1，0 < 1 - x - y < 1，然后必须符合三角形的边的要求，即两边之和大于第三边，x + y > 1 - x - y，x + 1 - x - y > y，y + 1 - x - y > x，化简即得0 < x < 1/2，0 < y < 1/2，1/2 < x + y < 1画图可知，此时(x,y)必须在边长为 1/2 的三角形的右上角的半个直角三角形里，面积为1/8。于是最终概率为 (1/8) / (1/2) = 1/4。

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

• 给所有的抛硬币操作从1开始编号，显然先手者只可能在奇数 (1,3,5,7…) 次抛硬币得到苹果，而后手只可能在偶数次(2,4,6,8…) 抛硬币得到苹果。
• 设先手者得到苹果的概率为 p，第1次抛硬币得到苹果的概率为 1/2，在第3次 (3,5,7…)以后得到苹果的概率为 p/4（这是因为这种只有在第1次和第2次抛硬币都没有抛到正面（概率为1/4=1/2*1/2）的时候才有可能发生，而且此时先手者在此面临和开始相同的局面）。
• 所以可以列出等式p=1/2+p/4，解得p=2/3。

三. 期望

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

• 因为每次抛到6的概率相等，都是1/6，于是期望的次数就是1/(1/6)=6次。
• 假设期望的次数为E。考虑第一次抛，如果已经抛到6了（概率为1/6），那么就不用再抛了。如果没抛到6（概率为5/6），那么还需要继续抛，可是还要抛多少次呢？显然，现在开始知道抛到6的次数仍然是E，但是刚刚已经抛了一次了于是可以得到这个等式E = 1 * 1/6 + (1 + E) * 5/6，解得 E = 6。即期望的次数为6次。

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

• 令桶中有i个红球后再把全部球涂红的期望时间为 a[i]，此时再取出一个球，如果是红色的（概率为i/m），则直接放回，且剩余的期望时间仍是 a[i]。
• 如果是白色的（概率为1-i/m），则涂红后放回，剩余的期望时间为a[i+1]，则a[i] = (1 + a[i]) * i/m + (1 + a[i+1]) * (1 – i/m)即 　　a[i] = a[i+1] + m/(m-i)显然，有a[m] = 0可以解得 a[0] = m/m + m/(m-1) + … + m/1 + 0

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

• 用 a[i] 表示从第 i-1 级升到第i级期望使用的宝石数量。
• 当 i<=5 时，因为不会降级，则期望的数量均为 2，即 a[2] = a[3] = a[4] = a[5] = 2
• 当 i>5 时，因为会降级，成功时一个宝石就够了，不成功时需要倒退一级，需要先使用 a[i-1]个宝石先回到 i-1 级，再使用 a[i] 个宝石升到第i级，即 a[i] = 1 * 1/2 + (1 + a[i-1] + a[i]) * 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。

4. 平均要取多少个(0,1)中的随机数才能让和超过 1

e 次， 其中 e 是自然对数的底

• 首先思考几个简单的问题:
  1. 任取 2 个 0 到 1 之间的实数, 它们的和小于 1 的概率是多少?
     满足 x+y<1 的点 (x, y) 占据了正方形 (0, 1) * (0, 1) 的一半面积, 因此这两个实数之和小于1的概率为 1/2=1/2!
  2. 任取 3 个 0 到 1 之间的实数, 它们的和小于 1 的概率是多少?
     3 个数之和小于 1 的概率是 1/6, 它是平面 x+y+z=1 在单位立方体中截得的一个三棱锥, 这个 1/6 可以例用截面与底面的相似比关系, 通过简单的积分求得:
     
  3. 4 个 0 到 1之间的随机数的和小于 1 的概率就等于四维超立方体一角的"体积", 它的"底面"是一个体积为 1/6 的三棱锥, 在第四维上对其进行积分便可得到其"体积":
     
  4. 以此类推, n 个 0 到 1之间的随机数的和小于 1 的概率为 1/n!, 反过来 n 个 0 到 1之间的随机数的和大于 1 的概率为 1 - 1/n!
• 加到第 n 个数才刚好超过 1 的概率:
  
• 因此, 要想让和超过 1, 需要累加的期望次数为:
  

5. 有一个随机数生成器，不断生成 [0,1] 的浮点数 n 次，把这 n 个数放入到一个数组中，但是这个数组里面的值你都看不到是个黑箱，要求用概率的角度分析出第 k 小的数是什么？

• 不妨考虑引入第 n+1 个随机变量，由于分布是均匀的，且取值是[0,1]，所以可以认为第 k 小的变量的期望等于第 n+1 个变量小于等于第 k 小的变量的概率。
• 那么问题就变为了如何求这个概率，从统计方案数出发。
• 它们的大小关系一共有 (n+1)! 种，而 n+1 个变量小于等于第 k 个变量的方案数一共有 k×n!，因为第 n+1 个变量一共有 k 个位置可以插入。所以概率为 k/(n+1)，也就是第 k 小的期望。
• 其他解法-概率密度

四. 随机数产生

1. 已知有个 rand7() 的函数，返回1到7随机自然数，怎样利用这个 rand7()构造 rand10()，随机 1~10。

• 产生随机数的主要原则是每个数出现的概率是相等的，如果可以得到一组等概率出现的数字，那么就可以从中找到映射为 1~10 的方法。
• rand7()返回 1~7 的自然数，构造新的函数 (rand7()-1)*7 + rand7()，这个函数会随机产生 1~49 的自然数。原因是 1~49 中的每个数只有唯一的第一个 rand7() 的值和第二个 rand7() 的值表示，于是它们出现的概率是相等。
• 但是这里的数字太多，可以丢弃 41~49 的数字，把 1~40 的数字分成10组，每组映射成 1~10 中的一个，于是可以得到随机的结果。
• 具体方法是，利用 (rand7()-1)*7 + rand7() 产生随机数 x，如果大于40则继续随机直到小于等于40为止，如果小于等于40，则产生的随机数为 (x-1)/4+1

2. 已知一随机发生器，产生0的概率是 p，产生1的概率是 1-p，现在要你构造一个发生器，使得它产生0和1的概率均为 1/2。

• 考虑连续产生两个随机数，结果只有四种可能：00、01、10、11，其中产生01和产生10的概率是相等的，均为p*(1-p)，于是可以利用这个概率相等的特性等概率地产生01随机数。比如把01映射为0,10映射为1。
• 于是整个方案就是：产生两个随机数，如果结果是00或11就丢弃重来，如果结果是01则产生0，结果是10则产生1。

3. 已知一随机发生器，产生的数字的分布不清楚，现在要你构造一个发生器，使得它产生0和1的概率均为 1/2。

• 考虑连续产生两个随机数 a、b，结果有三种情况a==b，a>b，a<b
• 其中由于a和b的对称性，a>b 和 a<b 出现的概率是相等的，于是可以利用这个概率相等的特性等概率地产生01随机数。

4. 已知一随机发生器，产生0的概率是 p，产生1的概率是 1-p，构造一个发生器，使得它构造 1、2、3 的概率均为 1/3; 更一般地，构造一个发生器，使得它构造 1、2、3、…n 的概率均为 1/n。

• 要从n 个数中等概率地产生一个随机数，关键是要找到 n 个或更多个出现概率相等的事件，然后我们重复随机地产生事件，如果是跟这 n 个事件不同的事件直接忽略，直到产生这 n 个事件中的一个，然后就产生跟这个事件匹配的随机数。
• 由于 n 个事件发生的概率相等，于是产生的随机数的概率也是相等的。考虑连续产生 x 个随机数，结果应该是 x 个0跟1的组合，为了使某些结果出现的概率相等，我们应该要让这个结果中0和1出现的次数相等，即各占一半。
• 于是 x 的长度必须是偶数的，为了方便，考虑连续产生 2x 个随机数。每
• x 个0跟1各出现一半的结果可以赋予1到n的某个数，为了能够表示这n个数，需要0跟1各出现一半的总结果数大于等于n，即C(2*x, x) >= n解出最小的 x 即为效率最高的 x。
• 然后把前 n 个0和1个出现一半的结果分别赋予1到n的值。随机时连续产生2*x个数，如果不是这n个结果中的一个则重新随机，如果是的话则产生对应的值作为随机结果。

五. 蓄水池抽样

1. 给出从 n 个数中随机选择 m 个的方法。注意，n 非常大，并且一开始不知道其具体值。数字流式给出，当给完之后，你必须立刻给出随机的结果。

• 首先前 m 个数字是必须拿的。
• 第 i 个数到来的时候，以 m/i 的概率决定是否要选择这个数字。如果选择了这个数字，则随机地替换掉 m 个数字中的一个。
• 如果前 i-1 个数字的时候保证了每个数字被选取的概率相等，则这样做之后可以保证每个数字被选取的概率也相等，为 m/i。
  • 第 i 个数选择的概率是m/i，因为算法就是这样决定的。
  • 考虑前 i-1 个数字中的任意一个，它在第 i 个数之前被选择的概率是m/(i-1)。在第 i 个数字的时候，这个数字要被选择的话又两种可能，一是第 i 个数没有被选中（概率是1-m/i），二是第 i 个数倍选中了（概率是m/i）但是替换掉的数字不是它（概率是1-1/m），于是这个数在第 i 个数时仍然被选择的概率是 m/(i-1) * ((1-m/i) + (m/i * (1-1/m))) = m / (i-1) * ((i-1) / i) = m/i。
  • 由数学归纳法原理知，对于任意的 n，当给完 n 个数的时候，选择的结果可以保证这 n 个数中每个被选中的概率都是相等。

六. 策略

1. 一个活动，女生们手里都拿着长短不一的玫瑰花，无序地排成一排，一个男生从队头走到队尾，试图拿到尽可能长的玫瑰花，规则是:一旦他拿了一朵，后面就不能再拿了，如果错过了某朵花，就不能再回头，问最好的策略是什么?

• 从数学模型上说，就是先拒掉前面 k 个人，不管这些玫瑰花有多长；然后从第 k+1 个人开始，一旦看到比之前所有花都要长，就毫不犹豫地选择。
• 不难看出，k 的取值很讲究，太小了达不到试的效果，太大了又会导致真正可选的余地不多了。
• 这就变成了一个纯数学问题：在玫瑰花总数 n 已知的情况下，当 k 等于何值时，按上述策略选中最长玫瑰花的概率最大？如何求出最优的 k 值？
  • 对于某个固定的 k，如果最长的玫瑰花出现在了第 i 个位置（k < i ≤ n），要想让它被选中，就必须得满足前 i-1 个人中的最好的人在前 k 个人里，这有 k/(i-1) 的可能。考虑所有可能的 i，我们便得到了试探前 k 个女生之后能选中最佳女生的总概率 P(k)：
    
  • 用 x 来表示 k/n 的值，并且假设 n 充分大，则上述公式可以写成：
    
  • 对 -x · ln x 求导，并令这个导数为 0，可以解出 x 的最优值1/e