三国杀中的概率学问题3——王荣

前言

本文是三国杀中的概率学问题系列文章中的一篇，将详细讨论王荣吉占的期望摸牌数问题。并加上连续情形作为拓展。

值得说明的是，本文的思路受到了一篇文章的启发，在此特别鸣谢，这是文章的链接。

王荣吉占的期望摸牌数

王荣的二技能吉占很有意思，展示牌堆顶的一张牌，然后猜测下一张牌比这张牌大还是比这张牌小，猜对了就继续猜，直到猜错为止，然后最终可以获得展示的所有牌。所以即便第一次就猜错，也能拿到2张牌（第一张展示的牌，和猜错的这张牌）。为了能够摸更多的牌，我们需要采取贪心的猜牌策略，保证自己这次猜对的概率最大。也就是说，在展示的牌为1-6时，我们选择猜大，8-13时猜小，7的时候由于猜大和猜小的概率一样，所以猜大猜小都可以。

离散情形

为了使得模型更一般化，将13种不同的点数改为n种不同的点数。那么问题可以重新描述如下：

问题：牌有1~n这n种点数，我们先亮出第一张牌，然后猜测下一张牌跟这一张牌的大小关系，然后亮出下一张牌，若猜对则继续猜，猜错就停止。求在最优策略下平均能亮出几张牌。

由于牌堆为理想牌堆，不管怎么拿牌，每种点数的牌的张数都是一样的，所以最优策略即为：若当前牌的点数小于等于$\frac{n+1}{2}$，就猜大，否则猜小。

我们令$f(x)$表示当前牌的点数为$x$时，后面会亮出的牌数的数学期望。那么，我们可以得到下面的公式：

$$f(x)=\{\begin{array}{ll}{\sum }_{i=x+1}^n\frac{1}{n}f(i)+1& 0\le x\le \frac{n+1}{2}\\ {\sum }_{i=1}^{x-1}\frac{1}{n}f(i)+1& \frac{n+1}{2}<x\le 1\end{array}$$

解释一下这个公式，当前牌的点数为$x$时，首先会亮出下一张牌，这是+1的含义。然后下一张牌是每个点数的概率都是$\frac{1}{n}$，把猜对了能亮出的牌数乘以概率累加起来，就是猜对了之后期望亮出的牌数。分成两段也仅仅是因为猜测策略的原因。

我们要求的是平均能亮出几张牌，假设这个数量为$E$，那么$E=\frac{1}{n}{\sum }_{i=1}^{n}f(i)+1$

首先先亮出一张牌，然后这张牌的点数有n种可能性，即有$\frac{1}{n}$的概率为i。如果第一张牌是i的话，则期望亮出的牌数就是$f(i)$。于是我们把概率乘以亮出牌数累加起来，就是接下来会亮出的牌数，即$\frac{1}{n}{\sum }_{i=1}^{n}f(i)$。再加上第一张亮出的牌，就是$\frac{1}{n}{\sum }_{i=1}^{n}f(i)+1$了。$E$就是我们想求的答案。

接下来我们来算出$f(x)$的具体值。

我们设出$f(x)$的前缀和。令$F(x)={\sum }_{i=1}^{n}f(i)$

当$\frac{n+1}{2}<x\le 1$时：

$f(x)=\frac{1}{n}F(x-1)+1$

$F(x-1)=nf(x)+n$

将$x+1$代入$x$得：

$F(x)=nf(x+1)+n$

两式相减得：

$f(x)=nf(x+1)-nf(x)$

于是得到了$f(x)$的递推式

$f(x+1)=\frac{n+1}{n}f(x)$

由于$n$为常数，于是我们发现在$\frac{n+1}{2}<x\le 1$上，$f(x)$是等比数列。

类似地，在$0\le x\le \frac{n+1}{2}$上求得$f(x+1)=\frac{n}{n+1}f(x)$

可以发现，$f(x)$是一列以$\frac{n+1}{2}$为对称轴，先递减，后递增的两段等比数列，公比分别为$\frac{n}{n+1}$和$\frac{n+1}{n}$。

等比数列的求和公式为$S=a_1\ast \frac{q^n-1}{q-1}$，现在公比已经知道了，所以要求首项。$f(\frac{n+1}{2})$位于两段的连接处，可以让它作为两段等比数列的首项。现在我们来求$f(\frac{n+1}{2})$。

我们不妨假设$n$为奇数，这样$x=\frac{n+1}{2}$在公式的两段上都可以成立。于是有

$f(\frac{n+1}{2})={\sum }_{i=\frac{n+3}{2}}^n\frac{1}{n}f(i)+1={\sum }_{i=1}^{\frac{n-1}{2}}\frac{1}{n}f(i)+1$

$(2+\frac{1}{n})f(\frac{n+1}{2})=\frac{1}{n}F(n)+2$

$f(\frac{n+1}{2})=\frac{1}{2n+1}F(n)+\frac{2n}{2n+1}$

利用$f(x)$的对称性，以及等比数列求和公式，有

$F(n)={\sum }_{i=1}^{\frac{n-1}{2}}f(i)+{\sum }_{i=\frac{n+1}{2}}^{n}f(i)={\sum }_{i=\frac{n+3}{2}}^{n}f(i)+{\sum }_{i=\frac{n+1}{2}}^{n}f(i)=\frac{n+1}{n}f(\frac{n+1}{2})\frac{(\frac{n+1}{n}{)}^{\frac{n-1}{2}}-1}{\frac{n+1}{n}-1}+f(\frac{n+1}{2})\frac{(\frac{n+1}{n}{)}^{\frac{n+1}{2}}-1}{\frac{n+1}{n}-1}=[2n(\frac{n+1}{n}{)}^{\frac{n+1}{2}}-2n-1]f(\frac{n+1}{2})$

联立两式
$$\{\begin{array}{l}f(\frac{n+1}{2})=\frac{1}{2n+1}F(n)+\frac{2n}{2n+1}\\ F(n)=[2n(\frac{n+1}{n}{)}^{\frac{n+1}{2}}-2n-1]f(\frac{n+1}{2})\end{array}$$

解得
$$\{\begin{array}{l}f(\frac{n+1}{2})=\frac{n}{2n+1-n(\frac{n+1}{n}{)}^{\frac{n+1}{2}}}\\ F(n)=\frac{n[\frac{2n}{2n+1}(\frac{n+1}{n}{)}^{\frac{n+1}{2}}-1]}{1-\frac{n}{2n+1}(\frac{n+1}{n}{)}^{\frac{n+1}{2}}}\end{array}$$

于是，可以得到

$E={\sum }_{i=1}^n\frac{1}{n}f(i)+1=\frac{1}{n}F(n)+1=\frac{1}{\frac{2n+1}{n}(\frac{n}{n+1}{)}^{\frac{n+1}{2}}-1}$

当$n=13$时，$E\approx 4.232$

当$n\to \infty$时，$li{m}_{n\to \infty }E=li{m}_{n\to \infty }\frac{1}{2(1-\frac{1}{n+1}{)}^{\frac{n+1}{2}}-1}=\frac{1}{2e^{-\frac{1}{2}}-1}\approx 4.69$

至此，原题就解出来了。

连续情形

我们再做一点点扩展，看看在$n$趋于无穷时的情况。现在我们把问题转化为连续的情况。

问题：在[0,1]区间上的均匀分布总体进行依次采样，约定若采样得到的随机数小于$\frac{1}{2}$，则猜测下一次采得的随机数会更大；若采样得到的随机数大于$\frac{1}{2}$，则猜测下一次采得的随机数会更小。若猜测正确，则继续猜；若猜测错误，则采样终止。求采样次数的数学期望。

设$f(x)$表示当前点为$x$时，继续猜测的次数。给出$f(x)$的表达式如下：
$$f(x)=\{\begin{array}{ll}{\int }_x^{1}f(t)dt+1& 0\le x\le \frac{1}{2}\\ {\int }_0^{x}f(t)dt+1& \frac{1}{2}<x\le 1\end{array}$$
值得说明的是，$x=\frac{1}{2}$的情况对于两个公式都成立。这个式子是怎么得出来的呢？现在的点是$x$，我们先要按上述规则进行一次猜测（这是+1的含义）。如果猜错了，我们就失去了继续猜测的机会。如果猜对了，那么我们可以继续猜测。假设下一个点是$t$，这样的概率为$dt$，继续猜测的次数为$f(t)$。这样做一个积分（可以理解为加权平均）就能得到$f(x)$的表达式了。

假设$E$为采样次数的数学期望，那么$E={\int }_0^{1}f(t)dt+1$

这个式子的含义是，先随机出现一个点（这是+1的含义），再按照这个点的值进行加权平均（也就是积分的含义）。

$E$就是在连续情形下，王荣的摸牌数。

接下来，我们开始解这个函数。

首先，发现一个很简单的事实，$f(0)=f(1)=E$

显然，这个函数关于$x=\frac{1}{2}$是对称的。那么，我们来求一下$f(\frac{1}{2})$的值。

$f(\frac{1}{2})={\int }_{\frac{1}{2}}^{1}f(t)dt+1={\int }_0^{\frac{1}{2}}f(t)dt+1$

$2f(\frac{1}{2})={\int }_0^{1}f(t)dt+2=E+2$

$f(\frac{1}{2})=\frac{1}{2}E+\frac{1}{2}$

当$0\le x\le \frac{1}{2}$时，我们对$f(x)={\int }_x^{1}f(t)dt+1$两边求导，得

$f^{\prime }=-f$

这是一个比较简单的常微分方程，接下来需要一点点常微分方程的知识。

$\frac{df}{dx}=-f$

$\frac{df}{f}=-dx$

$dlnf=-dx$

$lnf=-x+C_1$

$f=e^{-x+C_1}=C{e}^{-x}$

于是我们解得$f=C{e}^{-x}$

代入$x=0$和$x=\frac{1}{2}$得
$$\{\begin{array}{l}C{e}^0=E\\ C{e}^{-\frac{1}{2}}=\frac{1}{2}E+\frac{1}{2}\end{array}$$

解得$C=E=\frac{1}{2e^{-\frac{1}{2}}-1}$

于是得到，当$0\le x\le \frac{1}{2}$时，$f(x)=\frac{e^{-x}}{2e^{-\frac{1}{2}}-1}$

由于$f(x)$关于$x=\frac{1}{2}$对称，可对称地写出$\frac{1}{2}<x\le 1$的情况。于是我们可以得到$f(x)$的表达式。

$$f(x)=\{\begin{array}{ll}\frac{e^{-x}}{2e^{-\frac{1}{2}}-1}& 0\le x\le \frac{1}{2}\\ \frac{e^{x-1}}{2e^{-\frac{1}{2}}-1}& \frac{1}{2}<x\le 1\end{array}$$

$E=\frac{1}{2e^{-\frac{1}{2}}-1}\approx 4.69$即为我们所求的答案。

可以发现，连续情形就是离散情形在$n\to \infty$时的情况。而指数函数在离散情形下对应的其实就是等比数列。

总结

本文先将问题作为离散情形进行处理，将问题中的n=13推广到了n为任意奇数的情况（偶数情形略有不同，也可以做，但是没有什么意义，笔者就没有单独列出了）。并且将问题推广到了$n$为$+\infty$的情形，即连续情形。从而彻底解出了王荣吉占背后的数学模型。