Examine individual changes

''''Penney's game''', named after its inventor Walter Penney, is a [[Binary numeral system|binary]] (head/tail) [[sequence]] generating game between two players. At the start of the game, the two players agree on the length of the sequences to be generated. This length is usually taken to be three, but can be any larger number. Player A then selects a sequence of heads and tails of the required length, and shows this sequence to player B. Player B then selects another sequence of heads and tails of the same length. Subsequently, a fair [[coin]] is tossed until either player A's or player B's sequence appears as a consecutive subsequence of the coin toss outcomes. The player whose sequence appears first wins. Provided sequences of at least length three are used, the second player (B) has an edge over the starting player (A). This is because the game is [[Nontransitive game|nontransitive]] such that for any given sequence of length three or longer one can find another sequence that has higher [[probability]] of occurring first. ==Analysis of the three-bit game== For the three-[[bit]] sequence game, the second player can optimise his [[odds]] by choosing sequences according to: {| class="wikitable" style="text-align: center;" |- ! 1st player's choice !! 2nd player's choice !! Odds in favour of 2nd player |- |<u>H'''H'''</u>H || '''T'''<u>HH</u> || 7 to 1 |- |<u>H'''H'''</u>T || '''T'''<u>HH</u> || 3 to 1 |- |<u>H'''T'''</u>H || '''H'''<u>HT</u> || 2 to 1 |- |<u>H'''T'''</u>T || '''H'''<u>HT</u> || 2 to 1 |- |<u>T'''H'''</u>H || '''T'''<u>TH</u> || 2 to 1 |- |<u>T'''H'''</u>T || '''T'''<u>TH</u> || 2 to 1 |- |<u>T'''T'''</u>H || '''H'''<u>TT</u> || 3 to 1 |- |<u>T'''T'''</u>T || '''H'''<u>TT</u> || 7 to 1 |} An easy way to remember the sequence for using as a bar trick is for the second player to start with the opposite of the middle choice of the first player, then follow it with the first player's first two choices. :So for the first player's choice of <big>'''1-2-3'''</big> :the second player must choose <big>'''(not-2)-1-2'''</big> where (not-2) is the opposite of the second choice of the first player.<ref name=":0">[https://www.youtube.com/watch?v=IMsa-qBlPIE Predicting a coin toss] by [[Scam School]] (on [[YouTube]])</ref> An intuitive explanation for this result, is that in any case that the sequence is not immediately the first player's choice, the chances for the first player getting their sequence-beginning, the opening two choices, are usually the chance that the second player will be getting their full sequence. So the second player will most likely "finish before" the first player.<ref name=":0" /> lolololololololololol ==Strategy for more than three bits== The optimal strategy for the first player (for any length of the sequence no less than 4) was found by J.A. Csirik (See References). It is to choose HTTTT.....TTTHH (<math>k-3</math> T's) in which case the second player's maximal odds of winning is <math> (2^{k-1}+1):(2^{k-2}+1) </math>. ==Variation with playing cards== One suggested variation on Penney’s Game uses a pack of ordinary playing cards. The Humble-Nishiyama Randomness Game follows the same format using Red and Black cards, instead of Heads and Tails.<ref>[http://plus.maths.org/content/os/issue55/features/nishiyama/index Winning Odds] by Yutaka Nishiyama and Steve Humble</ref><ref>[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.177.1176 Humble-Nishiyama Randomness Game - A New Variation on Penney’s Coin Game] on CiteSeer</ref> The game is played as follows. At the start of a game each player decides on their three colour sequence for the whole game. The cards are then turned over one at a time and placed in a line, until one of the chosen triples appears. The winning player takes the upturned cards, having won that "trick". The game continues with the rest of the unused cards, with players collecting tricks as their triples come up, until all the cards in the pack have been used. The winner of the game is the player that has won the most tricks. An average game will consist of around 7 "tricks". As this card-based version is quite similar to multiple repetitions of the original coin game, the second player's advantage is greatly amplified. The probabilities are slightly different because the odds for each flip of a coin are [[Independence (probability theory)|independent]] while the odds of drawing a red or black card each time is dependent on previous draws. Note that HHT is a 2:1 favorite over HTH and HTT but the odds are different for BBR over BRB and BRR. Below are the probabilities of the outcomes for each strategy: {| class="wikitable" style="text-align: center;" |- ! 1st player's choice !! 2nd player's choice !! Probability 1st player wins !! Probability 2nd player wins !! Probability of a draw |- |<u>B'''B'''</u>B || '''R'''<u>BB</u> || 0.11% || 99.49% || 0.40% |- |<u>B'''B'''</u>R || '''R'''<u>BB</u> || 2.62% || 93.54% || 3.84% |- |<u>B'''R'''</u>B || '''B'''<u>BR</u> || 11.61% || 80.11% || 8.28% |- |<u>B'''R'''</u>R || '''B'''<u>BR</u> || 5.18% || 88.29% || 6.53% |- |<u>R'''B'''</u>B || '''R'''<u>RB</u> || 5.18% || 88.29% || 6.53% |- |<u>R'''B'''</u>R || '''R'''<u>RB</u> || 11.61% || 80.11% || 8.28% |- |<u>R'''R'''</u>B || '''B'''<u>RR</u> || 2.62% || 93.54% || 3.84% |- |<u>R'''R'''</u>R || '''B'''<u>RR</u> || 0.11% || 99.49% || 0.40% |} If the game is ended after the first trick, there is a negligible chance of a draw. The odds of the second player winning in such a game appear in the table below. {| class="wikitable" style="text-align: center;" |- ! 1st player's choice !! 2nd player's choice !! Odds in favour of 2nd player |- |<u>B'''B'''</u>B || '''R'''<u>BB</u> || 7.50 to 1 |- |<u>B'''B'''</u>R || '''R'''<u>BB</u> || 3.08 to 1 |- |<u>B'''R'''</u>B || '''B'''<u>BR</u> || 1.99 to 1 |- |<u>B'''R'''</u>R || '''B'''<u>BR</u> || 2.04 to 1 |- |<u>R'''B'''</u>B || '''R'''<u>RB</u> || 2.04 to 1 |- |<u>R'''B'''</u>R || '''R'''<u>RB</u> || 1.99 to 1 |- |<u>R'''R'''</u>B || '''B'''<u>RR</u> || 3.08 to 1 |- |<u>R'''R'''</u>R || '''B'''<u>RR</u> || 7.50 to 1 |} ==See also== *[[Nontransitive game]] ==References== {{Reflist}} * Walter Penney, Journal of Recreational Mathematics, October 1969, p.&nbsp;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), pp183–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.&nbsp;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, pp194–195. * Steve Humble & [[Yutaka Nishiyama]], [http://plus.maths.org/issue55/features/nishiyama/index.html "Winning Odds"], Plus Magazine, Issue 55, June 2010. * [[Yutaka Nishiyama]], [http://www.ijpam.eu/contents/2010-59-3/10/10.pdf 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.]], [http://blog.wolfram.com/2010/11/30/how-to-win-at-coin-flipping/ "How to Win at Coin Flipping"], [http://blog.wolfram.com/ 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. ==External links== * Play Penney's game [http://www.haverford.edu/math/cgreene/390b-00/software/CoinFlip.html against the computer] {{Use dmy dates|date=September 2010}} {{DEFAULTSORT:Penney's Game}} [[Category:Mathematical games]]'