红黑牌游戏的最佳策略(1)

KeyTo9_Fans

一副牌有$54$张，其中红色牌和黑色牌各有$27$张。

玩家的初始得分是$0$，一局游戏有$54$轮。

每轮游戏，庄家都会从没亮过的牌里随机选一张牌亮出来（每张牌被选中的概率相等）。

在亮牌前，玩家可以选择买红或者不买。

如果买红且庄家亮出了红色牌，那么玩家得$1$分；

如果买红且庄家亮出了黑色牌，那么玩家得$-1$分；

如果不买，那么亮牌后玩家的得分保持不变。

庄家亮过的牌会一直展示给玩家看，

因此玩家在每次亮牌前都可以根据庄家之前亮过的牌做决定。

玩家希望每局游戏得分之和的期望值尽可能大。

问每局游戏玩家得分之和的期望值是多少？

如果红色牌和黑色牌各有$n$张，那么每局游戏玩家得分之和的期望值是多少？

.·.·.

……不知为何firefox发不了图片（准确地说是打不开附件那个框）
或许该重装了……
以及图片画得很渣
题目很有趣，也很难，给出了一个编程计算的方法
然而没编程序

思想的核心是，利用国际象棋的残局进行枚举
不妨记终点（图片的右下角）为0，因为在这个点我们已经无利可图了。
然后，画格子，假设在终点，每向左边走一个格子，庄家手里就多一张红牌，每向上走一个格子，庄家手里就多一张黑牌
首先走一步，我们可以发现，从残局格子开始，往左数第i个格子的值应该是i（因为玩家知道庄家手里只有红牌了，于是玩家会选择买买买……）往上（直着往上不拐弯）的全部格子都是0
然后，假设现在在格子A=A(p,q)(有p张红牌和q张黑牌的格子)
EA(p,q)=max(在这个格子买的收益，在这个格子不操作的收益)
$E(A(p,q))=\frac{p}{p+q}E(A(p-1,q))+\frac{q}{p+q}E(A(p,q-1))+max(0，\frac{p}{p+q}-\frac{q}{p+q})$
然后，用动态规划或者递归
反正是一个二维的问题，并不麻烦

mathe

我们如果使用楼上的公式递推下去，除了继续包含E(A(.,.))的项，还会产生很多常数项。
其中每个常数项都是由某个E(A(x,y))产生($x>y$),这一项产生的值是E(A(x,y))本身的系数再乘上${x-y}/{x+y}$
而如果我们从某个E(A(p,q))出发利用上面公式反复递推到E(A(x,y)),在棋盘上相当于需要遍历所有从点(p,q)到(x,y)的最短路径
其中，每次从其中一个(u,v)移动到下一个(u-1,v)或(u,v-1)，产生的系数的分母都是u+v,而对应分子如果横坐标变化就是u，纵坐标变化就是v
由于乘法可以交换，而所有从(p,q)到(x,y)的路径都需要变化所有p->x的横坐标和q->y的纵坐标，所以每条(p,q)到(x,y)的最短路径都需要产生相同的系数
$\frac{p!q!(x+y)!}{(p+q)!x!y!}=\frac{C_{x+y}^x}{C_{p+q}^p}$,而所有这样的路径的数目有$C_{p+q-x-y}^{p-x}$
所以E(A(x,y))前面的系数是$\frac{C_{p+q-x-y}^{p-x}C_{x+y}^x}{C_{p+q}^p}$
需要注意上面的递推式对于$p=0$或$q=0$也都是成立的，由此我们得出
\(E(A(p,q))=\frac1{C_{p+q}^p}\sum_{x=1}^p\sum_{y=0}^{\min\{q,x-1\}} C_{p+q-x-y}^{p-x}C_{x+y}^x\frac{x-y}{x+y}\)
于是
\(E(A(p,p))=\frac1{C_{2p}^p}\sum_{x=1}^p\sum_{y=0}^{x-1} C_{2p-x-y}^{p-x}C_{x+y}^x\frac{x-y}{x+y}\)
\(E(A(p,p))=\sum_{x=1}^p\sum_{y=0}^{x-1} \frac{C_p^xC_p^y}{C_{2p}^{x+y}}\frac{x-y}{x+y}=\sum_{s=1}^{2p-1}\frac{1}{C_{2p}^s}\sum_{y=0}^{\lfloor\frac {s-1}2\rfloor}C_p^{s-y}C_p^y\frac{s-2y}s\)

mathe

这个比较难估算其近似值，计算机计算表明大概在$0.875\sqrt(p)$，而模型2中是$\sqrt(p/\pi)~=0.564\sqrt(p)$

mathe

我们可以先计算
\(\sum_{t=0}^sC_p^tC_p^{s-t}(s-2t)^2=s^2C_{2p}^s-4p(s-1)C_{2p-1}^{s-1}+4p(p-1)C_{2p-2}^{s-2}\)
\(\frac1{C_{2p}^s}\sum_{t=0}^sC_p^tC_p^{s-t}(s-2t)^2=s^2-4p(s-1)\frac{s}{2p}+4p(p-1)\frac{(s-1)s}{(2p-1)2p}\)
\(\frac1{C_{2p}^s}\sum_{t=0}^sC_p^tC_p^{s-t}(s-2t)^2=\frac{2ps-s^2}{2p-1}\)
所以\(\frac1{C_{2p}^s}\sum_{t=0}^sC_p^tC_p^{s-t}|s-2t|\le\sqrt{\frac1{C_{2p}^s}\sum_{t=0}^sC_p^tC_p^{s-t}(s-2t)^2}=\sqrt{\frac{2ps-s^2}{2p-1}}\)
\(E(A(p,p))=\sum_{s=1}^{2p-1}\frac{1}{C_{2p}^s}\sum_{y=0}^{\lfloor\frac {s-1}2\rfloor}C_p^{s-y}C_p^y\frac{s-2y}s\le \sum_{s=1}^{2p-1}\frac{1}{2}\sqrt{\frac{2p-s}{s(2p-1)}}\)
所以\(E(A(p,p))\le \sum_{s=1}^{2p-1}\frac{1}{2}\sqrt{\frac{2p-s}{s(2p-1)}}\le\sum_{s=1}^{2p-1}\frac{1}{2\sqrt{s}}\le\int_1^{2p}\frac{dx}{2\sqrt{x}}=\sqrt{2p}-1\)
于是结合策略(2)中结论，我们有\(\sqrt{\frac{p}{\pi}}\le E(A(p,p))\le\sqrt{2p}-1\)
还可以利用Beta函数，有更加精确一点的估计:
\[E(A(p,p))\le \sum_{s=1}^{2p-1}\frac{1}{2}\sqrt{\frac{2p-s}{s(2p-1)}}\le\int_0^{2p-1}\sqrt{\frac{2p-x}{x(2p-1)}}\frac{dx}2<\frac{p}{\sqrt{2p-1}}\int_0^1\sqrt{\frac{1-y}{y}}dy=\frac{p}{\sqrt{2p-1}}\int_0^1(1-y)^{\frac1 2}y^{-\frac1 2}dy=\frac{B(\frac1 2, \frac 3 2)p}{\sqrt{2p-1}}=\frac{\Gamma(\frac1 2)\Gamma(\frac3 2)p}{\Gamma(2)\sqrt{2p-1}}=\frac{\pi p}{2\sqrt{2p-1}}\]