量化面試綠皮書：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$ ），系統最終收斂到相同概率，反映復雜系統中的相變現象
金融場景隱喻
- 風險傳染：類比首個機構違約后，風險在金融網絡中隨機擴散至特定機構的概率
- 訂單流分析：高頻交易中單一錯誤訂單引發交易所撮合系統連鎖反應的建模
模型擴展方向
- 若加入乘客選座偏好（如總是優先選擇靠窗座位），模型可延伸至行為金融場景
- 若醉漢乘客數增加，可建模系統性風險壓力測試的臨界閾值