题目
有 n 只小鸟，各有自己的笼子（编号 1, 2, ..., n）。第一天，第一只小鸟（编号 1）没有回到自己的笼子（笼 1），而是随机进了其它某个笼子。后续的小鸟每天回来时，如果自己的笼子空着就进自己的笼子，否则从剩下的空笼子中随机选一个。
问：最后一只回笼的小鸟回到自己笼子的概率是多少？
这个问题和经典的飞机座位问题等价（见下），但需要注意的时初始条件不同，下面的问题第一个人位置也是随机的（可能回到自己的位置），而上面小鸟回笼问题则是在没有回到自己的笼子情况下。
有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。剩下的乘客将会：如果他们自己的座位还空着，就坐到自己的座位上；当他们自己的座位被占用时，随机选择其他座位，问：
第 n 位乘客坐在自己的座位上的概率是多少？
解答
**解：**设当所有鸟回到笼子后鸟和笼子编号的映射为 f(n) = m，其中 n 为鸟的编号，m 为笼子编号。
显然：
- 当 n=1 时，第 1 只鸟即为最后一只鸟，因此其回到自己的鸟笼的概率为 P=1；
- 当 n=2 时，第 1 只鸟因为没有回到自己的笼子，必然选择了第 2 只鸟即最后一只回笼小鸟所属的笼子，因此最后一只回笼小鸟回到自己的笼子的概率为 P=0。
下面讨论当 n≥3 时的情况，显然：
- f(1) ≠ 1;
- 若最后一只鸟回到自己的笼子，有 f(n)=n，否则 f(n)≠n。
再设当第 i 只鸟回到笼子时（1<i<n），剩下还没有鸟回笼的笼子编号集合为 C^l_i，剩下的鸟所属的笼子编号的集合为 C^b_i = {i, i+1, ..., n}。设 f(1)=k, k≠1。
若 k=n，则第 n 只鸟必然无法回到自己的笼子；当 k≠n 时，考虑第 k 只鸟回笼时，会发生如下情况：
- f(j)=j, 1<j<k;
- C^l_k={1, k+1, k+2, ..., n}，共 n-k+1 项。
显然，这一系列事件发生概率是由 f(1)=k 直接导致的，设此事件发生的概率为 P_k = 1/(n-1)，此时第 k 只鸟必须从 C^l_k={1, k+1, ..., n} 中随机选择一个笼子回笼，会出现三种情况：
- 选择笼子 1 回笼，则从 i>k 开始，第 i 只鸟的笼子都没有被占，后续所有鸟都会回到自己的笼子，这个事件发生的概率为 P^1_k = P_k * 1/(n-i+1)；
- 选择笼子 n 回笼，则第 n 只鸟因为自己的笼子已被占，因此必然无法回到自己的笼子，这个事件发生的概率也为 P^n_k = P_k * 1/(n-i+1)；
- 选择笼子 k+l 回笼，则当第 k+l 只鸟回笼时，C^l_{k+l}={1, k+l+1, k+l+2, ..., n}，显然第 k+l 只鸟回笼选择笼子的情况和第 k 只鸟相同，发生了一个递归过程。
这里可以定性的分析出，不论在哪个递归的分支，都有 P^1=P^n，即当笼子被占用的鸟随机选择笼子时，选择笼子 1 和 n 会直接决定第 n 只鸟能否回到自己的笼子，而这两种结果的概率是永远相等的。因此当 f(1)=k, k≠1, k≠n 时，第 n 只鸟能回到自己笼子的概率为 P^s_k = 1/2 * P_k，利用全概率公式，最终概率为 P = ∑_{k=2}^{n-2} 1/2 * P_k = (n-2)/(2(n-1))
综上，最后一只鸟回到自己的鸟笼的概率为 P = { 1, & n=1 0, & n=2 (n-2)/(2(n-1)), & n≥3 }
和经典问题的区别
在飞机座位问题中，由于第一个人也是随机选择的，迭代可以从第一个乘客开始，因此最终答案为 P=1/2
进一步地分析，如果我们从第一只鸟开始迭代（即第一只鸟是随机选择自己的鸟笼的），有如下情况:
- 显然当 n=1，P=1；
- 显然当 n=2，P=1/2；
- 显然当 n≥3，有：
- 若 f(1)=n，则最后一只鸟必然无法回到自己的笼子中；
- 若 f(1)=1，则后续回笼的鸟都能回到自己的笼子；
- 设总共有 n 只鸟时，最后一只鸟能回到自己鸟笼的事件为 A_n，若 f(1)=k, 1<k<n，则当第 k 只鸟进行选择时，其实际上面对的是一个 n-k+1 规模的同样的问题，因此有
P(A_n) = P[f(1)=1] + P[f(1)≠1,n] * ∑{k=2}^{n-1} P(A{n-k+1}) = 1/n + 1/n * ∑{k=2}^{n-1} P(A{n-k+1})
可以递推出 P(A_2)=P(A_3)=1/2，用数学归纳法，假设 n≥3 时，P(A_n)=1/2，则 P(A_{n+1}) = 1/(n+1) + 1/(n+1) * (n-1) * 1/2 = 1/2
这和经典问题是相同的。综上， P(A_n) = { 1, & n=1 1/2, & n≥2 }
