目前答案未知的挑战性难题

majer

下面的问题可能来自数学家Zachary Chase和Yuval Peres（微软研究院的首席研究员）， 或许是半开放的问题——过去几周因为希伯来大学的Gil Kalai用它作为挑战性问题，开始在圈里流传，目前还没有哪位能给出答案。

Bob 事先选择了一个长度为 N 的 0 和 1 序列（比如说，某个视频文件，把它以二进制流的形式展开）。

随后Bob把这些字节一个一个地呈现给 Alice。

Alice的任务是，在某个时间点叫停，然后自己选择一个数字 K（小于剩下的字节长度）并预测接下来的K个字节里1的占比。

如果 Alice 的预测与之后实际的误差在 1%以内，则她获胜。

问题：假设 N 足够大，Alice 是否有胜率99% 的策略？

按我个人的直觉，应该是没有这种策略，但既然这个问题被提了出来，如果答案是没有，那也太过平凡……或许需要某些概率/统计上的艰深技术。

##########本贴于2023-06-08 08:35被KeyTo9_Fans编辑，作了如下补充##########

如果只要求误差小于等于0.25、胜率大于等于2/3，则Alice的策略如下：

Alice只需从A1、A2、A3这3个策略里等概率地随机抽取1个策略，然后遵照执行即可：

A1：直接叫停，然后预测接下来的2个数字里，1的占比是0.25
A2：直接叫停，然后预测接下来的2个数字里，1的占比是0.75
A3：让Bob展示第1个数字，然后叫停，然后预测接下来的1个数字里，Bob展示的那个数字的占比是1

这样，无论Bob如何选取01数列，Alice的胜率都是2/3，具体的讨论如下：

如果Bob选取的前2个数字是00，则Alice抽到A1和A3时获胜
如果Bob选取的前2个数字是01，则Alice抽到A1和A2时获胜
如果Bob选取的前2个数字是10，则Alice抽到A1和A2时获胜
如果Bob选取的前2个数字是11，则Alice抽到A2和A3时获胜

于是，无论Bob怎么选取01数列，Alice的3个策略里都至少有2个策略获胜

这样我们只需取N=2，就做到了0.25的误差、2/3的胜率

仿照这种做法，把N取得很大，把候选的策略列得很多，即可达成更小的误差和更大的胜率。

例如，取$N=\exp(1/0.01+1/(1-0.99))\approx 7*10^86$，

然后再列出$(2^N-1)$个策略，使得Bob前N个数字无论怎么取，Alice都至少有$0.99*(2^N-1)$个策略的预测误差在0.01以内，

这样，Alice只要等概率地随机抽取1个策略去执行，就可以做到0.01的误差、0.99的胜率。

因此，本贴讨论的重点，应该是如何通俗易懂地描述这些策略，然后数学证明下面这个命题：

无论Bob前N个数字怎么取，Alice的$(2^N-1)$个策略里都至少有$0.99*(2^N-1)$个策略的预测误差在0.01以内

nyy

数学难题太多了，有本书叫做数论中未解决的问题，你从头到尾翻一翻，就可以发现自己很多都搞不定！

aimisiyou

能预测未来？

zeroieme

https://baike.baidu.com/item/%E4 ... 7%E6%95%B0/22784714

nyy

躺平吃低保其实没啥不好的！

KeyTo9_Fans

这1%和99%这两个参数有什么讲究么？

如果这都能做到，那提高要求，改成0.01%和99.99%，那应该也能做到吧？

如果做不到，那降低要求，改成25%和66.66%，是可以做到的。

这就变成了“做得到和做不到的分界线在哪里”的问题了。

#####

想了很久，也就只能做到25%的误差和66.66%的胜率了

想要提高胜率、减小误差的话，有点难度呃……留给比我更聪明的大神们去想吧……

majer

@KeyTo9_Fans ，我留言询问了Zachary Chase。他说答案在这篇论文里，关于{0，1}数列的重建：https://arxiv.org/pdf/2107.06454.pdf。

我注意到里面的引理1，似乎可以和上面题目的形式非常接近。不过lemma 1里，需要均匀分布的0/1样本，但Kalai的题目里对实际样本是没有限制的。我记得均匀分布的样本是可以通过变换得到任意分布的随机数。或许这处细节无关紧要，又或者这毕竟才是引理1，借助更后面的结论和数学技巧也能搞定。

KeyTo9_Fans

我把0.25误差、2/3胜率的策略分享一下吧，你看看能不能基于此，减少误差、提高胜率：

Alice只需从A1、A2、A3这3个策略里等概率地随机抽取1个策略，然后遵照执行即可：

A1：直接叫停，然后预测接下来的2个数字里，1的占比是0.25
A2：直接叫停，然后预测接下来的2个数字里，1的占比是0.75
A3：让Bob展示第1个数字，然后叫停，然后预测接下来的1个数字里，Bob展示的那个数字的占比是1

这样，无论Bob如何选取01数列，Alice的胜率都是2/3，具体的讨论如下：

如果Bob选取的前2个数字是00，则Alice抽到A1和A3时获胜，胜率是2/3
如果Bob选取的前2个数字是01，则Alice抽到A1和A2时获胜，胜率是2/3
如果Bob选取的前2个数字是10，则Alice抽到A1和A2时获胜，胜率是2/3
如果Bob选取的前2个数字是11，则Alice抽到A2和A3时获胜，胜率是2/3

于是，无论Bob怎么选取01数列，Alice的胜率都是2/3

这样我们就做到了0.25的误差、2/3的胜率

你看看能不能仿照这种做法，达成更小的误差和更大的胜率吧~

白新岭

这种问题我感觉规则并不明确，结果当然没答案。

majer

majer 发表于 2023-6-5 21:36
@KeyTo9_Fans ，我留言询问了Zachary Chase。他说答案在这篇论文里，关于{0，1}数列的重建：https://arxiv. ...

它这个领域里的核心技术是借助前段可以构造出若干迹，借助这些迹可以以一定概率的准确性重建部分被删除的后段。然后这个文章是证明迹的存在性。至于具体用迹如何重建或许是他们领域里前导的知识，貌似它都没涉及。