圣彼得堡游戏的悖论

KeyTo9_Fans

圣彼得堡游戏只有一个玩家，玩法如下：

=====
不断地抛一枚硬币，直到抛到反面朝上为止。

记此时一共抛出正面朝上的次数为$k$，那么玩家得到$2^k$块钱。
=====

也就是说，对于每次游戏，玩家都是：

以$1/2$的概率获得$1$块钱；
以$1/4$的概率获得$2$块钱；
以$1/8$的概率获得$4$块钱；
以$1/16$的概率获得$8$块钱；
以$1/32$的概率获得$16$块钱；
……
依次类推。

所得钱数的期望值是$1/2+1/2+1/2+1/2+1/2+......=+\infty$块钱。

也就是说，理论上玩家愿意付出任意多块钱来玩这个游戏。

现在我们规定第$i$次玩这个游戏需要付$i$块钱，

然后假设玩家采取以下策略：

=====
如果当前的盈亏总额大于$0$，那么就不再玩了；

否则继续玩，直到盈亏总额大于$0$为止。
=====

于是问题来了：

问题$1$：

求玩家最终的盈亏总额大于$0$的概率$p$。

这意味着玩家有$(1-p)$的概率无穷无尽地玩下去，永不盈利。

问题$2$：

如果规定第$i$次玩这个游戏需要付$f(i)$块钱，$f$是一个单调递增函数，

那么$f$至高以什么速度增长的时候，我们有$p=1$？

这意味着如果$f$增长得再快一些，玩家永不盈利的概率就大于$0$了。

#####

参考文献：
http://baike.baidu.com/view/1163899.htm

与文献中的描述相比，此贴把该游戏的奖金减半了，

但货币可以用任意单位来度量，所以实质上还是相同的游戏。

KeyTo9_Fans

此问题已贴出$2$年，没有收到回复，下面公布问题$1$的答案。

第$1$次游戏花$1$块钱，有$50%$的概率达到正盈利；

如果第$1$次游戏没有达到正盈利，那么第$2$次游戏花$2$块钱，有$25%$的概率达到正盈利，于是前$2$轮游戏共有$62.5%$的概率达到正盈利；

依次类推，可算得第$3$次、第$4$次、……、第$n$次游戏达到正盈利的概率。

通过一个时间复杂度为$O(n^3\log n)$，空间复杂度为$O(n^2)$的算法，可以算得在$2^0$、$2^1$、……、$2^14$轮游戏之内达到正盈利的概率，如下表所示：

1. 游戏次数        盈利概率
   
2. 1            0.5000000000
   
3. 2            0.6250000000
   
4. 4            0.7265625000
   
5. 8            0.7773361206
   
6. 16           0.8008533231
   
7. 32           0.8115877471
   
8. 64           0.8164711727
   
9. 128          0.8187391974
   
10. 256          0.8198162663
    
11. 512          0.8203368602
    
12. 1024         0.8205917213
    
13. 2048         0.8207175457
    
14. 4096         0.8207799940
    
15. 8192         0.8208110863
    
16. 16384        0.8208265955

复制代码

再通过数值分析方法，得到当$n->\infty$时，$n$轮游戏之内能达到正盈利的概率是$p=0.8208420767$，如下图所示：



也就是说，即使这是一个期望值为正无穷大的概率游戏，玩家理论上愿意付出任意多钱来玩这个游戏，

但是在楼主设定的游戏规则下，玩家仍然有$1-p=0.1791579233$的概率会无穷无尽地玩下去，永不盈利。

这就是该游戏的神奇之处。

#####

此为楼主对问题$1$的解答。

期待高人给出问题$2$的解答。

wayne

感觉事件空间有点乱, 此概率非彼概率.

如果严格的以 当前的盈亏总额大于0，那么就不再玩了； 作为游戏终止的条件,那么问题是不是应该这么表达:

玩家玩$1$次,因为盈亏额开始转正, 而终止游戏 的 这个事件发生的概率是 $1/2$
玩家玩$2$次,因为盈亏额开始转正, 而终止游戏 的  这个事件发生的概率是 $0$, ( 因为 第一次必须是反面,(如果是正面的话总盈亏为 $2-1>0$, 游戏本应该提前结束的), 那么总盈亏的最大值$ 2-1-2 = -1$,
玩家玩$3$次,因为盈亏额开始转正, 而终止游戏 的 这个事件发生的概率是 $0$, ( 因为 总盈亏最大的值为 $2^2-1-2-3=-2$, 不可能能玩3次就满足终止条件.
玩家玩$4$次,因为盈亏额开始转正, 而终止游戏 的 这个事件发生的概率是 $0$, ( 因为 总盈亏最大的值为 $2^3-1-2-3-4=-2$, 不可能能玩4次就满足终止条件.
玩家玩$5$次,因为盈亏额开始转正, 而终止游戏 的 这个事件发生的概率是 $1/32$, ( 因为 总盈亏为正只有一种情况,就是$[-++++]$, 盈亏值为 $2^4-1-2-3-4-5=1$
.....

KeyTo9_Fans

注意，是第$i$次【游戏】付$i$块钱，而不是第$i$次【抛硬币】付$i$块钱。

【一次游戏】的定义是【不断地抛一枚硬币，直到抛到反面朝上为止。记此时一共抛出正面朝上的次数为$k$，那么玩家得到$2^k$块钱】。

也就是说，只要玩家没有抛到反面朝上，【一次游戏】可以抛任意多次硬币。

每次游戏以抛到反面朝上为游戏结束，然后玩家根据此次游戏所抛出的正面朝上的次数获得此次游戏的奖金。

mathe

可以看成一次游戏有无穷个结果，其中$1/{2^h}$概率获得$2^{h-1}$元，而不需要抛很多次硬币。
然后第i次玩游戏需要压上费用i元。
虽然数值计算看是去问题1中p的极限小于1，但是我不确定。理论分析可以看出如果极限是1，必然逼近速度及其缓慢

wayne

KeyTo9_Fans 发表于 2017-5-31 14:55
注意，是第$i$次【游戏】付$i$块钱，而不是第$i$次【抛硬币】付$i$块钱。

【一次游戏】的定义是【不断地 ...

有点慢热哈, 现在才幡然醒悟, 这个已经不是数学题了.
=======================
啥都不说了.我比较好奇的是Fans的第1问是怎么计算出来的.
尤其是程序是如何巧妙处理无穷次投币的情况, 该不会是一个有可能永远不能退出的while循环吧.  让我们把舞台的灯光 都聚焦起来,打在这里,  

mathe

我们只要记录第i步后，玩家还亏损0,1,2,...,i(i+1)/2元的概率就可以了，而且显然这个概率是一个最多i+1比特的二进制有限小数（如果要准确表示，空间复杂度应该是O(n^3)).然后递推下去即可。计算还是比较容易的，只是n太大时就计算不下去了。

KeyTo9_Fans

可以证明极限小于$1$。

首先证明以下命题：

$9$次游戏所得钱数之和不多于$72$的概率至少是$0.5594...$。

证明：

因为$1$次游戏所得钱数不多于$8$的概率是$15/16$，

所以$9$次游戏所得钱数都不多于$8$的概率是$(15/16)^9$，

也就是$9$次游戏所得钱数之和不多于$8*9=72$的概率至少是$(15/16)^9=0.5594...$。

证毕。

接下来要用到切比雪夫不等式：

与期望值相差$k$个标准差以上的值，数目不多于$1/k^2$。

通过这个不等式可以证明以下命题：

$81$次游戏所得钱数之和不多于$3618$的概率至少是$0.4357...$。

证明：

因为对于每次游戏，前$2$次都是正面朝上的概率是$1/4$，方差是$1/4*3/4=3/16$，标准差是$\sqrt{3}/4$，

所以$81$次游戏里，前$2$次都是正面朝上的游戏次数的期望值是$81/4$，标准差是${9\sqrt{3}}/4$，

该期望值与$27$相差$27-81/4=27/4$，标准差的倍数为$k=27/{9\sqrt{3}}=\sqrt{3}$。

所以根据切比雪夫不等式，前$2$次都是正面朝上的游戏次数达到$27$次以上的概率小于等于$1/k^2=1/3$；

现在考虑$81$次游戏里，前$2$次都是正面朝上的游戏次数为$27$次以下的情况，该情况发生的概率至少是$1-1/3=2/3$。

对于前$2$次都是正面朝上的情况，所得钱数之和不多于$2^7*27=3456$的概率至少是$(63/64)^{27}=0.6536...$，

其余情况所得钱数之和不多于$2*81=162$，

综上所述，$81$次游戏所得钱数之和不多于$3456+162=3618$的概率至少是$0.6536...*2/3=0.4357...$。

证毕。

接下来可以证明以下命题：

$729$次游戏所得钱数之和不多于$169290$的概率至少是$0.6234...$。

证明：

因为$729$次游戏里，前$2$次都是正面朝上的游戏次数的期望值是$729/4$，标准差是${27\sqrt{3}}/4$，

该期望值与$243$相差$243-729/4=243/4$，标准差的倍数为$k=243/{27\sqrt{3}}=3\sqrt{3}$。

所以根据切比雪夫不等式，前$2$次都是正面朝上的游戏次数达到$243$次以上的概率小于等于$1/k^2=1/27$；

现在考虑$729$次游戏里，前$2$次都是正面朝上的游戏次数为$243$次以下的情况，该情况发生的概率至少是$1-1/27=26/27$。

此时再次使用切比雪夫不等式，得到前$4$次都是正面朝上的游戏次数为$81$次以上的概率小于等于$1/9$。

现在考虑前$2$次都是正面朝上的游戏里，前$4$次都是正面朝上的游戏次数为$81$次以下的情况，该情况发生的概率至少是$1-1/9=8/9$。

对于前$4$次都是正面朝上的情况，所得钱数之和不多于$2^11*81=165888$的概率至少是$(255/256)^{81}=0.7283...$，

其余情况所得钱数之和不多于$2*729+8*243=3402$，

综上所述，$729$次游戏所得钱数之和不多于$165888+3402=169290$的概率至少是$0.7283...*8/9*26/27=0.6234...$。

证毕。

接下来可以证明以下命题：

$6561$次游戏所得钱数之和不多于$8016570$的概率至少是$0.7469...$。

证明：

根据切比雪夫不等式，$6561$次游戏里，前$2$次都是正面朝上的游戏次数达到$2187$次以上的概率小于等于$1/243$；

现在考虑$6561$次游戏里，前$2$次都是正面朝上的游戏次数为$2187$次以下的情况，该情况发生的概率至少是$1-1/243=242/243$。

此时再次使用切比雪夫不等式，得到前$4$次都是正面朝上的游戏次数为$729$次以上的概率小于等于$1/81$。

现在考虑前$2$次都是正面朝上的游戏里，前$4$次都是正面朝上的游戏次数为$729$次以下的情况，该情况发生的概率至少是$1-1/81=80/81$。

此时再次使用切比雪夫不等式，得到前$6$次都是正面朝上的游戏次数为$243$次以上的概率小于等于$1/27$。

现在考虑前$4$次都是正面朝上的游戏里，前$6$次都是正面朝上的游戏次数为$243$次以下的情况，该情况发生的概率至少是$1-1/27=26/27$。

对于前$6$次都是正面朝上的情况，所得钱数之和不多于$2^15*243=7962624$的概率至少是$(1023/1024)^{243}=0.7886...$，

其余情况所得钱数之和不多于$2*6561+8*2187+32*729=53946$，

综上所述，$6561$次游戏所得钱数之和不多于$7962624+53946=8016570$的概率至少是$0.7886...*26/27*80/81*242/243=0.7469...$。

证毕。

依次类推，可以证得$9^n$次游戏所得钱数之和不多于$2^{4n-1}*3^{n+1}+2^1*3^{2n}+2^3*3^{2n-1}+2^5*3^{2n-2}+...+2^{2n-3}*3^{n+2}$的概率至少是$((4^{n+1}-1)/(4^{n+1}))^{3^{n+1}}*(3^{n-1}-1)/3^{n-1}*(3^n-1)/3^n*(3^{n+1}-1)/3^{n+1}*...*(3^{2n-3}-1)/3^{2n-3}$，

由此可得$9^n$次游戏所得钱数之和不多于$3*48^n$的概率至少是$1-(3/4)^{n+1}-1/(2*3^{n-2})$。

接下来考虑以下一系列事件及其概率：

前$9^{10}$次游戏都是第$1$次就抛到反面朝上，累计亏损$(9^{20}-9^{10})/2=6.1*10^{18}$，发生概率是$1/2^{9^{10}}$；

接下来$9^{10}$次游戏所得钱数之和不多于$3*48^{10}=1.9*10^{17}$，未能追回上期亏损，累计亏损达到$2.4*10^{19}$，发生概率至少是$(1-(3/4)^{11}-1/(2*3^8))$；

接下来$9^{11}$次游戏所得钱数之和不多于$3*48^{11}=9.3*10^{18}$，未能追回上期亏损，累计亏损达到$7.3*10^{20}$，发生概率至少是$(1-(3/4)^{12}-1/(2*3^9))$；

接下来$9^{12}$次游戏所得钱数之和不多于$3*48^{12}=4.5*10^{20}$，未能追回上期亏损，累计亏损达到$5.1*10^{22}$，发生概率至少是$(1-(3/4)^{13}-1/(2*3^{10}))$；

接下来$9^{13}$次游戏所得钱数之和不多于$3*48^{13}=2.2*10^{22}$，未能追回上期亏损，累计亏损达到$4.1*10^{24}$，发生概率至少是$(1-(3/4)^{14}-1/(2*3^{11}))$；

……

注意到当$n$每增加$1$时，$9^n$次游戏的投入会变成原来的$81$倍，而游戏所得不多于$48$倍的概率趋近于$1$，追不上投入的增长，

所以当以上一系列事件同时发生的时候，玩家就会无穷无尽地玩下去，永不盈利。

而这一系列事件同时发生的概率至少是$1/2^{9^{10}}*(1-((3/4)^{11}+(3/4)^{12}+(3/4)^{13}+...)-(1/(2*3^8)+1/(2*3^9)+1/(2*3^{10})+...))>1/2^{9^{10}+1}$，

所以玩家能盈利的概率的极限小于$(1-1/2^{9^{10}+1})$，的确是小于$1$的。

#####

既然第$1$问能证明极限小于$1$，那么第$2$问就很有意思了，期待高手的解答~

mathe

这道题目模型里面均值和方差都为无穷，如何用切定理的？

KeyTo9_Fans

举个简单的例子，连抛$81$次硬币，考察正面朝上的数量，

就可以得到均值$40.5$，方差$20.25$，标准差$4.5$。

而上面的证明把$2$次抛硬币的结果绑在了一起，

也就是连抛$81$组硬币（每组为$2$个硬币），考察全为正面朝上的组数，

就可以得到均值$81/4$，方差$243/16$，标准差${9\sqrt{3}}/4$，

这组数据与所得钱数多少是无关的。