從均勻分佈中採樣遞增序列的遊戲獲勝概率
這是我得到但無法解決的面試問題。
考慮一個兩人遊戲，其中 A 和 B 輪流從均勻分佈中抽樣 $ U[0, 1] $ . 只要他們獲得不斷增加的序列，遊戲就會繼續。如果在任何時候，玩家獲得的數字小於最後一個數字（迄今為止最大的數字），則該玩家輸。A先行。A獲勝的概率是多少？
例如，如果序列是 $ 0.1 (A), 0.15 (B), 0.2 (A), 0.25 (B), 0.12 (A) $ ，那麼 A 輸了。
我認為因為A在第一回合沒有限製而B有，A的獲勝機會高於0.5。在任何給定的轉彎 $ j $ ，我們正在查看新採樣的數字大於上一個採樣的數字的概率 $ x_{j-1} $ . 這是 $ 1 - CDF $ 的均勻分佈，這只是 $ F(x) = x $ , 所以在 step 上獲得更大數字的概率 $ j $ 是 $ 1 - x_{j-1} $ . 但我不知道從這裡去哪裡。如果是離散抽樣，我可能會嘗試以 B 的最後一個數字為條件，但在這裡，我不確定該怎麼做。我仍然可以使用集成進行調節，但我不知道如何使用有關是否打開的信息 $ j $ ，我們正在考慮 A 或 B 或 A 先行。我的想法是我們使用平價 $ j $ 但不太確定如何。呼叫 A 的第一回合 $ j = 1 $ ，我們有如果 $ j~\mathrm{mod}~2 = 0 $ 然後輪到 B 如果 $ j~\mathrm{mod}~2 = 1 $ ，輪到了。因此，如果 $ j~\mathrm{mod}~2 = 1 $ , A 有概率輸 $ x_{j - 1} $ 但如果 $ j~\mathrm{mod}~2 = 0 $ , A 以概率獲勝 $ x_{j - 1} $ ?
我的另一個思考過程是以圖形方式考慮問題。我正在描繪一個 1 x 1 的正方形，其中 x 和 y 軸分別代表 A 和 B 的數字。A 首先對一個數字進行採樣，這會立即縮小 B 的“安全”區域。這種情況一直持續到一名玩家輸掉。每一步，單位正方形的高和寬依次遞減 $ x_{j} - x_{j - 1} $ . 我也認識到，在 A 邁出第一步之後，我們基本上回到了同一個遊戲，只有一個起始位置 $ x_1 $ 代替 $ 0 $ ，所以這可能涉及建立遞歸關係，但不知道如何。
我對如何解決這個問題的提示很滿意，但我也不介意解決方案。
您可以組合解決此問題，而無需使用微積分。所有你需要看的是第一個的概率 $ n $ 樣本按特定順序排列，對於任何特定順序，這很簡單 $ 1/n! $
遊戲結束後恰好 $ n $ 當且僅當第一個步驟 $ n-1 $ 樣本是按遞增順序排列的，而最後一個樣本不是。最後一個樣本可以佔據任何 $ n $ 除了最高的位置，所以有 $ n-1 $ 這樣的序列；因此遊戲在恰好結束後結束的概率 $ n $ 步驟是 $ \frac{n-1}{n!} $ .
和 $ A $ 如果遊戲在偶數步後結束，則獲勝，所以 $ A $ 的獲勝概率為 $$ \begin{align} \sum_{n=1}^\infty\frac{2n-1}{(2n!)} & = \sum_{n=1}^\infty\left(\frac{1}{(2n-1)!}-\frac{1}{(2n!)}\right) \ & = \sum_{n=1}^\infty\frac{(-1)^{n+1}}{n!} \ & = 1-\sum_{n=0}^\infty\frac{(-1)^n}{n!} \ & = 1 - \frac{1}{e} \end{align} $$
這對樣本的特定分佈沒有任何假設，只是它是連續的。所以無論分佈如何，答案都是一樣的。