彭尼的游戏
彭尼的游戏（Penney's game）由沃尔特·彭尼（Walter Penney）提出，是一个两个玩家之间生成用“正面”和“反面”为代称产生二进制数列的游戏。玩家A报出至少包含3个项、每项只能是正面或反面的序列，然后展示给玩家B；玩家B则给出等长的正面反面序列。随后, 投掷一面均匀的硬币硬币，观察正反，直至投掷出一段序列刚好和某个玩家的序列吻合，则该名玩家获胜。
将序列中每个正面或者反面的判断称为比特（bit），使用长度为3比特的序列，玩家B相对玩家A有优势。这是因为这个游戏是一个非传递博弈，所以无论如何选定第一个序列，总会有一个序列有更大的获胜概率。
长度为3bit的游戏分析
长度为3比特的游戏中,第二名玩家可以通过以下途径最大化其胜算（odds）：
（H表示正面朝上，T表示反面朝上）
| 1号玩家 | 2号玩家 | 2号玩家胜算 |
|---|---|---|
| HHH | THH | 7：1 |
| HHT | THH | 3：1 |
| HTH | HHT | 2：1 |
| HTT | HHT | 2：1 |
| THH | TTH | 2：1 |
| THT | TTH | 2：1 |
| TTH | HTT | 3：1 |
| TTT | HTT | 7：1 |
简单的来说，对于2号玩家可以记下如下的序列作为获胜的技巧或者是讨喜的技巧（bar trick）：第一个比特与1号玩家的第二个比特相反，第二个比特与1号玩家的第一个比特相同，第三个比特与1号玩家的第二个比特相同。
- 如果1号玩家选择了“1-2-3”为顺序编号的序列，每个编号代表一个比特(正面/反面)，
- 那么2号玩家则应该选择：(与2相反)-1-2 [1]
这一结果有一个直观的解释：依照这种方法，当1号玩家猜测的前两比特刚好对上时，2号玩家的后两比特也对上，而1号玩家仍需要再猜测一轮才知晓是否胜利，直觉上而言，认为2号玩家更可能先猜全序列而成为赢家。[1]
3bit以上情形分析
在比特不小于4时1号玩家的优化策略由J.A. Csirik提出的(见参考资料)。这一策略即是选择HTTTT.....TTTHH( T's)这样的序列。在此情形下，2号玩家的最大胜率为 。
带扑克牌的变种
其中一种变种使用一套普通的扑克牌，被称为Humble-Nishiyama随机性游戏。该游戏遵从与彭尼的游戏同样的格式，只不过把猜正反改成猜红牌黑牌。[2][3]
游戏规则如下：
- 游戏开始时，各玩家决定在游戏中使用的对于连续三张卡片的颜色猜测顺序。每次抽出一张卡片，并按顺序放成一线，直至被选的三联顺序出现。选中这一顺序的玩家拿走最后对上的三张牌, 称为拿到1个“trick”。游戏用余下牌继续，直至玩家不断地拿到“trick”所有牌被拿完为止。拿了最多“trick”的玩家即为赢家。
这一游戏通常会包含7个“trick”。基于扑克牌的游戏非常接近于原先游戏的重复，2号玩家的优势被极大地放大。但是概率有略微不同，因为投硬币得到的两个结果是独立的，而取出红牌于黑牌的概率取决于之前的抽牌。记红为R，黑为B，正面为H，反面为T，可以注意到HHT对比HTH和HTT的概率比是2：1，但BBR对比BRB和BRR的概率比各不相同。
以下为电脑模拟对每种策略的结果的估算概率：[4]
| 1号玩家 | 2号玩家 | 1号玩家胜算 | 2号玩家胜算 | 平局概率 |
|---|---|---|---|---|
| BBB | RBB | 0.11% | 99.49% | 0.40% |
| BBR | RBB | 2.62% | 93.54% | 3.84% |
| BRB | BBR | 11.61% | 80.11% | 8.28% |
| BRR | BBR | 5.18% | 88.29% | 6.53% |
| RBB | RRB | 5.18% | 88.29% | 6.53% |
| RBR | RRB | 11.61% | 80.11% | 8.28% |
| RRB | BRR | 2.62% | 93.54% | 3.84% |
| RRR | BRR | 0.11% | 99.49% | 0.40% |
如果游戏在多于1个trick时结束，平局概率微乎其微。2号玩家的胜率如下表所示：
| 1号玩家 | 2号玩家 | 2号玩家胜算 |
|---|---|---|
| BBB | RBB | 7.50：1 |
| BBR | RBB | 3.08：1 |
| BRB | BBR | 1.99：1 |
| BRR | BBR | 2.04：1 |
| RBB | RRB | 2.04：1 |
| RBR | RRB | 1.99：1 |
| RRB | BRR | 3.08：1 |
| RRR | BRR | 7.50：1 |
带轮盘的变体
Robert W. Vallin以及后来他和Aaron M. Montgomery一起发表了有关赌便士问题的研究结果。他们把这一游戏改编为（美式）轮盘，玩家们通过选择红色或黑色，而不是硬币的正面反面，来进行游戏。这种情况下，球落在红色与黑色区域的概率各为9/19，而球落在绿色区域的概率为1/19。绿色区域有很多解读方式：
- (1)作为状况外卡牌，既可以当黑也可以当红；
- (2)意即本轮无效须重来，或者游戏直接结束；
- (3)作为一种非红非黑的颜色参与到序列中。
其研究结果计算了胜算与结束游戏所需要的回合数。[5]
参见
- 非传递博弈
参考资料
- ^ 1.0 1.1 Predicting a coin toss （页面存档备份，存于互联网档案馆） by 'Scam School' (on YouTube)
- ^ Winning Odds （页面存档备份，存于互联网档案馆） by Yutaka Nishiyama and Steve Humble
- ^ Humble-Nishiyama Randomness Game - A New Variation on Penney’s Coin Game （页面存档备份，存于互联网档案馆） on CiteSeer
- ^ Results are broadly in line with those in Steve Humble and Yutaka Nishiyama, Humble-Nishiyama Randomness Game Mathematics Today August 2010 p 143 - A new variation on Penney’s Coin Game [1] （页面存档备份，存于互联网档案馆）
- ^ Jennifer Beineke; Jason Rosenhouse; Robert W. Vallin. The Mathematics of Various Entertaining Subjects: Research in Games, Graphs, Counting, and Complexity, Volume 2. Princeton: Princeton University Press. 2017-09-05. ISBN 9780691171920.
- Walter Penney, Journal of Recreational Mathematics, October 1969, p. 241.
- Martin Gardner, "Time Travel and Other Mathematical Bewilderments", W. H. Freeman, 1988.
- L.J. Guibas and A.M. Odlyzko, "String Overlaps, Pattern Matching, and Nontransitive Games", Journal of Combinatorial Theory, Series A. Volume 30, Issue 2, (1981), pp 183–208.
- Elwyn R. Berlekamp, John H. Conway and Richard K. Guy, "Winning Ways for your Mathematical Plays", 2nd Edition, Volume 4, AK Peters (2004), p. 885.
- S. Humble & Y. Nishiyama, "Humble-Nishiyama Randomness Game - A New Variation on Penney's Coin Game", IMA Mathematics Today. Vol 46, No. 4, August 2010, pp 194–195.
- Steve Humble & Yutaka Nishiyama, "Winning Odds" （页面存档备份，存于互联网档案馆）, Plus Magazine, Issue 55, June 2010.
- Yutaka Nishiyama, Pattern Matching Probabilities and Paradoxes as a New Variation on Penney’s Coin Game （页面存档备份，存于互联网档案馆）, International Journal of Pure and Applied Mathematics, Vol.59, No.3, 2010, 357-366.
- Ed Pegg, Jr., "How to Win at Coin Flipping" （页面存档备份，存于互联网档案馆）, Wolfram Blog （页面存档备份，存于互联网档案馆）, 30 November 2010.
- J.A. Csirik, "Optimal strategy for the first player in the Penney ante game", Combinatorics, Probability and Computing, Volume 1, Issue 4 (1992), pp 311–321.
- Robert W. Vallin “A sequence game on a roulette wheel,” The Mathematics of Very Entertaining Subjects: Research in Recreational Math, Volume II, Princeton University Press, (to be published in 2017)
- James Brofos, "A Markov Chain Analysis of a Pattern Matching Coin Game." arXiv:1406.2212 （页面存档备份，存于互联网档案馆） (2014).