赌博的最优策略 (II)

作者: , 共 968 字
系列:生活中的数学

查看该系列所有文章

在 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.

系列: 生活中的数学 »
年终奖多一块钱,税后反而少一千多。微博上有人在质疑这一点。但这是真的。咱们国家对于奖金所得税的扣税方式是证明政府部门二逼的最佳案例之一。
网络的力量太大,这两次把问题放到网上不到半天,这些问题不但被解答,而且连出处都被翻出来了。这让我自己少了很多思考的乐趣。以后不能把问题太快放到网上。
类似文章:
相似度: 0.394
首先申明一下,赌博是不对的,下面的讨论也更多是理论性的。
数学 » 赌博
何时适合而止中,我们提到一个有趣的硬币问题,抛一个硬币,选择合适的时点,使得正面数与总次数的比值最大。这个问题目前还没有被完全解决,之前我们也只是用模拟法逼近了一下结果
相似度: 0.154
投资 » 凯利判据
凯利判据(英文 wikipedia)是一种人们在面对不确定事物时的选择标准,更准确地说,凯利判据是效应函数为「log 函数」的投资者(或赌徒)的决策方式。下面直接用一个例子来说明:
一个游戏:持续的抛一个均匀硬币,直到抛到出现反面为止,假设在之前你抛除了\( k\) 次正面,你将得到\( 2^{k+1}\) 次方这么多钱。
相似度: 0.069
最近看到一个有趣的问题:
最佳约会策略里,我们提到,如果有 100 个女孩可以顺序挑选,那么最好的方法是先看前 37 个,然后在剩下的女孩里选择当时最好的那个女孩,这样有接近 40%的概率挑选到最好的那个女孩。同时,不可能有更好的策略
相似度: 0.064
这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自姚期智教授的理论计算机( I )的授课内容——我是其助教之一。
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本On the graph isomorphism problem
年终奖多一块钱,税后反而少一千多。微博上有人在质疑这一点。但这是真的。咱们国家对于奖金所得税的扣税方式是证明政府部门二逼的最佳案例之一。
巴林银行是英国最古老的投资银行,成立于 1763 年。由于   尼克 李森( Nick Leeson )未经授权在新加坡国际货币交易所( SIMEX )从事日经 225 股票指数期货合约交易失败,致使巴林银行亏损 8.3 亿英镑,这远远超出了该行的资本总额( 3.5 亿英镑)。银行破产后,以 1 英镑的象征性价格被荷兰国际集团收购。