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

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

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

• 设第一段截 x第二段截 y，第三段 1 - x - y考虑所有可能的截法。

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）的时候才有可能发生，而且此时先手者在此面临和开始相同的局面）

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]

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

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

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

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

• 首先思考几个简单的問题:
• 任取 3 个 0 到 1 之间的实数, 它们的和小于 1 的概率是多少?
  3 个数之和小于 1 的概率是 1/6, 它是平面 x+y+z=1 在单位立方体中截得的一个三棱锥, 这个 1/6 可以例用截面與底面的相似比关系, 通过简单的积分求得:
  
• 4 个 0 到 1之间的随机数的和小于 1 的概率就等于四维超立方体一角的"体积", 它的"底面"是一个体积为 1/6 的三棱錐, 在第四维上对其进行积分便可得到其"体积":
  
• 以此类推, n 个 0 到 1之间的随机数的和小于 1 的概率为 1/n!, 反过来 n 个 0 到 1之间的随机数的和大于 1
• 加到第 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)也就昰第

• 产生随机数的主要原则是每个数出现的概率是相等的，如果可以得到一组等概率出现的数字那么就可以从中找到映射为 1~10 的方法。
• 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>ba<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）二是第
  • 由数学归纳法原理知，对于任意的 n当给完 n 个数的时候，选择的结果可以保证这 n 个数中每个被选中的概率都是相等

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

• 从数学模型上说就是先拒掉前面 k 个人，不管这些玫瑰花有多长；然后从第 k+1 个人开始一旦看到比之前所有花都要长，就毫不犹豫地选择
• 不难看出，k 的取值很讲究太小了达不到试的效果，太大了又会导致真正可选的余地不多了
• 这就变成了一个纯数学问题：在玫瑰花总数 n 已知的情况下，当 k 等于何值时按上述策略选中朂长玫瑰花的概率最大？如何求出最优的 k 值