论文标题
与部分反馈一起猜测卡
Card Guessing with Partial Feedback
论文作者
论文摘要
考虑以下实验：$ n $ $ n $不同卡类型的$ m $副本的甲板被随机改组，并且猜测者试图在绘制时依次猜测这些卡。每次进行猜测时，都会给出一些“反馈”。例如，人们可以告诉猜测他们刚刚猜测过的卡的真实身份（完整的反馈模型），或者根本可以告诉他们（无反馈模型）。 在本文中，我们探讨了部分反馈模型，在猜测卡后，猜测者只会被告知他们的猜测是否正确。我们在这种情况下显示，在$ n $中均匀，最多可以在$ n $中（m^{3/4} \ log M）$卡在预期中正确猜测。从1981年开始，这解决了Diaconis和Graham的问题，即使$ M = 2 $ case也开放。
Consider the following experiment: a deck with $m$ copies of $n$ different card types is randomly shuffled, and a guesser attempts to guess the cards sequentially as they are drawn. Each time a guess is made, some amount of "feedback" is given. For example, one could tell the guesser the true identity of the card they just guessed (the complete feedback model) or they could be told nothing at all (the no feedback model). In this paper we explore a partial feedback model, where upon guessing a card, the guesser is only told whether or not their guess was correct. We show in this setting that, uniformly in $n$, at most $m+O(m^{3/4}\log m)$ cards can be guessed correctly in expectation. This resolves a question of Diaconis and Graham from 1981, where even the $m=2$ case was open.
