從均勻分佈中採樣遞增序列的遊戲獲勝概率
這是我得到但無法解決的面試問題。
考慮一個兩人遊戲，其中 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 ，我們正在查看新採樣的數字大於上一個採樣的數字的概率 xj−1 . 這是 1−CDF 的均勻分佈，這只是 F(x)=x , 所以在 step 上獲得更大數字的概率 j 是 1−xj−1 . 但我不知道從這裡去哪裡。如果是離散抽樣，我可能會嘗試以 B 的最後一個數字為條件，但在這裡，我不確定該怎麼做。我仍然可以使用集成進行調節，但我不知道如何使用有關是否打開的信息 j ，我們正在考慮 A 或 B 或 A 先行。我的想法是我們使用平價 j 但不太確定如何。呼叫 A 的第一回合 j=1 ，我們有如果 j mod 2=0 然後輪到 B 如果 j mod 2=1 ，輪到了。因此，如果 j mod 2=1 , A 有概率輸 xj−1 但如果 j mod 2=0 , A 以概率獲勝 xj−1 ?
我的另一個思考過程是以圖形方式考慮問題。我正在描繪一個 1 x 1 的正方形，其中 x 和 y 軸分別代表 A 和 B 的數字。A 首先對一個數字進行採樣，這會立即縮小 B 的“安全”區域。這種情況一直持續到一名玩家輸掉。每一步，單位正方形的高和寬依次遞減 xj−xj−1 . 我也認識到，在 A 邁出第一步之後，我們基本上回到了同一個遊戲，只有一個起始位置 x1 代替 0 ，所以這可能涉及建立遞歸關係，但不知道如何。
我對如何解決這個問題的提示很滿意，但我也不介意解決方案。
您可以組合解決此問題，而無需使用微積分。所有你需要看的是第一個的概率 n 樣本按特定順序排列，對於任何特定順序，這很簡單 1/n!
遊戲結束後恰好 n 當且僅當第一個步驟 n−1 樣本是按遞增順序排列的，而最後一個樣本不是。最後一個樣本可以佔據任何 n 除了最高的位置，所以有 n−1 這樣的序列；因此遊戲在恰好結束後結束的概率 n 步驟是 n−1n! .
和 A 如果遊戲在偶數步後結束，則獲勝，所以 A 的獲勝概率為 ∞∑n=12n−1(2n!)=∞∑n=1(1(2n−1)!−1(2n!)) =∞∑n=1(−1)n+1n! =1−∞∑n=0(−1)nn! =1−1e
這對樣本的特定分佈沒有任何假設，只是它是連續的。所以無論分佈如何，答案都是一樣的。