论文标题
通过部分反馈的正确猜测数量
The number of correct guesses with partial feedback
论文作者
论文摘要
我们考虑以下游戏。带有$ n $不同卡中每本$ m $副本的甲板以一种完美的随机方式改装。猜测者依次将卡从上到下猜测。每次猜测之后，猜测者被告知猜测是否正确。目标是最大化预期的正确猜测数量。 我们证明，如果$ n =ω（\ sqrt {m}）$，则最多可以正确猜出$ m+o（\ sqrt {m}）$卡。当$ n =ω（m）$时，我们的结果与DiaConis，Graham和Spiro最大预期收益的下限相匹配。
We consider the following game. A deck with $m$ copies of each of $n$ distinct cards is shuffled in a perfectly random way. The Guesser sequentially guesses the card from top to bottom. After each guess, the Guesser is informed whether the guess is correct. The goal is to maximize the expected number of correct guesses. We prove that, if $n= Ω(\sqrt{m})$, then at most $m+O(\sqrt{m})$ cards can be guessed correctly. Our result matches a lower bound of the maximal expected payoff by Diaconis, Graham and Spiro when $n=Ω(m)$.
