返回题库

翻牌喊红：最优胜率

Well shuffled deck

专题
Probability / 概率
难度
L4

题目详情

概率题：翻牌喊红：最优胜率。

英文原题

You are playing the following game with a well shuffled deck of 52 cards facing down: at times n=1,2,…,52n = 1,2,\ldots ,52 , you turn over a new card and observe its color. Just once in this game, right before turning over a card, you must say "The next card is Red!" You win the game if the next card turned over is indeed red, and lose otherwise. Let RnR_{n} be the number of red cards remaining face down after the nn th card has been turned over. Show that Xn=Rn52−nX_{n} = \frac{R_{n}}{52 - n} , 0≤n<520 \leq n < 52 , is a martingale. Show that there is no strategy that guarantees winning with probability higher than 12\frac{1}{2} .

解析

设第 nn 张翻开后，剩余未翻红牌数为 RnR_n，则

Xn=Rn52−n,0≤n<52.X_n=\frac{R_n}{52-n},\quad 0\le n<52.

给定前 n−1n-1 张的信息（滤过 Fn−1\mathcal{F}_{n-1}），第 nn 张为红的条件概率是 Rn−152−(n−1)=Xn−1\frac{R_{n-1}}{52-(n-1)}=X_{n-1}。而

Xn=Rn−1−Dn52−n,X_n=\frac{R_{n-1}-D_n}{52-n},

其中 Dn∈{0,1}D_n\in\{0,1\} 表示第 nn 张是否为红。直接计算可得

E[Xn∣Fn−1]=Xn−1,\mathbb{E}[X_n\mid\mathcal{F}_{n-1}]=X_{n-1},

所以 XnX_n 是鞅。

你选择喊“红”的时刻等价于一个停时 τ\tau，在该时刻喊红的胜率就是 P(下一张红∣Fτ)=Xτ\mathbb{P}(\text{下一张红}\mid\mathcal{F}_\tau)=X_\tau。

由可选停止定理：

E[Xτ]=E[X0]=2652=12.\mathbb{E}[X_\tau]=\mathbb{E}[X_0]=\frac{26}{52}=\frac12.

因此任意策略的平均胜率都不超过 1/21/2，更不可能保证超过 1/21/2：

最优也只能做到 12.\boxed{\text{最优也只能做到 }\frac12}.

英文解析

Xn=Rn52−n,0≤n<52.X_n=\frac{R_n}{52-n},\quad 0\le n<52. Xn=Rn−1−Dn52−n,X_n=\frac{R_{n-1}-D_n}{52-n}, E[Xn∣Fn−1]=Xn−1,\mathbb{E}[X_n\mid\mathcal{F}_{n-1}]=X_{n-1}, E[Xτ]=E[X0]=2652=12.\mathbb{E}[X_\tau]=\mathbb{E}[X_0]=\frac{26}{52}=\frac12.