pith. sign in

arxiv: 2404.06585 · v3 · submitted 2024-04-09 · 🧮 math.CO

Penney's game for permutations

Sergi Elizalde , Yixin Lin This is my paper

Pith reviewed 2026-05-24 01:51 UTC · model grok-4.3

classification 🧮 math.CO
keywords Penney's gamepermutationsconsecutive patternsnon-transitive gameswinning probabilitiesbijectionsrandom permutations
0
0 comments X

The pith

Penney's game on permutations of length 3 is non-transitive, with explicit winning probabilities for every pair.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines a permutation analogue of Penney's game in which two players each pick a length-k permutation, after which independent random numbers are drawn until the relative order of the most recent k values matches one of the chosen patterns. It computes the exact probability that one pattern appears before the other for every pair of length-3 permutations and for selected length-4 pairs. These probabilities are generally not one-half and produce cyclic dominance relations, so that the game is non-transitive. New bijections on consecutive patterns are introduced to establish the counts, and general formulas are supplied together with a conjecture that the second player can always force a win probability strictly above one-half.

Core claim

For any two distinct permutations sigma and tau of length k, the probability that a random sequence realizes sigma before tau equals the number of sequences in which sigma occurs first, counted via bijections that map blocks containing one pattern to blocks containing the other while preserving the waiting-time structure; when these probabilities are evaluated for k=3 they yield a non-transitive tournament on the six permutations.

What carries the argument

Bijections between consecutive-pattern occurrences that equate the number of sequences in which one chosen permutation appears before the other.

If this is right

  • For every pair of length-3 permutations the probability that the first appears before the second is a rational number not equal to 1/2 except in symmetric cases.
  • The resulting dominance graph on the six length-3 permutations contains cycles.
  • The same non-transitivity appears for at least some pairs of length-4 permutations.
  • Recursive formulas exist that compute the winning probability for arbitrary pairs when k grows.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The bijections may transfer to counting problems for other consecutive-pattern statistics such as the number of alternating permutations or vincular patterns.
  • The non-transitivity suggests that similar waiting-time games could be defined on other pattern-avoidance posets.
  • The second-player strategy conjecture could be tested by computing the full set of length-4 probabilities and checking whether a response permutation always exists that beats any given choice.

Load-bearing premise

The input sequence consists of independent random values from a continuous distribution, so every block of k consecutive values realizes each of the k! relative orders with equal probability.

What would settle it

Direct enumeration or simulation of the waiting times for any specific pair of length-3 permutations whose reported winning probability differs from the value obtained by exhaustive counting of all possible relative-order sequences.

Figures

Figures reproduced from arXiv: 2404.06585 by Sergi Elizalde, Yixin Lin.

Figure 1
Figure 1. Figure 1: The bijection in the proof of Theorem 3.9. that is, we move entry π ′ n to the left by inserting it into the preceding increasing run. Note that, since π ′ n−k > π′ n−k+1, this move does not create any occurrence of ιk or σ in the permutation. It is clear that these two operations are inverses of each other. In analogy to the case of words, for any σ, τ ∈ Sk, we define the set Bσ,τ = {i ∈ [k − 1] : st(σk−i… view at source ↗
Figure 2
Figure 2. Figure 2: All tied pairs of patterns in S3. Dashed edges indicate pairs of the form σ ≡ σ. 4.2 132 vs. 231 Theorem 4.1. Pr(132 ≺ 231) = e 2 − 2e − 1 2 ≈ 0.476. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: All tied pairs of patterns in S4. Dashed edges indicate pairs of the form σ ≡ σ. The colors of the solid edges refer to the theorem proving that they are tied patterns: red for Theorem 3.9, brown for Theorem 3.10 with j = 1 (including Corollary 3.11), violet for Theorem 3.10 with j = 2, green for Theorem 3.13, and gray for Theorem 5.3. and τ in positions in S are called marked occurrences. Suppose that the… view at source ↗
Figure 4
Figure 4. Figure 4: shows the graph of beater relations among patterns of length 3, which has a directed edge from τ to σ if τ beats σ. This edge is a solid edge if τ is the best beater for σ, meaning that it minimizes Pr(σ ≺ τ ) over all τ of the same length as σ. 123 312 231 321 132 213 [PITH_FULL_IMAGE:figures/full_fig_p026_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The best-beater relations among patterns in S4. Acknowledgements The authors thank Peter Winkler for helpful suggestions. The first author was partially supported by Simons Collaboration Grant #929653. References [1] Eric Babson and Einar Steingrímsson. Generalized permutation patterns and a clas￾sification of the Mahonian statistics. Sém. Lothar. Combin., 44:Art. B44b, 18, 2000. [2] Anders Claesson. Gener… view at source ↗
read the original abstract

We consider the permutation analogue of Penney's game for words. Two players, in order, each choose a permutation of length $k\ge3$; then a sequence of independent random values from a continuous distribution is generated, until the relative order of the last $k$ numbers coincides with one of the chosen permutations, making that player the winner. We compute the winning probabilities for all pairs of permutations of length 3 and some pairs of length 4, showing that, as in the original version for words, the game is non-transitive. Our proofs introduce new bijections for consecutive patterns in permutations. We also give some formulas to compute the winning probabilities more generally, and conjecture a winning strategy for the second player when $k$ is arbitrary.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper defines a permutation analogue of Penney's game: two players each select a permutation of length k ≥ 3; a sequence of i.i.d. continuous random variables is generated until the relative ordering of some consecutive k-tuple matches one of the chosen permutations, at which point that player wins. The authors compute exact winning probabilities for every pair of length-3 permutations and selected length-4 pairs, establish non-transitivity via explicit bijections on consecutive patterns, supply general formulas for the probabilities, and conjecture a strategy guaranteeing a win for the second player when k is arbitrary.

Significance. If the bijections and resulting probabilities are correct, the work furnishes the first systematic treatment of Penney's game in the permutation setting, demonstrating that non-transitivity persists and supplying concrete numerical values together with a general conjecture. The new bijections for overlapping consecutive patterns constitute a technical contribution that may be reusable in other problems involving consecutive pattern statistics or Markov-chain analyses of permutation prefixes.

major comments (2)
  1. [§3] §3 (length-3 probability calculations): the central claim that the reported winning probabilities are exact rests on the correctness of the newly introduced consecutive-pattern bijections. The manuscript provides no independent verification—such as an exhaustive enumeration of all 3! = 6 patterns for small n or a machine-checked summation of all cylinder probabilities equaling 1—leaving open the possibility that an overlap case or measure mis-count has been missed.
  2. [Table in §3] Table of length-3 probabilities (presumably in §3): without an accompanying check that each pair of probabilities sums to 1 and that the non-transitivity cycles are consistent with these values, the non-transitivity conclusion cannot be confirmed from the numerical output alone.
minor comments (2)
  1. [§2] Notation for the state space of the Markov chain on prefixes is introduced without an explicit diagram or table listing all reachable prefixes for k=3; adding one would improve readability.
  2. [Conclusion] The conjecture for the second-player strategy is stated only in the abstract and conclusion; a precise formulation (e.g., which permutation the second player should choose against a given first-player choice) should appear in the main text.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for additional verification of the length-3 calculations. We address both major comments below and will incorporate the suggested checks into a revised manuscript.

read point-by-point responses

  1. Referee: [§3] §3 (length-3 probability calculations): the central claim that the reported winning probabilities are exact rests on the correctness of the newly introduced consecutive-pattern bijections. The manuscript provides no independent verification—such as an exhaustive enumeration of all 3! = 6 patterns for small n or a machine-checked summation of all cylinder probabilities equaling 1—leaving open the possibility that an overlap case or measure mis-count has been missed.

    Authors: The bijections are constructed explicitly in §3 with case-by-case analysis of all possible overlaps, and the probabilities are obtained by solving the resulting linear systems. Nevertheless, we agree that an independent numerical check would increase confidence. In the revision we will add a short subsection that (i) enumerates all 6 patterns for sequences of length up to 20 and compares the empirical frequencies against the closed-form probabilities, and (ii) confirms by direct summation that the cylinder probabilities over all 6 patterns sum to 1 for each pair. revision: yes

  2. Referee: [Table in §3] Table of length-3 probabilities (presumably in §3): without an accompanying check that each pair of probabilities sums to 1 and that the non-transitivity cycles are consistent with these values, the non-transitivity conclusion cannot be confirmed from the numerical output alone.

    Authors: We will augment the table (or add a companion table) that explicitly lists, for every ordered pair (σ,τ), the two probabilities and verifies that they sum to 1. The same table will also mark the three non-transitive cycles (123 ≻ 132 ≻ 213 ≻ 123, etc.) and confirm that the numerical values are consistent with the cycle inequalities. These additions will appear in the revised §3. revision: yes

Circularity Check

0 steps flagged

No circularity: probabilities derived via new bijections from uniform permutation measure

full rationale

The derivation begins from the standard assumption of i.i.d. continuous random variables inducing uniform random relative orders (permutations) and proceeds by constructing explicit bijections between sets of consecutive patterns. These bijections map the overlapping pattern problem to a solvable counting or Markov-chain system whose transition probabilities are determined directly by the uniform measure, without any parameter fitting, self-definition of the target probabilities, or load-bearing self-citations. The reported length-3 winning probabilities are therefore obtained by direct enumeration under the bijections rather than by construction from the same quantities they purport to predict. No step reduces an output to an input by renaming or tautological redefinition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard model of uniform random permutations induced by continuous i.i.d. samples and on the existence of the stated bijections; no free parameters or invented entities are introduced.

axioms (1)
  • standard math Independent continuous random variables induce a uniform random permutation on any finite initial segment.
    Invoked to equate the relative order of the last k numbers with a uniform random permutation.

pith-pipeline@v0.9.0 · 5644 in / 1283 out tokens · 37518 ms · 2026-05-24T01:51:09.535486+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Generalized permutation patterns and a clas- sification of the Mahonian statistics

    Eric Babson and Einar Steingrímsson. Generalized permutation patterns and a clas- sification of the Mahonian statistics. Sém. Lothar. Combin., 44:Art. B44b, 18, 2000

    work page 2000

  2. [2]

    Generalized pattern avoidance

    Anders Claesson. Generalized pattern avoidance. European J. Combin., 22(7):961–971, 2001

    work page 2001

  3. [3]

    Coin sequence probabilities and paradoxes

    Stanley Collings. Coin sequence probabilities and paradoxes. Bulletin, 18(11-12):227– 232, 1982

    work page 1982

  4. [4]

    F. N. David and D. E. Barton. Combinatorial chance. Hafner Publishing Co., New York, 1962

    work page 1962

  5. [5]

    Wilf equivalence relations for consecutive patterns

    Tim Dwyer and Sergi Elizalde. Wilf equivalence relations for consecutive patterns. Advances in Applied Mathematics, 99:134–157, 2018. 27

    work page 2018

  6. [6]

    A survey of consecutive patterns in permutations

    Sergi Elizalde. A survey of consecutive patterns in permutations. In Recent trends in combinatorics, volume 159 of IMA Vol. Math. Appl., pages 601–618. Springer, [Cham], 2016

    work page 2016

  7. [7]

    Consecutive patterns in permutations

    Sergi Elizalde and Marc Noy. Consecutive patterns in permutations. Adv. in Appl. Math., 30:110–123, 2003

    work page 2003

  8. [8]

    Clusters, generating functions and asymptotics for consecutive patterns in permutations

    Sergi Elizalde and Marc Noy. Clusters, generating functions and asymptotics for consecutive patterns in permutations. Adv. in Appl. Math, 49:351–374, 2012

    work page 2012

  9. [9]

    Optimal penney ante strategy via correlation polynomial identities

    Daniel Felix. Optimal penney ante strategy via correlation polynomial identities. The Electronic Journal of Combinatorics, 13(R35), 2016

    work page 2016

  10. [10]

    On the paradoxical situations that arise from nontransitive situation

    Martin Gardner. On the paradoxical situations that arise from nontransitive situation. Scientific American, pages 120–125, October 1974

    work page 1974

  11. [11]

    String overlaps, pattern match- ing, and nontransitive games

    Leonidas John Guibas and Andrew Michael Odlyzko. String overlaps, pattern match- ing, and nontransitive games. Journal of Combinatorial Theory, A(30):183–208, 1981

    work page 1981

  12. [12]

    On multi-avoidance of generalized patterns

    Sergey Kitaev and Toufik Mansour. On multi-avoidance of generalized patterns. Ars Comb., 76, 2005

    work page 2005

  13. [13]

    On the expected duration of a search for a fixed pattern in random data

    Peter Tolstrup Nielsen. On the expected duration of a search for a fixed pattern in random data. IEEE Transactions on Information Theory, 19(5):702–704, 1973

    work page 1973

  14. [14]

    The On-Line Encyclopedia of Integer Sequences

    OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. Published electronically at http://oeis.org

    work page

  15. [15]

    Problem 95: Penney-ante

    Walter Penney. Problem 95: Penney-ante. Journal of Recreational Mathematics, 2(4):241, October 1969

    work page 1969

  16. [16]

    Rodica Simion and Frank W. Schmidt. Restricted permutations. European J. Combin., 6(4):383–406, 1985

    work page 1985

  17. [17]

    Stanley.Enumerative Combinatorics, volume 1

    Richard P . Stanley.Enumerative Combinatorics, volume 1. Cambridge University Press, second edition edition, 2000. 28

    work page 2000