pith. sign in

arxiv: 2605.19904 · v1 · pith:RN632NIZnew · submitted 2026-05-19 · 🧮 math.CO · math.PR

Moments for generalizations of a coin flip game

Jia Huang This is my paper

Pith reviewed 2026-05-20 03:53 UTC · model grok-4.3

classification 🧮 math.CO math.PR MSC 05A1560C05
keywords coin flipsmomentsrecursive formulaEulerian numberswaiting timebinary stringsGoulden-Jackson cluster methodFaà di Bruno formula
0
0 comments X

The pith

A recursive formula computes the moments of flips needed to produce a run of heads or heads followed by a tail with a biased coin.

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

The paper establishes a recursive formula for computing all moments of the waiting time until a biased coin produces a chosen binary string. It restricts attention to strings that consist of consecutive heads or consecutive heads ended by one tail. A sympathetic reader would care because these moments describe the average wait as well as the variability and tail behavior of the number of trials until the pattern appears. The work also supplies a closed-form expression for moments in the broader setting of rolling a multi-faced die until any prescribed word occurs.

Core claim

We derive a recursive formula for the moments of the number of flips using a possibly biased coin to produce a prescribed finite binary string S when S is either a run of heads or a run of heads followed by a tails. Our recursive formula involve certain sums, which we simplify by using a one-parameter extension of the well-studied Eulerian number, which belongs to the two-parameter family of numbers introduced by Graham, Knuth, and Patashnik. We also use the Goulden--Jackson cluster method and Faà di Bruno's formula to establish a closed formula for the moments in a more general situation where a die having an arbitrary number of faces with possibly different probabilities is rolled repeated

What carries the argument

The recursive formula for the k-th moment, which closes because the target strings S have restricted self-overlap properties as runs of heads or heads followed by a tail.

If this is right

  • Any order moment of the waiting time can be obtained recursively for these special strings.
  • The formulas incorporate an arbitrary heads probability directly in the recursion.
  • Sums in the recursion simplify to expressions involving the one-parameter extension of Eulerian numbers.
  • Closed formulas for moments exist when rolling a general die until any word appears, via cluster and composition methods.

Where Pith is reading between the lines

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

  • The recursion offers a route to generating functions or large-run asymptotics for the moments without building full state spaces.
  • The method isolates how limited pattern overlaps control the tractability of higher-moment calculations in string waiting problems.
  • Numerical evaluation of the recursion for increasing run lengths would give concrete values for comparison with simulation.

Load-bearing premise

The target string S must be a run of heads or a run of heads followed by a tail so that the recursive relations close without extra terms from other overlaps.

What would settle it

For the small pattern of three heads, direct computation of the exact second moment by summing probabilities over all possible sequences should match the output of the recursive formula.

read the original abstract

We derive a recursive formula for the moments of the number of flips using a possibly biased coin to produce a prescribed finite binary string $S$ when $S$ is either a run of heads or a run of heads followed by a tails. Our recursive formula involve certain sums, which we simplify by using a one-parameter extension of the well-studied Eulerian number, which belongs to the two-parameter family of numbers introduced by Graham, Knuth, and Patashnik. We also use the Goulden--Jackson cluster method and Fa\`a di Bruno's formula to establish a closed formula for the moments in a more general situation where a die having an arbitrary number of faces with possibly different probabilities is rolled repeatedly until a prescribed finite word occurs.

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 / 3 minor

Summary. The manuscript derives a recursive formula for the moments of the waiting time (number of flips) until a prescribed finite binary string S appears in a sequence of possibly biased coin flips, specifically when S is a run of heads or a run of heads followed by a tails. The resulting sums are simplified via a one-parameter extension of the Eulerian numbers (from the Graham-Knuth-Patashnik two-parameter family). For the general case of rolling a multi-faced die with arbitrary probabilities until a prescribed finite word occurs, a closed-form expression for the moments is obtained by combining the Goulden-Jackson cluster method with Faà di Bruno's formula.

Significance. If the derivations are correct, the work provides explicit recursive and closed-form moment expressions for waiting times to restricted pattern classes in biased coin flips and a general treatment for dice rolls. The restriction on S is explicitly noted as the condition allowing the recursion to close without extra states, and the use of established tools (Goulden-Jackson, Faà di Bruno) plus the Eulerian extension is a reasonable and potentially useful contribution to combinatorics on words and enumerative probability. The absence of free parameters or fitted quantities in the central claims is a strength.

major comments (2)
  1. The recursive formula (main result for the restricted S): the closure of the recursion depends on the specific structural form of S; the manuscript should include an explicit enumeration of the automaton states and transition probabilities to confirm that no additional overlap or failure states arise for the heads-run and heads+tails cases.
  2. Definition and application of the one-parameter Eulerian extension: while the extension is introduced to simplify the moment sums, the paper must demonstrate explicitly (e.g., via an identity or small-case expansion) that the sums reduce to this extension without residual terms or hidden parameters, as this simplification is load-bearing for the claimed closed recursive expressions.
minor comments (3)
  1. Notation for coin probabilities (p for heads, q=1-p for tails) should be introduced once at the beginning and used consistently; occasional switches to generic symbols in the general die section create minor ambiguity.
  2. Add a brief reference or citation to the original Graham-Knuth-Patashnik paper when introducing the two-parameter Eulerian family, to contextualize the one-parameter extension.
  3. In the general-case section, explicitly name the inner and outer functions to which Faà di Bruno is applied when composing the Goulden-Jackson generating function; this would improve readability without altering the result.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the positive recommendation for minor revision. The comments highlight opportunities to strengthen the clarity of the automaton underlying the recursion and the explicit verification of the Eulerian-number simplification. We address each major comment below and will incorporate the suggested clarifications in the revised version.

read point-by-point responses

  1. Referee: The recursive formula (main result for the restricted S): the closure of the recursion depends on the specific structural form of S; the manuscript should include an explicit enumeration of the automaton states and transition probabilities to confirm that no additional overlap or failure states arise for the heads-run and heads+tails cases.

    Authors: We agree that an explicit description of the underlying automaton would make the closure of the recursion more transparent. In the revised manuscript we will add a short subsection (or appendix) that enumerates the states of the pattern-matching automaton for a run of heads and for heads followed by a tail. For each case we will list the transition probabilities under the biased coin model and verify that no additional overlap or failure states are required beyond those already accounted for in the recursion. This addition directly addresses the referee's concern without altering the derived formulas. revision: yes

  2. Referee: Definition and application of the one-parameter Eulerian extension: while the extension is introduced to simplify the moment sums, the paper must demonstrate explicitly (e.g., via an identity or small-case expansion) that the sums reduce to this extension without residual terms or hidden parameters, as this simplification is load-bearing for the claimed closed recursive expressions.

    Authors: We appreciate this observation. While the manuscript derives the sums and states that they equal the one-parameter Eulerian extension, an explicit verification step is indeed helpful. In the revision we will insert a short paragraph containing both the relevant combinatorial identity and a small-case expansion (for n=2,3 and representative bias values) that confirms the moment sums reduce exactly to the extended Eulerian numbers with no residual terms or hidden parameters. This will make the load-bearing simplification fully explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives a recursive formula for moments of waiting times to restricted target strings S (runs of heads or heads followed by tails) and simplifies it via a one-parameter extension of Eulerian numbers belonging to the Graham-Knuth-Patashnik family. For the general finite-word case on a multi-faced die it applies the standard Goulden-Jackson cluster method together with Faà di Bruno's formula. Both techniques are cited from independent prior literature; the structural restriction on S is explicitly required for the recursion to close, and no load-bearing step reduces a derived quantity to a fitted input, self-definition, or self-citation chain by construction. The central claims remain self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The claims rest on standard combinatorial and analytic identities from prior literature plus one combinatorial extension introduced for the sums.

axioms (2)
  • standard math Faà di Bruno's formula for the higher derivatives of a composition of functions
    Invoked to obtain the closed formula for moments in the general die case.
  • domain assumption Goulden-Jackson cluster method for counting occurrences of words in random sequences
    Used to handle overlaps when establishing the closed formula for arbitrary alphabets.
invented entities (1)
  • one-parameter extension of the Eulerian number no independent evidence
    purpose: To simplify the sums appearing in the recursive moment formulas for the coin-flip case
    Described as belonging to the two-parameter family of Graham, Knuth, and Patashnik; introduced here to close the recursion for the restricted strings.

pith-pipeline@v0.9.0 · 5637 in / 1488 out tokens · 51627 ms · 2026-05-20T03:53:54.248961+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · 1 internal anchor

  1. [1]

    Basdevant, O

    A-L. Basdevant, O. H´ enard,´E. Maurel-S´ egala, and A. Singh, On cases where Litt’s game is fair, C. R. Math. Acad. Sci. Paris363(2025), 977–984

    work page 2025

  2. [2]

    Bates, B

    E. Bates, B. Morrison, M. Rogers, A. Serafini, and A. Sood, A new combinatorial interpretation of partial sums ofm-step Fibonacci numbers, J. Integer Seq.28(2025), no. 6, Art. 25.6.6, 22 pp

    work page 2025

  3. [3]

    A. T. Benjamin, J. D. Neer, D. T. Otero, and J. A. Sellers, A probabilistic view of certain weighted Fibonacci sums, Fibonacci Quart.41(2003), no. 4, 360–364

    work page 2003

  4. [4]

    Cheplyaka, Alice and Bob flipping coins puzzle, March 18, 2024,https://ro-che.info/articles/ 2024-03-18-alice-bob-coin-flipping

    R. Cheplyaka, Alice and Bob flipping coins puzzle, March 18, 2024,https://ro-che.info/articles/ 2024-03-18-alice-bob-coin-flipping

    work page 2024

  5. [5]

    P. W. Diaconis, S. P. Holmes and R. W. Montgomery, Dynamical bias in the coin toss, SIAM Rev.49(2007), no. 2, 211–235

    work page 2007

  6. [6]

    S. B. Ekhad and D. Zeilberger, How to answer questions of the type: if you toss a coin n times, how likely is HH to show up more than HT? The personal Journal of Shalosh B. Ekhad and Doron Zeilberger, May 20, 2024,https: //sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/litt.html

    work page 2024

  7. [7]

    Fulghesu, J

    D. Fulghesu, J. A. Sellers, and C. K. Taylor, Infinite families of infinite series with integer sums, College Math. J.54 (2023), 33-–43

    work page 2023

  8. [8]

    I. P. Goulden and D. M. Jackson, An inversion theorem for cluster decompositions of sequences with distinguished subse- quences, J. London Math. Soc. (2)20(1979), no. 3, 567–576

    work page 1979

  9. [9]

    I. P. Goulden and D. M. Jackson,Combinatorial enumeration, Wiley-Interscience Series in Discrete Mathematics, Wiley, New York, 1983

    work page 1983

  10. [10]

    R. L. Graham, D. E. Knuth and O. Patashnik,Concrete mathematics, second edition, Addison-Wesley, Reading, MA, 1994

    work page 1994

  11. [11]

    G. R. Grimmett, Alice and Bob onX: Reversal, Coupling, Renewal, Amer. Math. Monthly133(2026), no. 5, 439–451

    work page 2026

  12. [12]

    L. J. Guibas and A. M. Odlyzko, String overlaps, pattern matching, and nontransitive games, J. Combin. Theory Ser. A 30(1981), no. 2, 183–208

    work page 1981

  13. [13]

    Huang, A coin flip game and generalizations of Fibonacci numbers, arXiv:2501.07463, to appear in Fibonacci Quart

    J. Huang, A coin flip game and generalizations of Fibonacci numbers, arXiv:2501.07463, to appear in Fibonacci Quart

    work page arXiv

  14. [14]

    Janson, M

    S. Janson, M. Nica, and S. Segert, The generalized Alice HH vs Bob HT problem, J. Theoret. Probab.38(2025), no. 4, Paper No. 83, 52 pp

    work page 2025

  15. [15]

    Litt,X-post, March 16 2024,https://x.com/littmath/status/1769044719034647001

    D. Litt,X-post, March 16 2024,https://x.com/littmath/status/1769044719034647001

    work page arXiv 2024

  16. [16]

    Lutsko, Monkeys typing and martingales,https://chrislutsko.com/files/Abracadabra.pdf

    C. Lutsko, Monkeys typing and martingales,https://chrislutsko.com/files/Abracadabra.pdf

    work page

  17. [17]

    Mansour and M

    T. Mansour and M. A. Shattuck, A combinatorial approach to a general two-term recurrence, Discrete Appl. Math.161 (2013), no. 13-14, 2084–2094

    work page 2013

  18. [18]

    Matsusaka, Applications of Fa` a di Bruno’s formula to partition traces, Res

    T. Matsusaka, Applications of Fa` a di Bruno’s formula to partition traces, Res. Number Theory11(2025), no. 3, Paper No. 69, 11 pp

    work page 2025

  19. [19]

    Neuwirth, Recursively defined combinatorial functions: extending Galton’s board, Discrete Math.239(2001), no

    E. Neuwirth, Recursively defined combinatorial functions: extending Galton’s board, Discrete Math.239(2001), no. 1-3, 33–51

    work page 2001

  20. [20]

    Noonan and D

    J. Noonan and D. Zeilberger, The Goulden-Jackson cluster method: extensions, applications and implementations, J. Differ. Equations Appl.5(1999), no. 4-5, 355–377. 12 JIA HUANG

    work page 1999

  21. [21]

    Segert, A proof that HT is more likely to outnumber HH than vice versa in a string of n coin flips, arXiv:2405.16660 [math.CO]

    S. Segert, A proof that HT is more likely to outnumber HH than vice versa in a string of n coin flips, arXiv:2405.16660 [math.CO]

    work page arXiv

  22. [22]

    J. A. Sellers, Beyond Mere Convergence, PRIMUS (Problems, Resources, and Issues in Mathematics Undergraduate Studies),XII(2002), 157—164

    work page 2002

  23. [23]

    Simonson,Looking for Math in All the Wrong Places: Math in Real Life, AMS/MAA Spectrum Vol

    S. Simonson,Looking for Math in All the Wrong Places: Math in Real Life, AMS/MAA Spectrum Vol. 104, American Mathematical Society, 2022

    work page 2022

  24. [24]

    N. J. A. Sloane et al.,The On-Line Encyclopedia of Integer Sequences, OEIS Foundation Inc.,https://oeis.org

    work page

  25. [25]

    M. Z. Spivey, On solutions to a general combinatorial recurrence, J. Integer Seq.14(2011), no. 9, Article 11.9.7, 19 pp

    work page 2011

  26. [26]

    The method of characteristics, and "problem 89" of Graham, Knuth and Patashnik

    H. S. Wilf, The method of characteristics, and “problem 89” of Graham, Knuth and Patashnik, arXiv:math/0406620

    work page internal anchor Pith review Pith/arXiv arXiv

  27. [27]

    Williams,Probability with martingales, Cambridge Mathematical Textbooks, Cambridge Univ

    D. Williams,Probability with martingales, Cambridge Mathematical Textbooks, Cambridge Univ. Press, Cambridge, 1991. Department of Mathematics and Statistics, University of Nebraska at Kearney, Kearney, NE 68849, USA Email address:huangj2@unk.edu

    work page 1991