面試書中對票務線問題的答案的一些疑問
我正在閱讀一本名為《量化金融面試實用指南》（暱稱：綠皮書）的面試書，無法理解以下問題的答案：
問題：來自第 5/5.2 章
票務線路：
在劇院售票處， $ 2n $ 人們在等著買票， $ n $ 他們中只有 5 美元的鈔票，另一個 $ n $ 人們只有 10 美元的鈔票。售票員一開始沒有變化。如果每個人買一張5美元的票，那麼所有人都能夠在不改變位置的情況下購買他們的票的機率是多少？
我對答案有一些疑問（下面以粗體突出顯示），非常感謝您的建議。
以下是書中的答案：
將 +1 分配給 $ n $ 有 5 美元鈔票的人，並將 -1 分配給 $ n $ 有 10 美元鈔票的人。把這個過程想像成一次散步。讓 $ (a,b) $ 表示之後 $ a $ 步驟，步行結束於 $ b $ . 所以我們從 $ (0,0) $ 並達到 $ (2n,0) $ 後 $ 2n $ 腳步。對於這些 $ 2n $ 步驟，我們需要選擇 $ n $ 步數為+1，所以有 $ {2n \choose n} = 2n!/(n!*n!) $ 可能的路徑。我們對具有該屬性的路徑感興趣 $ b \geq 0 $ ， 對所有人 $ a<2n $ 和 $ a>0 $ .
更容易計算到達的補碼路徑的數量 $ b=-1 $ , ∃a<2n 和 a>0。如所附螢幕截圖所示
，如果我們在路徑首先達到 -1 後反映跨線 y = -1 的路徑。
懷疑：為什麼我們可以假設路徑達到-1，因為我認為我們對 b>=0 感興趣，而我們永遠不會達到低於 0 的 b
對於在第 2n 步到達 (2n,0) 的每條路徑，我們都有一個在第 2n 步到達 (2n,-2) 的對應反射路徑。對於到達 (2n,-2) 的路徑，有 +1 的 (n-1) 步和 -1 的 (n+1) 步。所以有
$$ 2n Cr (n-1) $$= 2n!/((n-1)!*(n+1)!) 這樣的路徑。假設路徑到達 (2n,0)，則具有屬性 b = -1, ∃ a<2n 和 a>0 的路徑數也是$$ 2n Cr (n-1) $$ 疑問：為什麼具有屬性 b = -1 的路徑數是$$ 2n Cr (n-1) $$?
並且具有屬性 b>=0, ∀ a<2n 和 a>0 的路徑數為：
$$ 2n Cr n $$-$$ 2n Cr (n-1) $$= (1/(n+1))*$$ 2n Cr n $$. 因此，所有人都能夠在不改變位置的情況下購買門票的機率是 1/(n+1)
我理解這種方法的方式：
- 你從 $ A = (0, 0) $ .
- 每當一個 5美元的人想買一張票時，您將一個單元向右移動並向上移動。
- 每次一個 10美元的人想買一張票，你就將一個單元向右移動並向下移動一個單元。
- 這樣一來，畢竟 $ 2n $ 有人為你服務，你得到一條從 $ A $ 並在某個時候結束 $ B = (2n, 0) $ .
- 所有可能路徑的數量很容易確定： $$ N_\text{total} = {2n \choose n} = \frac{(2n)!}{n! \cdot n!}. $$
- 我們只對有效路徑感興趣：這些是所有客戶都可以買票的路徑。如果路徑從不接觸或越過水平線，則該路徑是有效的 $ y = -1 $ . 這是為什麼？因為只有在他們前面有 5美元的人排隊時，才能為 10美元的人提供服務。例如，假設排隊的第一個人是 5美元的人，而排隊的第二個人是 10美元的人。那麼對應路徑的開頭是這樣的： $$ (0,0) \rightarrow (1,1) \rightarrow (2, 0). $$
- 現在可以使用反射原理來計算無效路徑的數量。讓我們記住所有路徑（有效和無效）都從 $ A = (0, 0) $ 並結束於 $ B = (2n, 0) $ . 現在讓我們考慮一個無效的路徑。因為這條路徑無效，所以存在一個點（比如說點 $ C $ ) 在它接觸線的這條路徑上 $ y = -1 $ （否則它將是一個有效的行）。所以我們有 $ C = (x, -1) $ 在哪裡 $ x > 0 $ 和 $ x < 2n $ .
- 現在我們構造反射路徑（如圖所示）：反射路徑與之間的原始路徑相同 $ A $ 和 $ C $ 並反映在 $ y = -1 $ 之間 $ C $ 和 $ B $ . 由於原始路徑結束於 $ B $ 新路徑結束於 $ \widetilde{B} = (2n, -2) $ . 總結一下：反射路徑從 $ A $ 至 $ \widetilde{B} $ .
- 請注意，每條無效路徑都雙射對應於一條反射路徑。因此無效路徑的數量與反射的無效路徑的數量相同。
- 無效路徑都開始於 $ A = (0, 0) $ 並結束於 $ \widetilde{B} = (2n, -2) $ . 這對應於與我們最初的問題類似的問題 $ n-1 $ 5 $人和 $ n+1 $ 10美元的人。因此無效路徑的數量等於 $$ N_\text{invalid} = {2n \choose n+1} = \frac{(2n)!}{(n+1)! \cdot (n-1)!}. $$
- 因此有效路徑的數量是 $$ N_\text{valid} =N_\text{total} - N_\text{invalid} $$.
- 最後一條有效路徑的機率是 $$ p = \frac{N_\text{valid}}{N_\text{total}} = 1 - \frac{n! \cdot n!}{(n+1)! \cdot (n-1)!} = 1 - \frac{n}{n+1} = \frac{1}{n+1}. $$