A simple problem is studied in which there are N boxes and a prize known to be in one of the boxes. Furthermore, the probability that the prize is in any box is given. It is desired to find the prize with minimal expected work, where it takes one unit of work to open a box and look inside. The paper establishes bounds on the minimal work in terms of the $p=1/2$ H\"older norm of the probability density and in terms of the entropy of the probability density. We also introduce the notion of "Cartesian product" of problems, and determine the asymptotic behavior of the minimal work for the $n$th power of a problem. (This article is a newly typeset version of an internal publication written in 1984. The second author passed away on November 12, 2020, and his estate has approved the submission of this paper.)


翻译:研究一个简单的问题, 即是否有N箱和一个已知的奖品在其中一个盒中。 此外, 奖品在任何一个盒子中的概率是给的。 希望找到奖品时能做最起码的预期工作, 需要用一个单位的工作才能打开一个盒子, 并查看里面。 论文根据概率密度的$p=1/2$ H\"老规范以及概率密度的英特罗比, 确定了最小的作品的界限。 我们还引入了问题“ 笛克产物” 的概念, 并确定了问题力为$nth的微小作品的不稳行为 。 ( 文章是1984年撰写的内部出版物的新型版本。 第二作者于2020年11月12日去世, 他的财产批准提交这份文件。 )

0
下载
关闭预览

相关内容

专知会员服务
51+阅读 · 2020年12月14日
强化学习最新教程,17页pdf
专知会员服务
182+阅读 · 2019年10月11日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年7月7日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关主题
相关VIP内容
专知会员服务
51+阅读 · 2020年12月14日
强化学习最新教程,17页pdf
专知会员服务
182+阅读 · 2019年10月11日
相关资讯
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
相关论文
Arxiv
0+阅读 · 2021年7月7日
Arxiv
3+阅读 · 2018年2月24日
Top
微信扫码咨询专知VIP会员