Abstract
Informally, a first-past-the-post game is a (probabilistic) game where the winner is the person who predicts the event that occurs first among a set of events. Examples of first-past-the-post games include so-called block and hidden patterns and the Penney-Ante game invented by Walter Penney. We formalise the abstract notion of a first-past-the-post game, and the process of extending a probability distribution on symbols of an alphabet to the plays of a game.
Analysis of first-past-the-post games depends on a collection of simultaneous (non-linear) equations in languages. Essentially, the equations are due to Guibas and Odlyzko but they did not formulate them as equations in languages but as equations in generating functions detailing lengths of words.
Penney-Ante games are two-player games characterised by a collection of regular, prefix-free languages. For such two-player games, we show how to use the equations in languages to calculate the probability of winning. The formula generalises a formula due to John H. Conway for the original Penney-Ante game. At no point in our analysis do we use generating functions. Even so, we are able to calculate probabilities and expected values. Generating functions do appear to become necessary when higher-order cumulatives (for example, the standard deviation) are also required.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Backhouse, R.C.: Program Construction and Verification. Prentice-Hall International (1986)
Backhouse, R.: Program Construction. Calculating Implementations From Specifications. John Wiley & Sons, Ltd. (2003)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press (2009)
Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics: a Foundation for Computer Science, 2nd edn. Addison-Wesley Publishing Company (1994)
Guibas, L.J., Odlyzko, A.M.: String overlaps, pattern matching and nontransitive games. Journal of Combinatorial Theory, Series A30, 183–208 (1981)
Gries, D., Schneider, F.B.: A Logical Approach to Discrete Math. Springer (1993)
Penney, W.: Problem 95: Penney-Ante. Journal of Recreational Mathematics, 321 (1974)
Solov’ev, A.D.: A combinatorial identity and its application to the problem concerning the first occurrence of a rare event. Theory of Probability and its Applications 11, 276–282 (1966)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Backhouse, R. (2012). First-Past-the-Post Games. In: Gibbons, J., Nogueira, P. (eds) Mathematics of Program Construction. MPC 2012. Lecture Notes in Computer Science, vol 7342. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31113-0_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-31113-0_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31112-3
Online ISBN: 978-3-642-31113-0
eBook Packages: Computer ScienceComputer Science (R0)