Kong Kim in plane

金刚坐飞机问题,有一班飞机要起飞,乘客们正准备按机票号码(1,2,…,N)依次登机。突然来了个金刚,他也有飞机票,但是他插队第一个上了飞机,随机选个座位坐下了。其他乘客有两种反应:

  1. 他们也随意找个位置坐下;
  2. 如果自己座位没有被占领,就坐自己的位置,否则随意找个位置坐下。

在这两种情况下,第i个乘客(除去金刚外)坐到自己原机票位置的概率分别是多少?

Q1

要保证第i个乘客坐到自己的位置上,则前i-1个乘客包括金刚都别坐到第i个人的座位,第i个人就有机会坐到自己的位置,得到概率公式为:
$$
f(i)=\frac{N-1}{N}\frac{N-2}{N-1}\dots\frac{N-i+1}{N-i+2}\frac{1}{N-i+1}=\frac{1}{N} (1)
$$

Q2

由于当乘客座位没人坐的时候,他会优先选自己的座位,那么设金刚坐在n号位置,当n=1/n>j,即在最开始时,前i个人的座位都保留着,那么他们上机后都会坐自己的座位;当n=i时,第i个人肯定坐不到自己的位置了;比较麻烦的就是当金刚在1<n<i之间的情况,此时2~n-1这几位乘客还是能坐到自己的位置,而第n位乘客肯定坐不到自己的位置了,他要开始随便坐了,既然他都随便坐了,那和金刚有什么区别?因此我们换种想法:

image-20201014131143349

即把金刚当作第n个人,而真正的第n人当作金刚,只不过该虚假的金刚和真正的金刚还是有点差别的,那就是他没有真正金刚那么多的座位选择,这个假金刚只能从剩下的N-n+1个座位里边选一个坐(1, n+1,n+2,…,N)。如此一来,当金刚坐在第n个座位(1<n<i)时,第i个人坐到自己座位的概率就变成了:
$$
f(n)=\sum_j \frac{1}{N-n+1}f(j),(j=1,n+1,…,N)(2)
$$
由该递推式,进一步可以得到n=n+1时的情况,即:
$$
f(n+1)=\sum_j \frac{1}{N-n}
f(j),(j=1,n+2,…,N)(3)
$$
上述两个式子相减,即得到:
$$
(N-n)[f(n)-f(n+1)]=f(n+1)-f(n) => f(n)=f(n+1),(1<n<i-1)(4)
$$
最终可得:
$$
f(n)=\frac{N-i+1}{N-i+2}(5)
$$
在不同情况下的f(n)都已求得,最后在把所有情况概率和相加即可:
$$
\sum_{n=1}^N \frac{1}{N}
f(n)=\frac{N-i+1}{N-i+2}(6)
$$

扩展

上述两种情况都假设乘客按照顺序上机,那如果乘客上机的顺序也是随机,第i个乘客上机坐到自己位置的概率怎么算呢?

对第一种情况影响不大,因为所有人就算是按顺序上机,座位也是随便坐的,和随便登机没差。

第二种情况下,当金刚坐在n号座位时,如果紧接着就是第n个人登机,那么他完全有可能坐到前n个人的座位,Orz