REVIEW 2 major objections 5 minor 2 references
Gambler's Ruin? Some Aspects of Coin Tossing
T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For any fixed string of heads and tails, the average number of tosses until it first appears is always an even integer.
desk verdict A correct and clean teaching account of the classic autocorrelation formula, but the main algorithmic claim is not new and the crucial decomposition is asserted rather than proved. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing device is the pair of counting functions $\sigma_n$ and $\tau_j$, together with the branching identity $2\sigma_{n-1} = \sigma_n + \tau_n$, which says that a length-$(n-1)$ string avoiding the pattern either remains avoiding when a bit is appended or becomes a first occurrence at the end. Iterating and summing yields $N = \sum \sigma_n / 2^n$ and, ultimately, $N_{T_m} = \sum_{j=1}^m c_j 2^j$. The coefficient $c_j$ is 1 when a string of the form $S_n T_m$, truncated at length $n+j$, still ends in $T_m$; $c_m$ is always 1. The appendix supplies the convergence identity $\sum_j \tau_j / 2^j = 1$, which turns the infinite sums into a finite sum of powers of two.
What would settle it
Compute the expected waiting time for a longer pattern, say $T = 10110$, by solving the exact linear equations of the Markov chain whose states are the prefixes of $T$, and compare the result with the value $\sum c_j 2^j$ obtained from Eq. (27). If any pattern of length up to 8 gives a non-even expectation, or any coefficient $c_j$ is forced to lie outside $\{0,1\}$, the central claim collapses.
Extended reading notes
Core claim
The paper's central claim is that the expected number of fair-coin tosses needed for a specified string $T_m = (t_1 \ldots t_m)$ to occur for the first time is always an integer, and in fact always even. More precisely, writing $\sigma_n$ for the number of length-$n$ strings that avoid $T_m$ and $\tau_j$ for the number of length-$j$ strings whose last $m$ bits are $T_m$ and which contain $T_m$ nowhere else, the paper establishes $N_{T_m} = \sum_{n\ge 0} \sigma_n / 2^n = \sum_{j=1}^m c_j 2^j$, where $c_m=1$ and each $c_j$ is 0 or 1. The coefficients are found by asking, for each $j$, whether a truncation of $(S_n T_m)$ of length $n+j$ can end in $T_m$. The method reproduces all earlier examples and fills in the remaining triples, quadruples, quintuples, and sextuples in Table 3, every entry of which is an even integer.
Load-bearing premise
The whole argument rests on the claim that every string that avoids the target pattern falls into exactly one of the classes counted by the $\tau$ terms in Eq. (26), with each pattern described by 0-or-1 coefficients; this decomposition is illustrated on one example but not proved in full generality.
Editorial extensions
If this is right
- For every pattern of length $m$, the expected waiting time lies between $2^m$ and $2^{m+1} - 2$; the endpoints are realized by the pattern $100\ldots 0$ and the all-ones pattern $111\ldots 1$.
- Every expected waiting time in Table 3 is a sum of distinct powers of two; for example, $10101$ has average wait $42 = 2 + 8 + 32$ tosses.
- The gambler's wager from the introduction is decided: betting on $HH$ (average 6 tosses) is better than betting on $TH$ (average 4 tosses), and the same style of comparison can be made for any two patterns by adding their $c_j 2^j$ values.
- Computing the average wait for a new pattern reduces to checking which truncations are consistent with the pattern, a task the paper presents as doable by hand for patterns of length up to six and beyond.
Reading between the lines
- The coefficients $c_j$ appear to be exactly the 'border' lengths of the pattern, namely the lengths $j$ for which the pattern's prefix of length $j$ equals its suffix of length $j$; the paper does not state this identification in so many words, but it would connect Eq. (27) to the classical autocorrelation identity for pattern waiting times.
- For a biased coin, the same border set should enter a formula with powers of $1/p$ and $1/q$ instead of $2$, so the even-integer conclusion will fail; testing this would be a direct extension of Eq. (27).
- The method also suggests an automaton-free way to compute waiting times for overlapping patterns in alphabets of more than two symbols, where the coefficients would still be 0 or 1 but the base of the powers would change.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript studies the expected number of tosses of a fair coin until a given binary pattern T_m = (t_1 ... t_m) appears for the first time. For the patterns 01, 11, 100, and 110, the authors compute the expectations by explicit counting and by recursion relations. They then introduce a general method: if sigma_n is the number of length-n strings avoiding T_m and tau_k is the number of length-k strings whose last m bits equal T_m with no earlier occurrence of T_m, then the identity 2 sigma_{n-1} = sigma_n + tau_n leads to N_{T_m} = sum_{n>=0} sigma_n / 2^n. The paper's central step is the assertion that sigma_n = sum_{j=1}^m c_j tau_{n+j} with c_m = 1 and the remaining c_j equal to 0 or 1. This yields N_{T_m} = sum_{j=1}^m c_j 2^j, proving that every waiting-time expectation is an even integer. A table of values for patterns of length 2 through 6 is included, including N = 42 for T_5 = 10101.
Significance. If the decomposition in Eq. (26) were fully proved, the paper would provide a clean, hand-computable derivation of the classical pattern-waiting-time formula and an elegant explanation of why these expectations are always even integers. The numerical values in Table 3 match known results, and the elementary derivations in Sections 2 and 3 for 01, 11, 100, and 110 are correct and clearly presented. The paper is didactic and accessible. However, the central assertion is currently supported only by one worked example (T_5 = 10101) rather than a proof for arbitrary patterns, and the same unproved step is used in the Appendix to establish the normalization identity on which the whole derivation depends.
major comments (2)
- [Section 4, Eq. (26)] The decomposition sigma_n = sum_{j=1}^m c_j tau_{n+j} is the crucial bridge between avoidance counts and first-occurrence counts, but it is not proved for general T_m. The paper illustrates it for T_5 = 10101 and gives an informal description: 'The coefficient c_j is equal to zero if the string (S_n T_m), truncated at order n+j, does not contain T_m for its last m bits; otherwise it is equal to one.' This is not a definition of a coefficient depending only on T_m; it refers to the particular S_n and to n. The proof must show that for every n and every S_n avoiding T_m, the concatenated string S_n T_m has a unique first occurrence of T_m at some position n+j, that this j depends only on the border (prefix-suffix) structure of T_m, and that the resulting classes are disjoint and exhaustive. Without such a proof, Eqs. (26) and (27) are not established for arbitrary patterns.
- [Appendix, Eq. (30)] The proof of the normalization identity sum_{j=m}^{\infty} tau_j / 2^j = 1 uses Eq. (26) to conclude that sigma_n / 2^n tends to 0 as n tends to infinity. Since Eq. (26) is exactly the unproved decomposition, Eq. (30) is not established independently. The subsequent use of Eq. (30) in deriving Eq. (18) and then Eq. (27) is therefore circular unless a proof of Eq. (26) or an alternative proof of Eq. (30) is supplied. The manuscript should either prove the convergence of sigma_n / 2^n without relying on the decomposition, or restructure the Appendix so that the normalization identity is derived before the decomposition is introduced.
minor comments (5)
- [Section 3, around Eq. (9)] The text states 'K_m(110) = M_{m-1}(100; 11) = F_m - 1' and then 'From Eq.(9) we see that this is the same formula as the one we derived for the triple 100.' The first expression contains an apparent typo: it should read M_{m-1}(110; 11), not M_{m-1}(100; 11). Please correct this.
- [Section 4, after Eq. (26)] The definition of the coefficients c_j should be stated directly in terms of the pattern T_m: c_j = 1 if the prefix of T_m of length j equals its suffix of length j (a border), and c_j = 0 otherwise. The current phrasing, which refers to the string (S_n T_m) 'truncated at order n+j', makes the coefficient appear to depend on n and on the particular S_n. Such a reformulation would also make clear that the decomposition in Eq. (26) is a partition of the avoided strings according to the first completion position.
- [Section 4, Eq. (20)] The summation index j in Eq. (20) starts at 0, but tau_j is zero for j < m. For clarity, the lower limit should be m, matching the later line 'The lower limit of the summation on the right-hand side has been changed to j = m.'
- [Table 3] The layout of Table 3 is difficult to parse. For example, the row '2 6 11' is intended to mean that for length-2 patterns, the string 11 has average 6, while the length-2 value 4 for 10 is shown in a separate column. Please reformat the table so that each row explicitly gives the pattern length, the average, and the corresponding string(s).
- [Throughout] There are several typographical errors, including 'DA VID ATKINSON' in the author line, 'a part icular' and 'first' in the abstract, and inconsistent use of 'T_m' versus 'Tm' in the text. A careful proofreading pass is recommended.
Circularity Check
No circularity: the derivation is self-contained and does not assume the target result.
full rationale
The paper derives the waiting-time averages from first principles of counting binary strings. Equations (17) and (18) relate the avoidance counts sigma_n to the first-occurrence counts tau_j, and the target formula N_Tm = sum c_j 2^j is obtained by summing sigma_n/2^n and using the normalization identity (30). The final even-integer claim is an algebraic consequence of that formula, not an input to it. There are no fitted parameters, no self-citations used as evidence, and no invocation of prior work to forbid alternatives. The only substantive weakness is that Eq. (26), the decomposition sigma_n = sum c_j tau_{j+n} with c_j in {0,1}, is asserted rather than fully proved for arbitrary patterns; the paper supports it with one worked example and an informal description of c_j. That is a rigor gap in the proof, not circularity, because the decomposition is independent of the evenness conclusion and is not derived from it. The correct non-circular finding is therefore score 0.
Assumptions & free parameters
assumptions (3)
- domain assumption Coin tosses are fair and independent, so all 2^n sequences of length n are equally likely.
- standard math The series sum_{j=m}^{∞} τ_j/2^j converges and equals 1.
- standard math Standard Fibonacci number identities used in Sections 2 and 3.
Cite this review
Pith. "Pith review of Gambler's Ruin? Some Aspects of Coin Tossing." pith.science (2026). https://pith.science/paper/EL6NECPZ
@misc{pith2026190809234,
author = {Pith},
title = {Pith review of: Gambler's Ruin? Some Aspects of Coin Tossing},
year = {2026},
howpublished = {\url{https://pith.science/paper/EL6NECPZ}},
note = {Machine review of arXiv:1908.09234}
}
read the original abstract
What is the average number of tosses needed before a particular sequence of heads and tails turns up? We solve the problem didactically, starting with doubles, finding that a tail, followed by a head, turns up on the average after only four tosses, while six tosses are needed for two successive heads. The method is extended to encompass the triples head-tail-tail and head-head-tail, but head-tail-head and head-head-head are surprisingly more recalcitrant. However, the general case is finally solved by a new algorithm that allows a simple computation that can be done by hand, even for relatively long strings. It is shown that the average number of tosses is always an even integer.
Reference graph
Works this paper leans on
-
[1]
Feller, W. (1968). An Introduction to Probability and its Application, Vol. I. , 3rd edition. New York, Wiley. 14 Johnson Atkinson
work page 1968
-
[2]
Gardner, M. (1988). “Nontransitive Paradoxes,” in Time Travel and Other Mathematical Bewilderments. New York: W. H. Freeman, pp. 64-66. Gambler’s Ruin: Some Aspects of Coin Flipping 15 Num bits Average Terminating String(s) 4 10 2 6 11 8 100, 110 3 10 101 14 111 16 1000, 1100, 1110 18 1001, 1011, 1101 4 20 1010 30 1111 32 10000, 10100, 11000, 11010, 11100...
work page 1988
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.