找回密码
 欢迎注册
查看: 7110|回复: 12

[分享] 目前答案未知的挑战性难题

[复制链接]
发表于 2023-5-30 00:00:45 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
下面的问题可能来自数学家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以内
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-5-30 10:03:23 | 显示全部楼层
数学难题太多了,有本书叫做数论中未解决的问题,你从头到尾翻一翻,就可以发现自己很多都搞不定!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-5-30 10:19:03 | 显示全部楼层
能预测未来?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-6-3 13:20:26 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-6-3 21:00:01 | 显示全部楼层
躺平吃低保其实没啥不好的!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-6-4 09:39:41 | 显示全部楼层
这1%和99%这两个参数有什么讲究么?

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

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

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

#####

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

想要提高胜率、减小误差的话,有点难度呃……留给比我更聪明的大神们去想吧……
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-6-5 21:36:44 | 显示全部楼层
@KeyTo9_Fans ,我留言询问了Zachary Chase。他说答案在这篇论文里,关于{0,1}数列的重建:https://arxiv.org/pdf/2107.06454.pdf

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

点评

这个答案太晦涩难懂了,你可以仿照楼下这种大白话,把Alice的策略描述一下吗?  发表于 2023-6-6 09:05
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-6-6 08:59:26 | 显示全部楼层
我把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的胜率

你看看能不能仿照这种做法,达成更小的误差和更大的胜率吧~
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-6-7 23:54:23 | 显示全部楼层
这种问题我感觉规则并不明确,结果当然没答案。

点评

楼上8#不是给出了一种明确的规则了吗?仿照这种做法,达成更小的误差和更大的胜率。  发表于 2023-6-8 08:29
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-6-8 22:08:32 | 显示全部楼层
majer 发表于 2023-6-5 21:36
@KeyTo9_Fans ,我留言询问了Zachary Chase。他说答案在这篇论文里,关于{0,1}数列的重建:https://arxiv. ...

它这个领域里的核心技术是借助前段可以构造出若干迹,借助这些迹可以以一定概率的准确性重建部分被删除的后段。然后这个文章是证明迹的存在性。至于具体用迹如何重建或许是他们领域里前导的知识,貌似它都没涉及。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-12-27 11:52 , Processed in 0.033999 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表