首页 > > > 10035 赌徒的长征(2)——递推法的困境
既然无法用简单的几句话证明阿聪策略的期望收益为0,那么我们就来算一算,这个策略的期望收益到底是多少。计算这种问题常用递推法。为了说明递推法的原理,我们拿胆小的赌徒小白作为例子:
小白策略:初始赌本为1块钱;赌注也是1块钱,且始终不变。如果赢到5块钱,那就见好就收;如果输光了,那也没办法了。在任一时刻,小白手里的钱数只能是0、1、2、3、4、5这几个数字之一,那么我们就把这个钱数作为状态。用
表示从赌本为
块钱的状态出发,到游戏结束时赌本的期望。显然
,
,因为
等于0或5时游戏就已经结束了,
就是最后的赌本。而对于
,由于下一局有一半的可能性赢(赌本变成
),有一半的可能性输(赌本变成
),所以有递推式:★![]()
根据这个递推式和边界条件
,
,容易算出
,也就是说,无论初始赌本是多少,赌到最后,期望都是不赔不赚的。
上面设了一个函数
,表示最终赌本的期望,而
才是期望收益。其实完全可以直接设
,递推式仍然是
★![]()
而边界条件变成了
。容易解得
,这也说明期望收益为0。
这种递推法,还可以用来求从赌本为
块钱的状态出发,最终输光的概率
。递推式仍然不变:
★![]()
边界条件是
,
。容易解得
,所以从手中有1块钱的状态出发,会有4/5的概率输光。
同样的递推法还可以用来求从赌本为
块钱的状态出发,到游戏结束为止,要赌的局数的期望
。这次的递推式变成了:
★![]()
式中的1表示先赌一局,后两项表示的是这一局之后,期望还要赌多少局。边界条件为
,可以解得
,
。这说明,从赌本为1块钱的状态出发,平均要赌4局才能结束。

,还取决于当前赌注
,二者合在一起才构成状态。用
表示从赌本为
、赌注为
的状态出发,到游戏结束为止的期望收益,则我们想求的是
。显然,
或
代表游戏已经结束,这些时候的
。对于其它状态,可以写出如下的递推式:
★![]()
显然
是一个满足递推式的解。但它是唯一解吗?我们还是要递推一下来看看。

取
,可以确定
。上图中的红线,连接了递推式涉及到的三个状态。
但不幸的是,从现在开始,无法再取得一对
,使得递推式中有两项已知、一项未知了。为了能够递推下去,必须设未知数。好吧,那就设我们要求的
。由此出发,可以依次求得
、
、
、
、
,每一步的依据,依次用红、橙、绿、蓝、紫线标了出来。

,由此可以求得
和
(红线、橙线)。此时,再利用
时的递推式(绿线),就能把
用
表示出来(
):



至此,我们不仅没能解出
这个未知数,反而又引入了一个新的未知数
。事实上,所有形如
(
为整数)的项都会引入新的未知数,未知数会越来越多。

阿聪的策略毕竟比较复杂,赌本、赌注都在变化。但其实,有一些比阿聪策略更简单的策略,用递推法一样会遇到困难。比如赌徒大白的策略:
大白策略:初始赌本为1块钱;赌注也是1块钱,且始终不变。如果出现三连胜,那就见好就收;如果输光了,那也没办法了。
与小白策略不同,大白一定要赌到三连胜,这使得赌局可能无限进行下去:赢、赢、输,赢、赢、输,赢、赢、输,一直不出现三连胜,但赌本却每三局涨1块钱。下面我们会看到,在这种存在“无限”的情况下,递推法又一次会失效。
大白策略中,赌注始终为1,所以不必包含在状态里。但是,状态需要记录到目前为止已经取得了几连胜。用
表示从赌本为
、已经取得
连胜的状态出发,到游戏结束为止的期望收益,则我们要求
。递推式为:
★边界条件为![]()
。递推过程如下,关系线使用的顺序为红、绿、蓝,红、绿、蓝……:
本身是解不出来的。

大白策略的递推法其实只差一个条件,就能解出未知数
。@Jack Diamond找到了这个条件。他发现,如果大白拿着2块钱入场,其实可以看作先拿1块钱入场,如果三连胜则结束,如果输光了,则再拿剩下的1块钱入场。这样,初始赌本为2时的期望收益,就可以分成两部分:一部分是初始赌本为1时的期望收益;另一部分还是初始赌本为1时的期望收益,不过只在第1块钱输光的情况下才取得。用
表示初始赌本为1时输光的概率,则上面的结论可以写成:
★![]()
而之前,我们设了
,并已经用递推法求得
,故有
★![]()
因为
,上式若把
约掉,则不可能成立,所以必有
。
事实上,
本身也能够求出来。用递推法,可以得到2块钱入场输光的概率为
:

。由此可解得
。
通过发掘隐藏条件,我们用递推法证明了大白策略的期望收益为0。不过阿聪策略到底还是比大白策略复杂得多,未知数都有无穷多个,要找到无穷多个隐藏条件,谈何容易!必须另辟蹊径。
原文作者:;如有侵权,请联系管理员删除。