量化面试绿皮书：23. 醉酒乘客

文中内容仅限技术学习与代码实践参考，市场存在不确定性，技术分析需谨慎验证，不构成任何投资建议。

23. 醉酒乘客

100名乘客排队登机，每人持有一张对应座位的机票（第n位乘客的座位号为n）。
第一位乘客喝醉后随机选择了一个座位（每个座位被选中的概率相等）。
其他乘客清醒时会按票就座，但若自己的座位已被占，则会随机选择一个空座位。

Q: 假设你是第100位乘客，求你坐到座位100的概率。

A: 在100名乘客登机的问题中，第一位乘客随机选择一个座位（每个座位被选中的概率相等），后续乘客如果发现自己的座位空闲则按票就座，否则随机选择一个空闲座位。目标是求第100位乘客坐到座位100的概率。

通过分析，发现无论乘客总数 $n$ 是多少（ $\geq 2$ ），最后一位乘客坐到自己的座位的概率始终为 $\frac{1}{2}$ 。这一结论可以通过以下关键观察得出：

座位 $1$ （第一位乘客的座位）和座位 $n$ （最后一位乘客的座位）在随机选择过程中扮演对称角色。
当有乘客被迫随机选择座位时（即发现自己的座位被占用），空座位集合包括座位1、座位 $n$ 和其他一些座位。
在随机选择过程中，座位 $1$ 和座位 $n$ 被选中的概率相等。
如果座位 $1$ 在座位 $n$ 之前被选中，则后续所有乘客（包括第 $n$ 位）都能坐到自己的座位，因此第 $n$ 位乘客坐到座位 $n$ 。
如果座位 $n$ 在座位 $1$ 之前被选中，则座位 $n$ 被提前占用，第 $n$ 位乘客无法坐到座位 $n$ 。
由于在每一步随机选择中，座位 $1$ 和座位 $n$ 被选中的概率相同，因此座位 $1$ 在座位 $n$ 之前被选中的概率为 $\frac{1}{2}$ ，这意味着第 $n$ 位乘客坐到座位 $n$ 的概率为 $\frac{1}{2}$ 。

对于 $n = 100$ ，这一概率同样适用。

因此，第100位乘客坐到座位100的概率为:

$\boxed{\dfrac{1}{2}}$

Python 实现

以下是使用Python实现的代码，通过模拟登机过程计算第100位乘客坐到座位100的概率，并验证理论值1/2：

import random
from typing import Setdef simulate_boarding(n: int, num_simulations: int) -> float:"""模拟乘客登机过程，计算最后一位乘客坐到正确座位的概率。根据概率理论，无论总乘客数多少(n≥2)，最后一位乘客坐到正确座位的概率恒为1/2。本函数通过蒙特卡洛模拟验证该理论。Args:n (int): 乘客总数（座位总数），要求n≥2num_simulations (int): 模拟实验次数Raises:ValueError: 如果n < 2Returns:float: 最后一位乘客坐到正确座位的概率估计值"""# 参数校验if n < 2:raise ValueError("乘客总数n必须至少为2")success_count = 0  # 记录成功次数（最后一位坐到正确座位）for _ in range(num_simulations):# 初始化座位状态：用集合跟踪剩余空座位available_seats: Set[int] = set(range(n))# 第一位乘客随机选座（0~n-1均匀分布）first_passenger_choice = random.choice(list(available_seats))available_seats.remove(first_passenger_choice)# 中间乘客（第2位到第99位）登机for passenger in range(1, n - 1):  # 乘客索引1到n-2（共n-2位）# 如果自己的座位空闲，直接入座if passenger in available_seats:available_seats.remove(passenger)# 座位被占则随机选择空座位else:chosen_seat = random.choice(list(available_seats))available_seats.remove(chosen_seat)# 最后一位乘客（第100位）登机：检查唯一剩余座位last_seat = available_seats.pop()if last_seat == n - 1:  # 检查是否是正确座位（索引n-1对应座位100）success_count += 1return success_count / num_simulations# 参数设置
PASSENGERS = 100  # 乘客总数
SIMULATIONS = 100_000  # 模拟次数# 执行模拟并打印结果
probability = simulate_boarding(n=PASSENGERS, num_simulations=SIMULATIONS)
print(f"模拟次数: {SIMULATIONS:,}")
print(f"第{PASSENGERS}位乘客坐到正确座位的概率: {probability:.6f}")
print(f"理论概率值: 0.500000")
print(f"绝对误差: {abs(probability - 0.5):.6f}")

代码说明

强类型规范：
- 所有变量和返回值均使用类型注解（如Set[int]）
- 函数参数明确标注类型（n: int）
- 添加了详细的文档字符串（docstring），包含参数说明和返回值解释
核心逻辑：
- 初始化：创建座位集合available_seats（0~99）
- 第一位乘客：随机选择任意座位
- 中间乘客：
  - 若自己座位空闲则入座
  - 若被占则随机选择空座位
- 最后一位乘客：检查剩余的唯一座位是否是99号（对应座位100）
概率计算：
- 通过success_count统计成功次数
- 返回成功频率作为概率估计值
理论验证：
- 打印理论值0.5作为参照
- 显示绝对误差验证准确性

输出示例

模拟次数: 100,000
第100位乘客坐到正确座位的概率: 0.502590
理论概率值: 0.500000
绝对误差: 0.002590

算法分析

时间复杂度： $num_simulations × n ) O(\text{num\_simulations} \times n)$ ，单次模拟需处理 $n$ 位乘客
空间复杂度： $O (n)$ ，维护座位集合
准确性：10万次模拟可使误差小于0.01（95%置信度）

这道面试题的本质是考察候选人将复杂随机过程抽象为概率模型的能力和利用递归与对称性进行问题降维的思维，这类能力直接对应量化金融中高频交易撮合、信用风险传染建模以及衍生品路径依赖定价的核心挑战。

🔑 核心知识点

随机过程建模
- 登机过程本质是带吸收态的马尔可夫链：座位占用状态转移具有无后效性
递归问题分解
- 当第 $k$ 位乘客发现座位被占时，问题规模递归降为 $n - k + 1$ 的子问题
概率不变性原理
- 关键洞察：最后一位乘客的成功概率恒为 $\frac{1}{2}$ （ $\ge 2$ ），与总人数无关
吸收态分析
- 座位 $1$ 和座位 $n$ 构成双吸收态，其被占顺序决定最终结果

📊 面试评估维度

考察维度	具体表现要求	本题对应点
随机建模能力	将现实场景转化为概率模型	识别座位占用过程的马尔可夫链特性
递归思维	建立自相似问题结构	当乘客随机选座时，问题规模递归减小
对称性洞察	发现系统隐含的不变量	证明座位1和n的对称性导致 $\frac{1}{2}$
金融映射能力	关联抽象模型与金融场景	类比信用违约链式反应（一家机构违约引发随机传染）或交易所订单流拥堵问题

🧩 典型回答框架

定义关键事件
- 事件A：第 $1$ 位乘客直接坐自己座位（概率 $\frac{1}{n}$ ）→ 第 $n$ 位必然坐对
- 事件B：第 $1$ 位乘客坐第n位座位（概率 $\frac{1}{n}$ ）→ 第 $n$ 位必然坐错
- 事件C：第 $1$ 位坐第 $k$ 位座位（ $\le k \le n - 1$ , 概率 $\frac{n-2}{n}$ ）
递归分解

$P_n = \frac{1}{n} \times 1 + \frac{1}{n} \times 0 + \frac{1}{n} \sum_{k=2}^{n-1} P_{n-k+1}$
- 当第1位占 $1$ 座时，第 $21$ 至 $k - 1$ 位正常入座，问题退化为 $n - k + 1$ 人子问题
数学归纳证明
- 基准情形： $n = 2$ 时 $P_2 = \frac{1}{2}$
- 假设 $P_m = \frac{1}{2}$ 对所有 $m < n$ 成立
- 代入递归式得 $P_n = \frac{1}{n} + \frac{n-2}{n} \cdot \frac{1}{2} = \frac{1}{2}$
对称性论证
- 在整个过程中，座位1和座位 $n$ 被随机选中的概率始终相等
- 第 $n$ 位坐对当且仅当座位 $n$ 比座位 $1$ 更晚被占用

💡 核心洞察

系统鲁棒性
- 无论乘客规模 $n$ 如何增大（ $\ge 2$ ），系统最终收敛到相同概率，反映复杂系统中的相变现象
金融场景隐喻
- 风险传染：类比首个机构违约后，风险在金融网络中随机扩散至特定机构的概率
- 订单流分析：高频交易中单一错误订单引发交易所撮合系统连锁反应的建模
模型扩展方向
- 若加入乘客选座偏好（如总是优先选择靠窗座位），模型可延伸至行为金融场景
- 若醉汉乘客数增加，可建模系统性风险压力测试的临界阈值