First-past-the-post games
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 for...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Book Section |
| Published: |
Springer
2012
|
| Online Access: | https://eprints.nottingham.ac.uk/1857/ |
| _version_ | 1848790675513933824 |
|---|---|
| author | Backhouse, Roland |
| author2 | Gibbons, Jeremy |
| author_facet | Gibbons, Jeremy Backhouse, Roland |
| author_sort | Backhouse, Roland |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T18:16:23Z |
| format | Book Section |
| id | nottingham-1857 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:16:23Z |
| publishDate | 2012 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-18572020-05-04T16:33:20Z https://eprints.nottingham.ac.uk/1857/ First-past-the-post games Backhouse, Roland 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. Springer Gibbons, Jeremy Nogueira, Pablo 2012-06-25 Book Section PeerReviewed Backhouse, Roland (2012) First-past-the-post games. In: Mathematics of program construction: 11th International Conference, MPC 2012, Madrid, Spain, June 25-27, 2012: proceedings. Lecture notes in computer science (7342). Springer, Berlin, pp. 157-176. ISBN 9783642311130 https://link.springer.com/chapter/10.1007%2F978-3-642-31113-0_9 doi:10.1007/978-3-642-31113-0_9 doi:10.1007/978-3-642-31113-0_9 |
| spellingShingle | Backhouse, Roland First-past-the-post games |
| title | First-past-the-post games |
| title_full | First-past-the-post games |
| title_fullStr | First-past-the-post games |
| title_full_unstemmed | First-past-the-post games |
| title_short | First-past-the-post games |
| title_sort | first-past-the-post games |
| url | https://eprints.nottingham.ac.uk/1857/ https://eprints.nottingham.ac.uk/1857/ https://eprints.nottingham.ac.uk/1857/ |