返回题库

翻牌喊红:最优胜率

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=Rn52nX_{n} = \frac{R_{n}}{52 - n} , 0n<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=Rn52n,0n<52.X_n=\frac{R_n}{52-n},\quad 0\le n<52.

给定前 n1n-1 张的信息(滤过 Fn1\mathcal{F}_{n-1}),第 nn 张为红的条件概率是 Rn152(n1)=Xn1\frac{R_{n-1}}{52-(n-1)}=X_{n-1}。而

Xn=Rn1Dn52n,X_n=\frac{R_{n-1}-D_n}{52-n},

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

E[XnFn1]=Xn1,\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}.