圣彼得堡游戏的悖论

mathe

是不是每轮放缩到成概率为2^-h取值大于2^h,余下部分收益都是2^h?

wayne

如果是$n$次投币，正面朝上的次数的数字特征的计算倒是可以这样的：
首先是概率：$ p_k = 1/2^k, (0<=k<=n-1), p_n=1/2^n$
其次是期望值：$ E(X) = \sum_{k=0}^{n} k*p_k = 2 -  (2 + n)/2^n$
方差：$DX = E(X^2)-(EX)^2 =2 - 2^(-2 n) (2 + n)^2 - 2^-n (-2 + n^2) $  

KeyTo9_Fans

考虑到之前给的证明里，具体数据太多而且放缩过于厉害，不容易看出问题本质，

下面再给个证明，虽不严谨，但容易理解。

考虑足够多的游戏次数，比如$2^100$次游戏，大约能得多少钱呢？

结论是大约能得$51*2^100$块钱，求解过程如下：

在$2^100$次游戏里，

有$2^99$次游戏得$1$块钱，共计$2^99$块钱；

有$2^98$次游戏得$2$块钱，共计$2^99$块钱；

有$2^97$次游戏得$4$块钱，共计$2^99$块钱；

……

有$2^1$次游戏得$2^98$块钱，共计$2^99$块钱；

有$2^0$次游戏得$2^99$块钱，共计$2^99$块钱；

还有$1$次游戏人品大爆发，得$2^100$块钱。

以上所得钱数相加，一共是$2^99*100+2^100=51*2^100$块钱。

但是……

$2^100$次游戏所花的钱数是${2^100*(2^100-1)}/2$，约等于$2^199$块钱，

远大于游戏所得的$51*2^100$块钱，

所以玩$2^100$次游戏，玩家会大概率大幅亏损。

而玩更多轮游戏也无济于事，

因为$n$轮游戏所花钱数是$\Omega(n^2)$，所得只有$O(n\log n)$，

所以一旦玩家出师不利，永不盈利是很正常的。

#####

所以这个游戏并没有什么悖论，

其收益的增长速度是可以完全量化的，

每局游戏的平均收益随着游戏次数增加而增加，

其增长速度与$\log n$相当，

确实是趋于无穷大的。

而玩家永不盈利是因为玩家投入的增长速度更快而已。

KeyTo9_Fans

于是第$2$问也就不难了:

要想盈利概率为$1$，$n$轮游戏所花钱数之和只能是$n\log n$级别，

也就是每轮游戏的投入大约是$\log n$级别的增长速度。

具体的结论如下:

当每局花费$f(n)=\Theta(n^c)$时，$c$只能小于等于$0$，否则就有可能永不盈利;

当$f(n)=\Theta(\log^c n)$时，$c$只能小于等于$1$，否则就有可能永不盈利。

#####

有趣的是，在盈利概率为$1$的前提下，$f(n)$还可以增长得比$\log n$快一些:

当$f(n)=\Theta(\log n\log^c\log n)$时，$c$最大可以取$1$;

当$f(n)=\Theta(\log n\log\log n\log^c\log\log n)$时，$c$仍然最大可以取$1$;

……

依次类推，只要下一项多一重$\log$，并且次数为$1$，是可以添加任意多项上去的。

如果我们强行规定$log x$不能小于$1$，

也就是说，当$x$小于$\log$的底数时，重新定义$\log x$运算的结果为$1$，

那么当$f(n)$取无穷多项多重$\log n$之积的极限时，

即$f(n)=\Pi_{k=1}^{\infty}\log^{(k)}n$时，

其中，$\log^{(k)}n=\log\log\log...\log n$（$k$重$\log$），

那么玩家可以盈利的概率是多少呢？

答案依然是$1$。

#####

在盈利概率为$1$的前提下，$f(n)$还可以增长得比$\Pi_{k=1}^{\infty}\log^{(k)}n$快一些吗？

答案是可以的。

为了讨论方便，我们此后将$\log$的底数设为$2$，

那么再添加一项$\log^{**}n$，

即$f(n)=\log^{**}n*\Pi_{k=1}^{\infty}\log^{(k)}n$时，玩家可以盈利的概率依然为$1$。

其中$\log^{**}n$是一个增长速度比任意多重$\log n$还慢得多的函数。

其函数值的定义是【要使得$\log^{(k)}n$等于$1$，$k$至少要取多少】，

例如：

要使得$\log^{(k)}2$等于$1$，$k$至少要取$1$，所以$\log^{**}2=1$；

要使得$\log^{(k)}4$等于$1$，$k$至少要取$2$，所以$\log^{**}4=2$；

要使得$\log^{(k)}16$等于$1$，$k$至少要取$3$，所以$\log^{**}16=3$；

要使得$\log^{(k)}65536$等于$1$，$k$至少要取$4$，所以$\log^{**}65536=4$；

要使得$\log^{(k)}2^65536$等于$1$，$k$至少要取$5$，所以$\log^{**}2^65536=5$；

要使得$\log^{(k)}2^{2^65536}$等于$1$，$k$至少要取$6$，所以$\log^{**}2^{2^65536}=6$；

要使得$\log^{(k)}2^{2^{2^65536}}$等于$1$，$k$至少要取$7$，所以$\log^{**}2^{2^{2^65536}}=7$；

……

依次类推。

当$n$小于$2$时，我们规定$\log^{**}n=1$。

如果我们给$\log^{**}n$添加指数，

即$f(n)=(\log^{**}n)^c*\Pi_{k=1}^{\infty}\log^{(k)}n$，

那么$c$最大可以取多少呢？

答案依然是$1$。

只要$c$比$1$大一丁点儿，玩家永不盈利的概率就大于$0$了。

#####

在盈利概率为$1$的前提下，$f(n)$还可以增长得比$\log^{**}n*\Pi_{k=1}^{\infty}\log^{(k)}n$快一些吗？

答案是可以的。

$f(n)$还可以添加一项因子$\log\log^{**}n$，即对$n$进行$log^{**}$运算之后再进行$\log$运算，例如：$\log\log^{**}2^{2^{2^{...}}}=4$（$16$层指数塔）。

$f(n)$还可以添加一项因子$\log^{(2)}\log^{**}n$，即对$n$进行$log^{**}$运算之后再进行$2$次$\log$运算，例如：$\log^{(2)}\log^{**}2^{2^{2^{...}}}=4$（$65536$层指数塔）。

$f(n)$还可以添加一项因子$\log^{(3)}\log^{**}n$，……

依次类推，得到$f(n)=(\Pi_{k=1}^{\infty}\log^{(k)}n)*\log^{**}n*\log\log^{**}n*\log^{(2)}\log^{**}n*\log^{(3)}\log^{**}n*...$

也就是当$f(n)=(\Pi_{k=1}^{\infty}\log^{(k)}n)*\Pi_{k=0}^{\infty}\log^{(k)}\log^{**}n$时，

玩家可以盈利的概率依然是$1$。

在盈利概率为$1$的前提下，$f(n)$还可以增长得比$(\Pi_{k=1}^{\infty}\log^{(k)}n)*\Pi_{k=0}^{\infty}\log^{(k)}\log^{**}n$快一些吗？

答案是可以的。

$f(n)$还可以添加一项因子$\log^{**}\log^{**}n$，即对$n$进行$2$次$log^{**}$运算，例如：$\log^{**}\log^{**}2^{2^{2^{...}}}=5$（$2^65536$层指数塔）。

$\log^{**}\log^{**}n$可以写成$\log^{**(2)}n$。

$f(n)$还可以添加以下因子：

$\log\log^{**(2)}n$，$\log^{(2)}\log^{**(2)}n$，$\log^{(3)}\log^{**(2)}n$，……

也就是当$f(n)=(\Pi_{k=1}^{\infty}\log^{(k)}n)*\Pi_{k=0}^{\infty}(\log^{(k)}\log^{**}n*\log^{(k)}\log^{**(2)}n)$时，

玩家可以盈利的概率依然是$1$。

同理，$f(n)$还可以添加的项有：

$\log^{**(3)}n$，$\log\log^{**(3)}n$，$\log^{(2)}\log^{**(3)}n$，$\log^{(3)}\log^{**(3)}n$，……

$\log^{**(4)}n$，$\log\log^{**(4)}n$，$\log^{(2)}\log^{**(4)}n$，$\log^{(3)}\log^{**(4)}n$，……

$\log^{**(5)}n$，$\log\log^{**(5)}n$，$\log^{(2)}\log^{**(5)}n$，$\log^{(3)}\log^{**(5)}n$，……

也就是当$f(n)=(\Pi_{j=0}^{\infty}\Pi_{k=0}^{\infty}\log^{(k)}\log^{**(j)}n)/n$时（由于$\log^{(0)}\log^{**(0)}n=n$，分母$n$是用来抵消这一项的），

玩家可以盈利的概率依然是$1$。

#####

$f(n)$还可以增长得比$(\Pi_{j=0}^{\infty}\Pi_{k=0}^{\infty}\log^{(k)}\log^{**(j)}n)/n$快一些吗？

答案是可以的。

$f(n)$还可以再添加一项$\log^{** **}n$，

即$f(n)=(\log^{** **}n*\Pi_{j=0}^{\infty}\Pi_{k=0}^{\infty}\log^{(k)}\log^{**(j)}n)/n$时，

玩家可以盈利的概率依然为$1$。

$\log^{** **}n$是一个增长得比任意多重$\log^{**}n$还慢得多的函数，

定义是【要使得$\log^{**(j)}n$等于$1$，$j$至少要取多少】。

例如：当$n=2^{2^{2^...}}$（$2^{2^{2^...}}$层指数塔）（$65536$层指数塔）时，$\log^{** **}n=5$，

分析如下：

　　$\log^{**}n=2^{2^{2^...}}$（$65536$层指数塔），

　　$\log^{**(2)}n=65536$，

　　$\log^{**(3)}n=4$，

　　$\log^{**(4)}n=2$，

　　$\log^{**(5)}n=1$，

　　也就是$j$要取$5$才有$\log^{**(j)}n$等于$1$，

　　所以$\log^{** **}n=5$。

当$n$小于$2$时，我们规定$\log^{** **}n=1$。

如果我们给$\log^{** **}n$添加指数，

即$f(n)=((\log^{** **}n)^c*\Pi_{j=0}^{\infty}\Pi_{k=0}^{\infty}\log^{(k)}\log^{**(j)}n)/n$，

那么$c$最大可以取多少呢？

答案依然是$1$。

只要$c$比$1$大一丁点儿，玩家永不盈利的概率就大于$0$了。

同理，当$f(n)=(\Pi_{i=0}^{\infty}\Pi_{j=0}^{\infty}\Pi_{k=0}^{\infty}\log^{(k)}\log^{**(j)}\log^{** **(i)}n)/n$时，

玩家可以盈利的概率依然是$1$。

同理，当$f(n)=(\Pi_{i=0}^{\infty}\Pi_{j=0}^{\infty}\Pi_{k=0}^{\infty}\Pi_{l=0}^{\infty}\log^{(i)}\log^{**(j)}\log^{** **(k)}\log^{** ** **(l)}n)/n$时，

玩家可以盈利的概率依然是$1$。

同理，当$f(n)=(\Pi_{i=0}^{\infty}\Pi_{j=0}^{\infty}\Pi_{k=0}^{\infty}\Pi_{l=0}^{\infty}\Pi_{m=0}^{\infty}\log^{(i)}\log^{**(j)}\log^{** **(k)}\log^{** ** **(l)}\log^{** ** ** **(m)}n)/n$时，

玩家可以盈利的概率依然是$1$。

……

依次类推，当$f(n)=(\Pi_{a_0=0}^{\infty}\Pi_{a_1=0}^{\infty}\Pi_{a_2=0}^{\infty}\Pi_{a_3=0}^{\infty}...\Pi_{a_k=0}^{\infty}\log^{(a_0)}\log^{**(a_1)}\log^{** **(a_2)}\log^{** ** **(a_3)}...\log^{** ** ** ... **(a_k)}n)/n$（$k$个$**$，$k->\infty$）时，

玩家可以盈利的概率依然是$1$。

KeyTo9_Fans

下载这个附件，解压后就可以玩这个游戏了：

StPetersburg.zip (87.84 KB, 下载次数: 2)

2017-12-6 02:43 上传

点击文件名下载附件

为了简单起见，每局游戏玩家都无需付钱，累计收益是根据每局连抛正面的次数结算出来的：）

KeyTo9_Fans

mathe        你的随机数是用什么函数产生的？需要注意Windows下默认随机数函数只有16比特，周期很小，会导致结果不准确（可以查看RAND_MAX,应该是65535?)。
                建议使用硬件伪随机数RDRAND指令。
发表于        2017-12-06 08:56
--------------------------------------------------

先调用srand(time(NULL))初始化种子，然后每次调用rand()函数就可以得到$15$个$\{0,1\}$随机数。

由于rand()函数的周期太短，所以通过叠加噪声来加长周期。

每次鼠标点击的坐标就是叠加进去的噪声之一。

叠加了噪声之后，即使每次都点击同一个坐标，周期长度估计也有$10^14$，大概能够维持$100$万次鼠标点击同一个地方。

如果鼠标点击的坐标没有规律，那么周期只会更长。

我已经用按键精灵点击了$3208$次鼠标，每次都点击同一个地方，玩最大的$10^22$局，结果如下：



由于$log_2(3208\times 10^22)=84.729876513976891950993045580313$，有$2$次连续抛出$84$次正面是很合理的。

由于$log_2(3208\times 10^22)/2=42.364938256988445975496522790157$，局均收益$42.778666$也是很合理的。

wayne

http://www.cplusplus.com/referen ... m_int_distribution/
rand确实不太妥。加噪声虽然是增加了不确定性，但好像不一定增加了随机性吧。不确定性不一定等于随机性。

我现在都是用C++11的random。另外C++11的random_device好像是支持非确定性的随机数生成器的，如果支持(如mathe所提及的intel的rdrand)
下面的代码是产生10个均匀分布的64位随机整数

1. #include <iostream>
   
2. #include <random>
   
3. 
   
4. int main ()
   
5. {
   
6.   std::random_device rd;
   
7. 
   
8.   std::cout << "default random_device characteristics:" << std::endl;
   
9.   std::cout << "minimum: " << rd.min() << " maximum: " << rd.max() << std::endl;
   
10.   std::cout << "entropy: " << rd.entropy() << " a random number: " << rd() << std::endl;
    
11. 
    
12.   std::mt19937_64 gen(rd());
    
13.   std::uniform_int_distribution<uint64_t> rnd;
    
14. 
    
15.   for(int i=0;i<10;++i)  {
    
16.       std::cout << rnd(gen) <<std::endl;
    
17.   }
    
18. 
    
19.   return 0;
    
20. }
    
21. 
    

复制代码

KeyTo9_Fans

发一张只用rand()的结果，对比一下：



可以看到，周期性很明显：

$72$次正面有$6656=512\times 13$局；
$73$次正面有$3072=512\times 6$局；
$74$次正面有$\ \ \ \ \ \ 0=512\times 0$局；
$75$次正面有$\ \ 512=512\times 1$局；
$76$次正面有$\ \ 512=512\times 1$局；
$77$次正面以上都是$0$局。

而$16$楼的结果则没有这样的周期性。

mathe

https://software.intel.com/en-us/articles/the-drng-library-and-manual

.·.·.

KeyTo9_Fans 发表于 2017-6-4 09:15
举个简单的例子，连抛$81$次硬币，考察正面朝上的数量，

就可以得到均值$40.5$，方差$20.25$，标准差$4. ...

菜鸡来回答一下问题
忘勿见怪

首先把游戏改掉，原来的游戏太离散不好看，可以把新游戏改成，
a)每一局在[0,1]上的均匀分布U[0,1]上选一个x，获得$\frac1{2x}$
b)每一局在[0,1]上的均匀分布U[0,1]上选一个x，获得$\frac1x$
可以看出这两个游戏的回报，一个严格比“圣彼得堡游戏”要低，另一个严格比“圣彼得堡游戏”要高(有$\frac1 2$概率（0.5<x<=1）得不到/至少得到1,剩下的可能有$\frac1 2$概率(0.25<x<=0.5)得不到/至少得到2，剩下的可能有$\frac1 2$(0.125<x<=0.25)得不到/至少得到4，……)

于是我们可以研究这一类问题来代替“圣彼得堡游戏”
感觉仿佛回到了高等概率论课堂上……
下面是补钙的时间了……

先留个$f(n)g(n)$备用：
n次游戏没有一次得多于$\frac{n(n+1)}{f(n)}$的概率为
${1-\frac k{n(n+1)}}^n$，根据{(1+1/n)^n}的极限为e知这玩意会收敛到$e^{-\frac{f(n)}{n+1}}$
这样只要f(n)/(n+1)->0那么这个概率会收敛到1

而n次游戏有至少k次得少于g(n)的概率为
$(1/g(n))^k*C_n^k$

然后我们只需要找到$f(n)g(n)$使得上面那两个极限都趋向1，且$kg(n)+\frac{n(n-k)(n+1)}{f(n)}<\frac{n(n+1)}2$

感觉第二问应该也是这个思路
我先撤了……还需要读论文


最后，\frac12竟然不是$\frac1 2$简直差评啊……