返回题库

递增随机数游戏：先手胜率

Increasing Random Numbers Game

专题
Probability / 概率
难度
L4

题目详情

两人轮流从 Unif[0,1]\mathrm{Unif}[0,1] 抽样，形成序列 X1,X2,…X_1,X_2,\ldots。只要序列严格递增游戏继续；第一次抽到的数小于上一次抽到的数的人输。

若你先手，获胜概率是多少？

We play a game by taking turns sampling values from a Uniform[0, 1] distribution. The game continues as long as the sequence is strictly increasing. The first person to draw a number smaller than the previous one loses. If you go first, what is your probability of winning?

解析

设游戏在第 kk 次抽样时首次失败（即 X1<⋯<Xk−1X_1<\cdots<X_{k-1} 但 Xk<Xk−1X_k<X_{k-1}）。

对连续分布，kk 个样本的相对大小顺序等可能。事件“前 k−1k-1 个严格递增”意味着在 kk 个数的全排列中，前 k−1k-1 个必须是递增的那一种顺序，占比 1/(k−1)!1/(k-1)!。在此条件下，要在第 kk 次失败等价于 XkX_k 不是这 kk 个数中的最大值，共有 k−1k-1 种可能位置，因此

P(L=k)=k−1k!.\mathbb{P}(L=k)=\frac{k-1}{k!}.

你在 kk 为偶数时获胜（对手抽到了失败那步），所以

P(Win)=∑j=1∞P(L=2j)=∑j=1∞2j−1(2j)!.\mathbb{P}(\text{Win})=\sum_{j=1}^{\infty}\mathbb{P}(L=2j)=\sum_{j=1}^{\infty}\frac{2j-1}{(2j)!}.

并且

2j−1(2j)!=1(2j−1)!−1(2j)!,\frac{2j-1}{(2j)!}=\frac{1}{(2j-1)!}-\frac{1}{(2j)!},

因此

P(Win)=(11!−12!)+(13!−14!)+⋯=1−e−1.\mathbb{P}(\text{Win})=\left(\frac{1}{1!}-\frac{1}{2!}\right)+\left(\frac{1}{3!}-\frac{1}{4!}\right)+\cdots =1-e^{-1}.

答案：1−e−1≈0.6321\boxed{1-e^{-1}}\approx 0.6321。