薛定谔调和级数的最佳开箱方案

KeyTo9_Fans

KeyTo9想判断这个薛定谔的调和级数±1±1/2±1/3±1/4±……±1/10^40是否大于0

式子里的±表示一个正负叠加态的箱子，打开后有50%的概率坍缩成+，有50%的概率坍缩成-

为了打开尽可能少的箱子就能做出正确的判断，KeyTo9的开箱策略如下：

从左往右依次开箱，直到剩余的箱子无论开出什么符号，都不会对总和是否大于0的结论产生影响为止

例如：

运气最好的情况是连续开出74930600128844902361个+，就知道总和一定大于0了，剩下的箱子就不用开了

运气最差的情况是开了(10^40 - 1)个箱子，还是不能确定总和是否大于0，一定要把10^40个箱子全都打开，才能确定总和是否大于0

问题1：平均情况下KeyTo9需要打开多少个箱子？（KeyTo9需要打开的箱子数的期望值是多少？）

问题2：如果允许有1%的误判概率，那么KeyTo9应该如何开箱和下结论，才能使得正确率不低于99%且打开的箱子数量的期望值最小呢？这个最小的期望值是多少？

mathe

我们知道$1+1/2+...+1/n \approx \ln(n)+\gamma$, 于是近似的$1/{n+1}+...+1/m \approx \ln(m)-\ln(n)$。$m=10^40$
由于我们这里有一批独立分布的概率模型进行叠加（只是不是同分布的），真实计算会比较困难，我们可以假设对于充分大的n, 叠加以后的结果会比较接近正态分布，那么我们就只需要计算前n项的均方差即可，这个为$1/1^2+1/2^2+...+1/n^2 \to \frac{\pi^2}6$。（前面若干项绝对值比较大，可能会有一些偏离，所以实际上的分布应该会略有区别，但是对于充分大的n，分布应该是比较稳定的).
从这个角度来看，也就是给定一个均值为0，方差为$ \frac{\pi^2}6$的随机变量$\eta$，我们需要找到第一个使得$\ln(m)-\ln(n)<|\eta|$的n的期望值
所以$n\approx \exp(\ln(m)-|\eta|)=m\exp(-|\eta|)$。 由于$\frac{\sqrt{6}\eta}{\pi}$服从标准正太分布，于是结果就应该约等于
$\frac{m}{\sqrt{2\pi}}\int_{-\infty}^{+\infty}\exp(-|\frac{\pi x}{\sqrt{6}}|)\exp(-\frac{x^2}2)dx \approx 0.454 m=4.54\times 10^{39}$。

KeyTo9_Fans

我编程模拟了10万个箱子的情况，平均需要打开42447个，和楼上的结论一致

如果允许有1%的误判概率，平均情况好像只需打开不到180个箱子，正确率就有99%了

策略如下：

1、从左到右开箱，一旦已开箱子的和值大于未开箱子的标准差的2.5倍，就根据当前的和值下结论，正确率为99.4%
2、如果开了1万个箱子还未触发上述条件，也根据当前的和值下结论，正确率（保守估计）为50%

1万个箱子以内能触发条件1的概率约为0.992，因此总的正确率为0.992*0.994+0.008*0.5=0.99

程序模拟结果表明，上述策略平均情况下只需要打开179个箱子

当然，这个策略还有不少优化的空间，优化后估计能减少到100个箱子左右

不知道如果把正确率提高到99.99%，需要开的箱子数量会变成原来的几倍呢？

mathe

前面只给出了前n个和对近似分布，为方差为$\frac{\pi^2}6$的正态分布，
那么余下的m-n个数的和同样可以计算其方差为$E_{n,m}=\sum_{h=n+1}^n \frac 1{h^2}\approx \frac1 n -\frac1 m$ (这部分有些误差，如果能用更精确的估计可能会更好，但是后面估计不大好计算）
我们可以找一个正态分布表，我们需要的是绝对值在正态分布表中间部分要尽量大，比如我们要求99%的精度，那么对应概率分布表查表值为1-(1-0.99)/2=0.95, 对应约为标准方差的2.58倍。
所以一般情况，我们需要计算前n个之和形成的随机变量绝对值取值超过$\lambda \sqrt{E_{n,m}}$的概率，其中比如选择99%的成功率的话,$\lambda$就选择2.58.
也就是我们需要计算第一个使得$\eta > \lambda \sqrt{E_{n,m}}$ 或$\eta < -\lambda\sqrt{E_{n,m}}$的数值n的期望值, 也就是我们需要求解$(\frac{\eta}{\lambda})^2 = E_{n,m}$
近似方程为$ n=\frac1{\frac1m+(\frac{\eta}{\lambda})^2}$, 所以我们需要计算最终期望值约等于
$\frac1{\sqrt{2\pi}}\int_{-\infty}^{\infty}\frac{\exp(-\frac{x^2}2)}{\frac1m+\frac{\pi^2}6(\frac{x}{\lambda})^2}dx$
比如在$m=10^{40}, \lambda=2.58$时，上面的值约 $2.5\times10^{20}$. 而在$m=10^4 ,\ lambda=2.58$时，值约248.