赌博的最优策略(II)

作者:
系列:生活中的数学

查看该系列所有文章

在 slashdot 上看到一篇 科技新闻 ,两个数学家(其中一个来自于 MIT )和一个计算机学家,在 arXiv 上发表了一篇论文《HOW TO GAMBLE IF YOU』RE IN A HURRY》( PDF 版链接 ),是最近几天很热门的一条新闻。

其实论文的内容很简单,基本上就是我以前一篇博客 赌博的最优策略 里的内容:

假设有数量为 \( n\) 的本钱,赌博规则为每次可以压任意多的钱,赌博结果为以 \( p\) 的概率赢回同样多的钱(输了的话压出去的钱就没了)。如果赌博的目标是本钱增长到 \( N\) 或者破产(输光所有的钱为止)。问什么样的方式可以最大化成功(赢到 \( N\) 走人)的概率呢?

然后这篇文章里只考虑离散的情况,即 \( n\)\( N\) 都是整数,并且每次只能下整数的赌注。在这种情况下问题更简单了。如果不考虑结束的时间的话,赌博的策略如下:

如果 \( p<0.5\) ,那么每次下注 \( \min(n, N-n)\)

如果 \( p>0.5\) ,每次下注 1。

但当 \( p>0.5\) 时,每次下注 1 ,游戏结束的时间太长了。更优的方法是 Kelly 判据 ,即每次押上 \( 2p-1\) 倍的本金。在初始本金 n 为 100 , N 为 200 , p 为 3/5 时, Kelly 策略的成功概率为 99.988%,期望结束时间只有 45 轮,而每次下注 1 的期望结束时间是 500 轮。

那上面新闻里的论文做了什么工作呢?事实上,它给出了一个程序,用来计算用什么方式可以最大化在给定期限 \( T\) 内赢到 \( N\) 走人的概率(还有一些其它乱七八糟但也差不多的东西),即计算以下函数:

$$f(n, T) = \max_{1\leq x \leq \min(n, N-n) } \left((1-p)f(n-x, T-1) + pf(n+x,T-1)\right)$$

好吧,我也没明白这篇文章为何会这么热门,我认为 这个程序是一个本科生甚至一个高中生就可以完成的工作,这篇文章也不是严肃的学术性结果新闻里提到 作者之一 Evangelos Georgiadis 是来自 MIT 的数学家。但我在 MIT 上找不到该人的详细信息,深表怀疑他只是 MIT 的一个学生。

Q. E. D.

系列: 生活中的数学 »
年终奖多一块钱,税后反而少一千多。微博上有人在质疑这一点。但这是真的。咱们国家对于奖金所得税的扣税方式是证明政府部门二逼的最佳案例之一。
网络的力量太大,这两次把问题放到网上不到半天,这些问题不但被解答,而且连出处都被翻出来了。这让我自己少了很多思考的乐趣。以后不能把问题太快放到网上。
年终奖多一块钱,税后反而少一千多。微博上有人在质疑这一点。但这是真的。咱们国家对于奖金所得税的扣税方式是证明政府部门二逼的最佳案例之一。
巴林银行是英国最古老的投资银行,成立于 1763 年。由于   尼克 李森( Nick Leeson )未经授权在新加坡国际货币交易所( SIMEX )从事日经 225 股票指数期货合约交易失败,致使巴林银行亏损 8.3 亿英镑,这远远超出了该行的资本总额( 3.5 亿英镑)。银行破产后,以 1 英镑的象征性价格被荷兰国际集团收购。