ITPub博客

首页 > > > 10035 赌徒的长征(2)——递推法的困境

10035 赌徒的长征(2)——递推法的困境

作者:格伯纳 时间:2015-10-18 12:27:11 0 删除 编辑

  既然无法用简单的几句话证明阿聪策略的期望收益为0,那么我们就来算一算,这个策略的期望收益到底是多少。计算这种问题常用递推法。为了说明递推法的原理,我们拿胆小的赌徒小白作为例子:

小白策略:初始赌本为1块钱;赌注也是1块钱,且始终不变。如果赢到5块钱,那就见好就收;如果输光了,那也没办法了。
  在任一时刻,小白手里的钱数只能是0、1、2、3、4、5这几个数字之一,那么我们就把这个钱数作为状态。用f(m)表示从赌本为m块钱的状态出发,到游戏结束时赌本的期望。显然f(0) = 0,f(5) = 5,因为m等于0或5时游戏就已经结束了,m就是最后的赌本。而对于1 \le m \le 4,由于下一局有一半的可能性赢(赌本变成m+1),有一半的可能性输(赌本变成m-1),所以有递推式:
★ f(m) = \frac{1}{2} f(m+1) + \frac{1}{2} f(m-1) \quad (1 \le m \le 4)

根据这个递推式和边界条件f(0) = 0,f(5) = 5,容易算出f(m) = m,也就是说,无论初始赌本是多少,赌到最后,期望都是不赔不赚的。

  上面设了一个函数f(m),表示最终赌本的期望,而f(m) - m才是期望收益。其实完全可以直接设g(m) = f(m) - m,递推式仍然是


★ g(m) = \frac{1}{2} g(m+1) + \frac{1}{2} g(m-1) \quad (1 \le m \le 4)

而边界条件变成了g(0) = g(5) = 0。容易解得g(m) = 0,这也说明期望收益为0。

  这种递推法,还可以用来求从赌本为m块钱的状态出发,最终输光的概率p(m)。递推式仍然不变:


★ p(m) = \frac{1}{2} p(m+1) + \frac{1}{2} p(m-1) \quad (1 \le m \le 4)

边界条件是p(0) = 1,p(5) = 0。容易解得p(m) = 1 - m/5,所以从手中有1块钱的状态出发,会有4/5的概率输光。

  同样的递推法还可以用来求从赌本为m块钱的状态出发,到游戏结束为止,要赌的局数的期望T(m)。这次的递推式变成了:


★ T(m) = 1 + \frac{1}{2} T(m+1) + \frac{1}{2} T(m-1) \quad (1 \le m \le 4)

式中的1表示先赌一局,后两项表示的是这一局之后,期望还要赌多少局。边界条件为T(0) = T(5) = 0,可以解得T(1) = T(4) = 4,T(2) = T(3) = 6。这说明,从赌本为1块钱的状态出发,平均要赌4局才能结束。

  现在我们来研究阿聪的策略。与小白策略不同的是,赌局在将来的发展情况,不仅取决于当前赌本m,还取决于当前赌注n,二者合在一起才构成状态。用g(m,n)表示从赌本为m、赌注为n的状态出发,到游戏结束为止的期望收益,则我们想求的是g(2,1)。显然,m \le 0或n=0代表游戏已经结束,这些时候的g(m,n) = 0。对于其它状态,可以写出如下的递推式:


★ g(m,n) = \frac{1}{2} g(m+n, n-1) + \frac{1}{2} g(m-n, n+1) \quad (m > 0, n > 0)

显然g(m,n) \equiv 0是一个满足递推式的解。但它是唯一解吗?我们还是要递推一下来看看。

  取m=n=1,可以确定g(1,1) = 0。上图中的红线,连接了递推式涉及到的三个状态。

  但不幸的是,从现在开始,无法再取得一对(m,n),使得递推式中有两项已知、一项未知了。为了能够递推下去,必须设未知数。好吧,那就设我们要求的g(2,1) = x。由此出发,可以依次求得g(1,2)、g(3,1)、g(2,2)、g(4,1)、g(3,2),每一步的依据,依次用红、橙、绿、蓝、紫线标了出来。

  到这里又卡住了,只能继续设未知数。设g(5,1) = y,由此可以求得g(4,2)和g(1,3)(红线、橙线)。此时,再利用(m,n) = (3,2)时的递推式(绿线),就能把y用x表示出来(y=32x):

  用类似的方法,一直可以填到这么多:

但接下来又卡住了,因为橙线不能用了,蓝线也用不了:

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

  阿聪的策略毕竟比较复杂,赌本、赌注都在变化。但其实,有一些比阿聪策略更简单的策略,用递推法一样会遇到困难。比如赌徒大白的策略:

大白策略:初始赌本为1块钱;赌注也是1块钱,且始终不变。如果出现三连胜,那就见好就收;如果输光了,那也没办法了。

  与小白策略不同,大白一定要赌到三连胜,这使得赌局可能无限进行下去:赢、赢、输,赢、赢、输,赢、赢、输,一直不出现三连胜,但赌本却每三局涨1块钱。下面我们会看到,在这种存在“无限”的情况下,递推法又一次会失效。

  大白策略中,赌注始终为1,所以不必包含在状态里。但是,状态需要记录到目前为止已经取得了几连胜。用g(m,n)表示从赌本为m、已经取得n连胜的状态出发,到游戏结束为止的期望收益,则我们要求g(1,0)。递推式为:


★ g(m,n) = \frac{1}{2} g(m+1, n+1) + \frac{1}{2} g(m-1, 0) \quad (m > 0, 0 \le n \le 2)
边界条件为g(m,n) = 0 \quad (m = 0 \text{ or } n = 3)。递推过程如下,关系线使用的顺序为红、绿、蓝,红、绿、蓝……:

这样递推下去,虽然不会引入新的未知数,但x本身是解不出来的。

  大白策略的递推法其实只差一个条件,就能解出未知数x。@Jack Diamond找到了这个条件。他发现,如果大白拿着2块钱入场,其实可以看作先拿1块钱入场,如果三连胜则结束,如果输光了,则再拿剩下的1块钱入场。这样,初始赌本为2时的期望收益,就可以分成两部分:一部分是初始赌本为1时的期望收益;另一部分还是初始赌本为1时的期望收益,不过只在第1块钱输光的情况下才取得。用P表示初始赌本为1时输光的概率,则上面的结论可以写成:


★ g(2,0) = g(1,0) + P \cdot g(1,0)

而之前,我们设了g(1,0) = x,并已经用递推法求得g(2,0) = 6x,故有


★ 6x = x + Px

因为0 < P < 1,上式若把x约掉,则不可能成立,所以必有x=0。

  事实上,P本身也能够求出来。用递推法,可以得到2块钱入场输光的概率为6P-4:

而还有一个条件可以发掘出来:2块钱入场输光只有一种可能,即第1块钱输光,第2块钱也输光,故有6P-4 = P^2。由此可解得P = 3 - \sqrt{5}。

  通过发掘隐藏条件,我们用递推法证明了大白策略的期望收益为0。不过阿聪策略到底还是比大白策略复杂得多,未知数都有无穷多个,要找到无穷多个隐藏条件,谈何容易!必须另辟蹊径。

原文作者:;如有侵权,请联系管理员删除。

请登录后发表评论 登录
全部评论
管理员

注册时间:2018-03-30

  • 博文量
    2383
  • 访问量
    983773