Asymptotic analysis of card guessing with feedback
Asymptotic analysis of card guessing with feedback
复制标题
带反馈的猜牌渐近分析
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Pengda Liu
中科院分区：
文献类型：
--
作者：
Pengda Liu
研究了带反馈的猜牌博弈。将一副标有1到$n$的$n$张牌以某种方式洗牌并放在桌子上。玩家尝试从顶部猜牌，并在每次猜牌后得到一定的反馈。目标是找到具有最大奖励（预期正确猜测次数）的猜测策略。本文首先提供了一个阐述了以前的工作，并介绍了一些研究这个问题的一般框架。然后，我们回顾并纠正了Ciucu在{riffle shuffle，no feedback}设置中所做工作中的一个错误。我们还推广了他的一个结果，证明了在这种情况下，最优策略的预期回报为2/sqrt{pi}cdotsqrt{n}+O（1）$。最后，我们的框架，我们部分解决了拜耳和Diaconis的一个公开问题，提供了最佳策略{riffle shuffle，完全反馈}，并证明了最大期望回报是$n/2+sqrt{2/pi}cdotsqrt{n}+O（1）$。
This paper studies the game of guessing shuffled cards with feedback. A deck of $n$ cards labelled 1 to $n$ is shuffled in some fashion and placed on a table. A player tries to guess the cards from top and is given certain feedback after each guess. The goal is to find the guessing strategy with maximum reward (expected number of correct guesses). This paper first provides an exposition of the previous work and introduces some general framework for studying this problem. We then review and correct one mistake in the work done by Ciucu in the setting of {riffle shuffle, no feedback}. We also generalize one of his results by proving that the optimal strategy in that scenario has expected reward $2/sqrt{pi}cdotsqrt{n}+O(1)$. Finally, with our framework, we partially solve an open problem of Bayer and Diaconis by providing the optimal strategy for {riffle shuffle, complete feedback} and proving that the maximum expected reward is $n/2+sqrt{2/pi}cdotsqrt{n}+O(1)$.