概率题

1. 一个桶里面有白球、黑球各100个，现在按下述规则取球：

• i 、每次从桶里面拿出来两个球；
• ii、如果取出的是两个同色的求，就再放入一个黑球；
• iii、如果取出的是两个异色的求，就再放入一个白球。
  问：最后桶里面只剩下一个黑球的概率是多少？
  答：
  动态规划，令f[i,j]表示有i个白球，j个黑球的概率。
  已知f[100,100] = 1/2, 求f[0,1]。
  拿到两个白球: f[i-2,j+1] = i/(i+j) (i-1)/(i+j-1) f[i,j] + f[i-2, j + 1]
  拿到两个黑球: f[i, j-1] = j/(i+j) (j-1)/(i+j-1) f[i,j] + f[i, j - 1]
  拿到一黑一白: f[i, j-1] =2 i/(i+j) j/(i+j-1) * f[i,j] + f[i, j - 1]

2. 10个人出去玩，集合时间有10分钟，每个人都在该时间内到达，概率均匀分布，彼此独立，那么最后一个人最有可能到达的时间是?
   遇到这种想不明白，最好的方法就是枚举。
   若最后一个人在10分钟到达（概率1/10），其他人也都已经到达了（概率是1），总概率是 1^9 (1/10)
   若最后一个人在9分钟到达（概率1/10），其他人到达的概率是(9/10)9，总概率是 (9/10)^9 (1/10)
   依此类推。可见概率最大的是第10分钟。

3. 已知随机数生成函数f()，返回0的概率是60%，返回1的概率是40%。根据f()求随机数函数g()，使返回0和1的概率是50%，不能用已有的随机生成库函数。
   调用f()两次即可，会出现4种结果(0,0), (0,1), (1,0), (1,1)，其中出现(0,1), (1,0)的概率是一样的，可以构造出等概率事件，比如出现(0,1)可返回0，出现(1,0)可返回1，如果出现其他两种情况则舍掉重新调用。

4. 给定rand5()，实现一个方法rand7()。也即，给定一个产生0到4（含）随机数方法，编写一个产生0到6（含）随机数的方法。
   随机数函数的关键是确保产生每一个数的的概率相等。我们可用通过5 * rand5() + rand5()产生[0:24]，舍弃[21:24]，最后除以7取余数，则可得到概率相等的[0:6]的数值。

5. 100个人排队，每个人只能看到自己之前的人的帽子的颜色（假设只有黑白两色），每个人都得猜自己帽子的颜色，只能说一次，说错就死掉，别人可以听到之前的人的答案以及是否死掉。请问用什么策略说死掉的人最少。
   假设只有3个人，假设ture = 白，false = 黑，用这个公式x3 = (x1 == x2)，用人话就是1和2的帽子颜色一样的话就说白，不一样的话就说黑。这个策略第一个人死的概率是1/2，剩下的两个都不会死。
   推广到4个人，也就是x4 = (x3 == (x1 == x2))，照理可以推广到100人。但问题就是人很难判断，只能靠计算机来算。
   另一个解题方法：“最后一个人看一下前面黑帽子的个数是奇数还是偶数，比如约定奇数说黑，偶数说白。这样前面的人都可以推断出来正确的结果。”

6. 54张牌，平均分成三堆，大小王在同一堆的概率？
   先平均分三堆，大王在第一堆的概率是1/3, 小王在剩下的53张牌中，有17/53的概率和大王同一堆。依此类推，大王还可能在2,3堆，因此
   1/3∗17/53∗3=17/53

7. 买饮料，三个瓶盖可以换一瓶，请问要买100瓶饮料，最少需要买多少瓶？
   答：
   设要买x瓶。
   x+x/3>=100
   对么？小心！x/3瓶如果满3瓶还可以再换的，想象某人堵在小卖部门口狂开瓶。因此应该是
   x+x/3+x/9+…+x/3n>=100
   n=log3x
   x(1−1/3n)/(1−1/3)>=100
   x(1−1/x)>=200/3
   x=68
   不过我返回去算了下, 发现x=68只能买99瓶…毕竟算的时候当x是实数了，因此还是再返回来推一下的靠谱，x=69。

8. 在半径为1的圆中随机选取一点。
   从[0, 2*pi)随机选取一个角度，再在这个方向的半径上随机选取一个点。但半径上的点不能均匀选取，选取的概率要和离圆心的距离成正比，这样才能保证随机点在圆内是均匀分布的。

9. 一根木棒，截成三截，组成三角形的概率是多少？
   设第一段截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。

10. 抛一个六面的色子，连续抛直到抛到6为止，问期望的抛的次数是多少
    因为每次抛到6的概率相等，都是1/6，于是期望的次数就是1/(1/6)=6次。

11. 一个木桶里面有M个白球，每分钟从桶中随机取出一个球涂成红色（无论白或红都涂红）再放回，问将桶中球全部涂红的期望时间是多少？
    通过动态规划来进行求解。
    

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

13. 已知有个randM()的函数，返回1到M随机自然数，怎样利用这个randM()构造randN()，随机1~N。
    当N<M的时候，可以直接得到，将大于N的数去除掉即可。
    当N>M，构造类似于(randM() - 1) * M + randM()，可以产生1——M^2，然后在M^2中选择N个构造1——N的映射。
    如果N>>M,可以对上面得到的randM(M^2)继续进行构造
    思路二：可以通过位操作进行。用已经知道的randM作为一个0，1生成器，生成所求数的最大位数词。然后组成这个数，当生成的数大于N的时候，舍弃重新开始。

14. 已知一随机发生器，产生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。

15. 已知一随机发生器，产生的数字的分布不清楚，现在要你构造一个发生器，使得它产生0和1的概率均为1/2。
    和上面类似，可以产生两个数a，b，第一个比第二个大的时候，判断为0，反之，判断为1

16. . 已知一随机发生器，产生0的概率是p，产生1的概率是1-p，构造一个发生器，使得它构造1、2、3的概率均为1/3；…。更一般地，构造一个发生器，使得它构造1、2、3、…n的概率均为1/n。
    关键是找到n个出现概率相等的事件。
    考虑到产生x个随机数，我们希望0和1的组合概率相等。即二者程度必须是偶数。然后为每种组合赋予一个值即可。
    要求是C(2*x, x) >= n

17. 给出从n个数中随机选择m个数的方法。n很大，可以认为是亿级别。m可以很小，如接近1；也可以很大，如接近n。
    一个直接的思路是一直重复地随机，直到随机到m个数为止。这个方法有两个弊端：

• 难以直到后面随机到的一个数是否在前面已经随机过了，因为数据量很大，无法保存在内存中，如果保存到外存中则时间花费太大。
• 如果m很大，甚至接近于n，则后面随机到的数字基本上都是前面随机过的，因而需要尝试的随机次数太多。
• 一个思路是每个数被选中的概率是m/n，则可以遍历一遍原数据，在遍历每个数字的同时以m/n的概率决定是否要选择当前数字，则当遍历完毕的时候，选择到的数字在平均意义就是m个。这个会随着n的增大而更好地趋近于m，但不能很精确地保证随机到的数字一定是m个。
• 以上思路虽然不能满足要求，但我们可以进行改进。刚才我们在遍历每个数字的时候都是以同样的概率m/n决定是否要选择该数字，实际上，在当前遍历数字的前面的数字的结果我们是已经知道了，我们可以根据前面的随机结果动态地调整当前的随机策略，使得最终能够保证随机到的数字一定是m个。

  具体的做法是，**遍历第1个数字时有m/n的概率进行选择，如果选择了第1个数字，则第2个数字被选择的概率调整为(m-1)/(n-1)，如果没选择第1个数字，则第2个数字被选择的概率为m/(n-1)。即遍历到第i个数字的时候，如果此时已经选择了k个，则以(m-k)/(n-i+1)的概率决定是否要选择当前的第i个数字。
  这样可以保证每次都能够保证在剩下的数字中能选择适当的数使得总体选择的数字是m个。比如，如果前面已经随机了m个，则后面随机的概率就变为0。如果前面一直都没随机到数字，则后面随机到的概率就会接近1。最终得到的结果始终精确地是m个数字。**

18. 给出从n个数中随机选择1个的方法。注意，n非常大，并且一开始不知道其具体值。数字是一个一个给你的，当给完之后，你必须立刻给出随机的结果。
    答案是要保证每个数字被选取的概率是相等，当第i个数来的时候，如果我们已经保证了前i-1个数每个数被选取的概率都是相等的，那么只要第i个数字被选取的概率是1/i，我们就可以知道所有i个数被选取的概率都是1/i了。所以只需要以1/i的概率决定是否要选取当前的第i个数字即可。
    于是可以保证对于任意的n，当给完n个数字时，选择每个数字的概率都是相等的，为1/n。

19. 给出从n个数中随机选择m个的方法。注意，n非常大，并且一开始不知道其具体值。数字是一个一个给你的，当给完之后，你必须立刻给出随机的结果。
    这题是上一题的推广，于是可以仿照着进行。
    首先前m个数字是必须拿的。问题是当第i（i>m）个数字来的时候，究竟是要丢弃这个数，还是保留这个数？如果要保留这个数的话，则必须得丢弃手中已有的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个数中每个被选中的概率都是相等

20. 一个三角形， 三个端点上有三只蚂蚁，蚂蚁可以绕任意边走，问蚂蚁不相撞的概率是多少?
    乍一看有点蒙…
    其实很简单…
    1.每个蚂蚁在方向的选择上有且只有2种可能，共有3只蚂蚁，所以共有2的3次方种可能
    2.不相撞有有2种可能，即全为顺时针方向或全为逆时针方向。
    不相撞概率=不相撞/全部=2/8

21. A城一个商人有一头驴子和3000根胡萝卜.要将萝卜拉到1000公里外的B城去卖，只能用驴子驮。已知驴子一次性可驮1000根胡萝卜,但每走一公里要吃掉一根胡萝卜.问商人共可卖出多少胡萝卜?
    这题的问题出在给的条件不充分，可能有两种情况，一种是非理想状态的拉运萝卜，这种情况的话，一个也不能卖出去；第二种为理想状态下的，就是能在每走一公里的时候能够卸货下来，并且还没有其他的外在因素使得萝卜丢失，这样的理想状态下能够运送到B城833个萝卜。计算过程如下：1、因为有3000萝卜，所以消耗掉前面的1000个萝卜的时候，每前进一公里要来回3次消耗3个萝卜，因此第一次前进了X公里，X=1000/3=333余数为1；2、剩下的2001个萝卜在第334公里的时候需要来回3次才能运送完，我们就将这一公里路算在2000个萝卜在第一次运送的时候算在一起，那么第二次运送萝卜只需要来回2次消耗2个萝卜，因此第二次消耗1000个萝卜前进了Y公里，Y=1000/2=500；现在前进了500+333=833公里，剩下167公里后，萝卜也只剩下了1000个，所以就这1000个直接中途不卸货的一次到达B城，消耗167个萝卜，所以最后剩下1000-167=833个萝卜。

22. 甲乙两个人答对一道题的概率分别为90%和80%，对于一道判断题，他们都选择了“正确”，问这道题正确的概率。请问这题怎么做，谢谢
    有人有以下解法，以下是否正确？
    题目为真且甲乙都选则正确的概率 / 甲乙都选择正确的概率
    题目为真且甲乙都选真/(题目真甲乙都选真+题目假甲乙都选真)
    (0.50.90.8)/{(0.50.90.8+0.50.10.2)}
    =72/74

23. 飞机上有100个座位，按顺序从1到100编号。有100个乘客，他们分别拿到了从1号到100号的座位，他们按号码顺序登机并应当对号入座，如果他们发现对应号座位被别人坐了，他会在剩下空的座位随便挑一个坐。现在假如1号乘客疯了 -_-! (其他人没疯)，他会在100个座位中随机坐一个座位。那么第100人正确坐自己座位的概率是多少？
    注意登机是从1到100按顺序的。
    换个角度，相当于疯会传染，如果某个人的作为被疯子占了，那么他就会去做其他人的位置，当最后的时刻。相当于疯子要么坐上自己的位置，要么坐上了我的位置。二选一。

24. 两个信封，一封里装的钱是另一封里的两倍，你选了一个打开一看，里面是十块钱，这个时候你可以选择换成另一个，问你该不该换？
    第一印象肯定是换不换无所谓，因为貌似二者不相关。
    但是随后又会想到，另一个信封有一半可能是五块，一半可能是二十块，期望值会是1/2(5+20) = 12.5，当然应该换。

25. 三人陪审团，其中两人每人做出正确决定的概率是Ｐ。另一人总是靠扔硬币来决定支持谁。最后由多数票决定结果。另一个审判由一人决定，这个人做出正确决定的概率也是Ｐ。问三人陪审团与一人审判谁有更大概率做出正确决定？
    一样大，都是p

概率面试题

1. 给你一个数组，设计一个既高效又公平的方法随机打乱这个数组（此题和洗牌算法的思想一致）

import random
def shuffle(nums):
	for i in range(len(nums)):
		j = random.randint(0, i)
		nums[i], nums[j] = nums[j], nums[i]
return

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。

3. 一个面试题：快速生成10亿个不重复的18位随机数的算法(从n个数中生成m个不重复的随机数

   import random
   
   def random_choice(n, m):
   	count = 0
   	for i in range(1, n + 1):
   		if count == m:
   			break
   		t = random.randint(n - i)
   		if t < m:
   			count += 1
   	return

4. 你有两个罐子以及50个红色弹球和50个蓝色弹球，随机选出一个罐子然后从里面随机选出一个弹球，怎么给出红色弹球最大的选中机会?
   在你的计划里，得到红球的几率是多少? 题目意思是两个罐子里面放了50红色和50蓝色弹球，然后我任选一个罐子，从中选中一个红球的最大概率，是设计一个两个罐子里怎么放这100球的计划。一个罐子：1个红球另一个罐子：49个红球，50个篮球几率=1/2+(49/99)*(1/2)=74.7%

5. 一副扑克牌54张，现分成3等份每份18张，问大小王出现在同一份中的概率是多少？（大意如此）
   不妨记三份为A、B、C份。大小王之一肯定在某一份中，不妨假定在A份中，概率为1/3。然后A份只有17张牌中可能含有另一张王，而B份、C份则各有18张牌可能含有另一张王，因此A份中含有另一张王的概率是17/(17+18+18)=17/53。

也因此可知，A份中同时含有大小王的概率为1/3 * 17/53。

题目问的是出现在同一份中的概率，因此所求概率为3(1/3 17/53)=17/53。

6. 有一对夫妇，先后生了两个孩子，其中一个孩子是女孩，问另一个孩子是男孩的概率是多大？

答案是2/3.两个孩子的性别有以下四种可能：（男男）（男女）（女男）（女女），其中一个是女孩，就排除了（男男），还剩三种情况。其中另一个是男孩的占了两种，2/3.　之所以答案不是1/2是因为女孩到底是第一个生的还是第二个生的是不确定的。

7. 一个国家人们只想要男孩，每个家庭都会一直要孩子，只到他们得到一个男孩。如果生的是女孩，他们就会再生一个。如果生了男孩，就不再生了。那么，这个国家里男女比例如何？
   一个家庭的孩子数量可以为:1,2,3,4,5….. 对应的的男女分布为: “男”,”女男”,”女女男”,”女女女男”,”女女女女男”…

对应的概率分布为 1/2, 1/4, 1/8, 1/16, 1/32 。其中女孩的个数分别为 0,1,2,3,4……

因此 S2=01/2 + 11/4 + 21/8 + 31/16 + 4*1/32 + ………

可以按照题目2用级数求，也可以用错位相减法：S2=1/4+2/8+3/16+4/32+… 两边乘以2,得: 2*S2=1/2+2/4+3/8+4/16+5/32+..

两个式子相减得 S2=1/2+1/4+1/8+1/16+1/32+…=1. 所以期望值都为1，男女比例是一样的。

8. 有一个很大很大的输入流，大到没有存储器可以将其存储下来，而且只输入一次，如何从这个输入流中等概率随机取得m个记录
   不知道数据量有多大的问题。
   蓄水池抽样 或 reservoir sample。假设输入到第n个记录了，以m/n的概率取该数，如果取中则随机替换掉原来取中的m个记录中的一个。初始时，选中前m个记录。

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

   数学期望类的题目，主要是要理解什么是数学期望，数学期望是干什么用的，关于这些问题的解答，大家可以自己去理解，思考或者翻书，我要讲的内容是如何利用这些数学期望的特点。
   
   现在我们开始解答上面的问题：
   
   令P[i]代表M个球中已经有i个球是红色后，还需要的时间期望，去将所有球都变成红色。
   
    
   
   So，给出递归式：
   P[i]= (i/M) * P[i] + (1-i/M)* P[i+1] + 1
   
   我相信大家都能理解这个公式的含义，不过还是解释一下，在P[i]的情况下，我们选一次球，如果是红球，那么概率是i/M，子问题还是P[i]，如果是白球，那么概率是1-i/M，子问题是P[i+1]，注意你当前的选球操作要计算在内，即一次
   
    
   
   化简如上递归式得：P[i] = P[i+1] + M/(M-i)，显然P[M] = 0;
   
   所以：
   
   P[M-1] = P[M] + M/1
   
   P[M-2] = P[M-1] + M/2
   
   …
   
   P[0] = P[1] + M/M
   
   综上：P[0] = 0 + M/1 + M/2 + … + M/M，至此问题已经解决，不过我希望大家学到的不是这个答案，而是分析这个题目的过程