.题目1：篮子里有M个绿苹果，N个红苹果。我们随机逐个拿出苹果，直到所有绿苹果都被取出。问停下来的时候，篮子为空的概率。
解：当绿苹果全部取出的时候，篮子为空。代表了绿苹果是最后取出的。成为最后一个苹果的概率大家都相同。因此绿苹果最后取出的概率为M/(M+N)。
题目2：投掷硬币n次，问 正面次数*反面次数 的期望是多少？
解：根据二项公式：出现 i 次正面，n-i 次反面的概率是 C(n, i)*0.5^n。带入期望公式加和得(n^2 - n)/4。
题目3：x1, ..., x9 是 1, .. 9 随机环形排列。问差值的绝对值相加的最小值是多少？出现最小值的概率是多少？
解：1 9 中间有gap，因此是两个特殊点。环形结构，不失一般性，以1为起点。如果想要得到差值绝对值的最小和。1和9之间的数字必须是递增或者递减。比如 1 2 3 4 9 8 7 6 5。这样就可以得到差值绝对值的最小和16。剩下七个数字，每个数字都有0.5的概率进入1-9的区间或9-1的区间。因此得到最小值的组合有 0.5^7 种。而以1为起点的组合有 8! 种。相除得概率1/315.
题目4：A中有1000个绿球，3000个红球。B中有3000个绿球，1000个红球。你从A中取出一半的球放入B中。然后从B中取出一个球，问这个球是绿球的概率。
解：假设从A中转移了X个绿球到B中。那B中取出1个球为绿的期望是 E[(3000+x)/6000]，因此只需要求 E[x]即可。E[x] = 1000/4000 * 2000 = 500.带入得7/12。
题目5：机器人丢硬币，科学家AB都可以从其动作和声音推测结果。A有80%的概率猜中，B有60%的概率猜中。机器人开始后，A猜测硬币是正面，B猜测硬币是反面。你能否计算出硬币正面的概率。
解：
题目6：抽牌游戏，指定一个 <= 52 的正整数k。你抽k张牌，如果最后一张牌为A，且前面的k-1张牌有且只有一张A，则获胜。你应该如何选择k.
解：4张A为特殊牌，其他48张牌位普通牌。k张牌，总的排列数是A(52,k)。获胜排列中，有两张A，A(4,2)，其中一张是最后一张，那另一张的位置有A(k-1,1)，剩下的k-2张牌为普通牌，A(48, k-2)。概率为A(4,2)*A(k-1,1)*A(48, k-2)/A(52,k)，化简为12*(k-1)*(52-k)*(51-k)/(52*51*50*49).
比较概率 P(k+1) < P(k), P(k-1) < P(k) 得18.
题目7：N为正整数随机变量。证明N的期望等于 sum(i=0, 正无穷)P(N>i).
解：E[N] = sum(i=0, 正无穷) i * P(N=i)，按照 i = 1, 2, 3, ... 逐行展开。那第一列就是 P(N>0), 第二列是 P(N >1)...得证。
题目8：每个盲盒里面有一张券，如果有p种券，问平均需要买多少个盲盒才能集齐所有券。
解：这里假设每种券出现的概率一致。已有 i 种券的时候，新一种券的到达服从泊松过程，到达率lambda = (p-i)/p。因此每次等待新券的期望时间为 p/(p-i)。总等待时间为 p/p + p/(p-1) +p/(p-2) + ... + p/(p-i) + .. + p/1
题目9：你有一个n面的色子。重复投掷加和点数。问平均来说，你需要投掷多少次，才能使得和为n的倍数。
解：已经投掷了i-1次，第i次投掷能使得和为n的倍数的概率为1/n.因此，每次投掷，成功的概率都是1/n. 二项分布成功所需要的实验次数的期望为n.
题目10：你有两个有问题的6面色子。点数为两个色子之和。问是否可能所有的结果服从均匀分布。
解：可能的结果有{2,3,4,5,6,7,8,9,10,11,12} 11种，服从均匀分布的话，每个结果的概率都为1/11。因此P(2) = P(12) = 1/11。p1,1 * p2,1 = 1/11，p1,6 * p2,6 = 1/11。 P(7) > p1,6 * p2,1 + p1,1 * p2,6 > 2*(p1,6 * p2,1 * p1,1 * p2,6)^0.5 > 2 * 1/11。
题目11：2^n 个选手参加淘汰赛，两位选手碰不上的概率是多少？
解：不失一般性，假设两位选手是1 2 号选手。1 2 号选手碰面的概率为P1,2，那一号选手一共可以玩的游戏局数是 P1,2 + P1,3 + ... + P1,2^n。由对称性可得 P1,2 * （2^n - 1）.
总共的比赛场次Total = 2^(n - 1) + .. + 2^0。那平均每个选手参加Total*2/2^n. Total*2/2^n = P1,2 * （2^n - 1）得到P1,2 = 0.5^(n-1)
题目12: 类似题目做过。而且这道题有点问题。
题目13：52张扑克牌。红黑各26张。同颜色的连续n张牌为串，问平均有多少个串。
解：Fk = 1 如果第k张牌为串的第一张，否则为0。串的期望数为 E[Sum(2, 52)Fk]，第一张牌一定为串的第一张，因此期望数为1 + Sum(2, 52)Fk。第二张牌E[Fk] = 26/51。可以证明后续任意第k张牌的期望E[Fk] = 26/51。
E[Fk] = 2P(k为红|k-1为黑) = 2 * 26/52*26/51 = 26/51
题目14: 8男7女坐一排。问挨着坐的男女有多少对？
解：Dk = 1 如果第k个和k+1个座位性别不同，否则为0。k 属于[1, 14]。对的期望数为 E[Sum(1, 14)Dk]，可以证明任意第k个座位的期望E[Dk] = 8/15。
E[Dk] = P(k为男|k+1为女) + P(k为女|k+1为男)= 8/15*1/14 + 7/15*8/14 = 8/15.
题目15：N个球等概率随机放入N个篮子。求空篮子的期望和方差。
解：任意一个篮子为空的概率为 ((N-1)/N)^N。这题有点像二项分布，但不是！因为每个篮子的是否为空这个事件并非相互独立。空篮子个数X的期望容易计算 (N-1)^N/N^(N-1)。方差Var(X) = E[X^2] - E[X]^2。其中， E[X^2] = E[sum(1,N) Indexi^2 + sum(i=1,N)(j=1,N, j !=i) Indexi*Indexj ]
题目16：两个色子，6个面，每次投掷，我们获得的点数为两个点数加和。问我们在得到2个七之前就得到6个偶数的概率是多少？
解题：本题核心是引入一个相关事件的概念。只有获得偶数，或者七，才算相关事件。否则就当没投掷。单次投掷获得七的概率为6/36 = 1/6。单次投掷获得偶数的概率为 1/2。因此，在出现相关事件时，获得七的概率是1/6/(1/6+1/2) = 1/4。
要在得到2个七之前就得到6个偶数，实验次数可能为6次，也可能为7次。 (3/4)^6 + 6*(1/4)(3/4)^5*(3/4).
题目17：平均来说，投色子投多少次会出现重复？
解：2次出现重复的概率是1/6。3次出现重复的概率是(1-1/6)*2/6 = 5/18。4次出现重复的概率是(1-1/6-5/18)*3/6=5/18。5次出现重复的概率是(1-1/6-5/18-5/18)*4/6=5/27。6次出现重复的概率是(1-1/6-5/18-5/18-5/27)*5/6=25/324。7次出现重复的概率是1-1/6-5/18-5/18-5/27-25/324 = 5/324。计算期望得1223/324.
题目18：n是个随机正整数，问2^n以1开头的概率是多少？
解：2^n以1开头意味着存在一个k，使得 10^k < 2^n < 2*10^k。取对数后得 n = ceil(k*log2,10)。因此，对于任意n 属于区间(ceil(k*log2,10), ceil((k+1)*log2,10))。都有 k 个小于n的整数 i 使得2^i以1开头。那概率 k/n 属于区间(k/((k+1)*log2,10 +1), 1/k*log2,10)。取极限得1/log2,10。
题目19：你可以搭乘1路车和2路车。一路车在二路车开出后10分钟到达，二路车在一路车开出20分钟后到达。问平均等待时间。
解：等待区间(0, 30]，以二路车开出的时间为0，在(0, 10]区间，等待时间为10-x；在(10, 30]区间，等待时间为20-x；均匀分布积分即可。得25/3
题目20：七个小矮人按顺序选择就寝。但第一个小矮人喝醉了，他随机选取一个床铺睡下。后面的小矮人会选择自己的床，如果自己的床没有被占用；否则随机选择其他没被占用的床。问最后一个小矮人睡在自己床上的概率。
解：n个小矮人中，第k个小矮人无法睡在自己床上的概率为1/(n-k+2)。推导过程看书。
题目21：n辆车以不同速度开在一条单行道上。如果碰到较慢的前车，后车速度会减到与前车一致，这样同速度的车群成为一块。问最终将形成多少个快。
解：只要关注最慢的车即可m = min(X1, ..., Xn)。alphaN 为n辆车形成的块的数量Cn的期望，alphaN = E[Cn] = n * E[Cn| Xk = m]。其中E[Cn| Xk = m] = 1 + E[Cn-k] = 1 + alphaN-K. 因此有 N * alphaN = N + alphaN-1 + alphaN-2 + .. + alpha1. 得 alphaN = sum(k=1, n) 1/k.
题目22：25只蚂蚁随机散落在一米长的木棍中，它们运动速度相同，运动方向随机左右。棍子中间的蚂蚁有传染病，该病会传染给所有与宿主接触过的蚂蚁。问当蚂蚁全部掉下木棍时，有多少蚂蚁得病。
解：假设中间那只得病的蚂蚁向右运动：那右半边所有向左移动的蚂蚁都会被传染。因此右半边得病蚂蚁的数量期望是24/2/2 = 6。但凡右半边蚂蚁不是全都向右（1 - (1/2)^12）左半边向右移动的蚂蚁也必然会被传染。因此数量期望是 6 * （1 - (1/2)^12）
题目23：掷骰子直到出现两个连续的相同点数。问所有点数加起来为偶数的概率。
解：定义事件E为所有点数和为偶数。F1, F12分别代表第一次点数为1，第一二次点数为1 2 。
P(E) = 1/6 * [ P(E|F1) + P(E|F2) + P(E|F3) + P(E|F4) + P(E|F5) + P(E|F6)] = 1/2 * [ P(E|F1) + P(E|F2)] 利用对称性
令 alpha = P(E|F1) , beta = P(E|F2)。
alpha = 1/6 * [ P(E|F11) + P(E|F12) + P(E|F13) + P(E|F14) + P(E|F15) + P(E|F16)] = 1/6 * [ P(E|F11) + 3 * P(E|F12) + 2* P(E|F13)]
P(E|F12) = 1 - P(E|F2). 因为F12第一个点数是1，多了一个奇数。总和为偶数的概率就是1 - P(E|F2)。因此有
alpha = 1/6 * [1 + 3 * (1 - beta) + 2 * (1-alpha)]； 同理有 beta = 1/6 * [1 + 3 * alpha + 2 * beta]. alpha = 21/41, beta = 26/41
题目24：投掷硬币直到获得连续 n 个正面（头像）所需要的投掷次数的方差。
解：离散时间马尔科夫链的 "连胜问题"（run problem） 是一个经典的概率问题，涉及在独立重复试验（如投掷硬币）序列中寻找连续出现某一事件（如连续出现n个正面）的首次出现时间。
### 期望值和方差
E[x] = 2^{n+1} - 2
Var(X) = (2^n - 1)(2^{n+1} - 1)
题目25：三只青蛙栖息在等边三角形的三个顶点上。每隔一秒，它们以相等概率跳向另外两个顶点。问需要等待多久，三只青蛙在同一个顶点。
解：三种状态：（111），（012），（003）分别定义为状态123. 状态123之间可以相互转化。P11 = 1/4, P12 = 3/4; P21 = 1/4, P22 = 5/8, P23 = 1/8. 状态3为终止态。因此，从状态1到终止态的步长期望 E1 = 1/4 * E1 + 3/4 * E2 + 1；从状态2到终止态的步长期望 E2 = 1/4 * E1 + 5/8 * E2 + 1/8 * E3 + 1。E3 = 0。解得E0 = 12.
题目26：是否有可能用硬币来实现{a, b, c}的随机选取？
解：硬币投出 HH, HT, TH 分别对应 a b c。投出TT就重新投。
题目27：河中间有6个岛屿（下图深黑色点）用13座桥与堤岸相连。洪水发生时，每座桥都有独立的0.5的概率被冲毁，问还能过河的可能性。
解：考虑一个很高的船能通行的可能性。如果桥在则过不去，桥被冲毁了则可以通过。因此船过河的方式为浅灰色的岛屿和桥。与黑色的岛屿桥对称。且两个事件为互补关系。因此人能过河的概率是0.5.
题目29：投掷硬币30次，我们可以得到随机变量 头像个数X 的概率分布。问X的个位数的期望是多少？
定义事件：R=1 代表个位数为1. 则概率 P(R=1) = P(R=9)。因此X的个位数的期望是 Sum((1,9); i * P(R=i) ) = Sum((1, 9); 5 * P(R=i) ) = 5 * [1-P(R=0)] = 5 * [1 - 2 * C(30,0) * 2 ^-30 - 2 * C(30,10) * 2 ^-30]
题目30：n*n 的行列式A，元素都是[-1, 1]中随机抽取的。问行列式的方差是多少？
解：det(A) = sum(Pi)，其中Pi = sgn(i)*ai1*ai2*...*ain，i为行列式计算中的斜线。E[Pi] = 0，因为每个元素都是独立的，且期望为0.
Var(det(A)) = sum E[(Pi)^2] + sum E[Pi]E[Pj]；E[(Pi)^2] = 1， E[Pi]E[Pj] = 0. 因此方差为 n!.
题目31：AB两个箱子，各有n个球。每一步，我们随机拿一个箱子取出一颗球。不断重发，直到发现所选的箱子已空，问另一个箱子中剩下球的个数的期望。
解：事件剩下k个球的概率为P(k)，P(k) = P(k|A空) + P(k|B空)，两者对称，因此P(k) = 2* P(k|A空)。我们会在2n-k+1步的时候发现A箱子空了。多出的一步用来发现A空了。因此在前面的2n+k次抽取中，有n次抽了A箱子；最后一次抽取也抽了A箱子。 P(k|A空) = C(2n-k, n)*(1/2)^(2n-k)*1/2。P(k) = C(2n-k, n)*(1/2)^(2n-k)。E[k] = sum(k*P(k))。后续数学计算略去。
题目32：
