疯狂邮差
Crazy Postman
题目详情
邮差给一户人家送 封信，门口有两个空信箱。
他先往两个信箱各放 1 封。之后每投递一封信，会按“当前信箱内信的数量占比”随机选择其中一个信箱放入（某箱里信越多，被选中概率越大）。
问：最终信件较少的那个信箱里，信件数量的期望是多少？
提示：可等价为把一张牌随机插入黑牌堆中。
A postman brought N letters to a house with two letter-boxes. Since the two boxes were empty, he puts 1 mail in each of the two mail boxes. Then he chooses one of boxes with probability proportional to number of letters present in that box, and puts the 3rd letter in it. He does this for all subsequent letters. What is the expected number of letters in the box with lower letters?
Hint
This can be made equivalent to randomly splitting a deck of n cards into two parts. (n>2)
解析
答案量级为 。
一种等价建模：把“红牌”视为分割点，黑牌数量对应两箱信件数。按比例投递对应于“按当前上下段长度比例，随机在红牌上方或下方插入一张黑牌”。
在该过程中，红牌出现在任意高度的位置概率近似均匀，因此“较小一侧的黑牌数量”在 到 之间近似均匀，故其期望约为 （渐近）。
Original Explanation
Solution
Suppose I have a stack of 2 black cards and one red card. Initially I put red between 2 black cards. Now I add black cards randomly between any two cards (so, initially it is either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be: if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent.
Now this way, we are getting all possible combinations in which one red and n black cards can be mixed, we see that the probability that the red card is at height h is independent of h. So, the probability that the smallest box contains n/2 letter or 1 letter (or any number of letters between 1 and n/2) are all same. So, expected number of letters in the smaller box is asymptotically n/4