{"id":"40133b6c-f362-4db9-97d0-5e60f349081a","arxiv_id":"1908.09234","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":2.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The expected waiting time for any fixed binary pattern under fair coin tossing is an even integer, computed by a simple counting algorithm.","lead":"This paper calculates the average number of fair coin tosses needed before a specified pattern of heads and tails appears. It shows the average is always an even integer, offering a precise take on a classic gambler's fallacy puzzle.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The even-integer waiting-time claim depends on Eq. (26), which is asserted but not proved for general Tm; Table 3 is correct, but the proof as written has a gap.","rationale":"The reader's weakest-assumption identification matches the structural location of the gap: Eq. (26) is the bridge between avoidance counts and first-occurrence counts, and it is not proved in general. I agree that this is the most load-bearing spot. The central claim itself is a known theorem and Table 3 is correct; the computations check out. Because the missing piece is a fillable proof rather than a false statement, the appropriate verdict remains conditional, as the reader already set. I do not see a reason to move to accept, reject, or unverified on the basis of this review.","tokens_in":8529,"tokens_out":12713,"duration_ms":129266,"concrete_test":"For every binary pattern Tm with 1 <= m <= 6 (126 patterns), compute sigma_n by dynamic programming over automata for n=0..30, compute tau_k as the number of length-k strings whose first occurrence of Tm ends at k, and test Eq. (26) with c_j = 1 exactly when the length-j prefix of Tm equals its length-j suffix. Any violation would invalidate the central claim; if no violation occurs, the formula is at least verified in all small cases, and the remaining issue is the missing general proof of Eq. (26) via the border bijection.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central result, NTm = sum c_j 2^j yielding an even integer, rests entirely on Eq. (26): sigma_n = sum_{j=1}^m c_j tau_{j+n} with c_m=1 and c_j in {0,1}. This is the only step that relates the avoidance counts sigma_n to the first-occurrence counts tau_k for an arbitrary pattern Tm. The paper supports it with one worked example (T=10101) and an informal statement that 'The coefficient c_j is equal to zero if the string (SnTm), truncated at order n+j, does not contain Tm for its last m bits; otherwise it is equal to one.' That description is not a definition of c_j from T alone: it is a property of the extended string that depends on n and on the particular Sn, and the text never proves that such a coefficient is well-defined, independent of n, or that the classes are disjoint and exhaustive. Moreover, the Appendix proves the normalization identity Eq. (30), sum tau_i/2^i = 1, by using Eq. (26) to show sigma_n/2^n -> 0; so the convergence used in deriving Eq. (27) is not established independently of the unproved decomposition. If Eq. (26) failed for some pattern, Eq. (27) and the universal evenness assertion would not follow. The identity is in fact true—it is the standard border/autocorrelation decomposition—so the paper states a correct theorem but gives an incomplete proof of the crucial bridge.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8743,"tokens_out":7473,"duration_ms":73805,"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":[{"comment":"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.","section":"Section 4, Eq. (26)"},{"comment":"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.","section":"Appendix, Eq. (30)"}],"minor_comments":[{"comment":"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":"Section 3, around Eq. (9)"},{"comment":"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":"Section 4, after Eq. (26)"},{"comment":"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.'","section":"Section 4, Eq. (20)"},{"comment":"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).","section":"Table 3"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The result that the expected waiting time for a fixed binary pattern is an even integer is classical in pattern-matching theory, and the paper's contribution is primarily its elementary, self-contained derivation. The missing proof of Eq. (26) is a genuine gap in the central argument, so the revision should be substantive rather than cosmetic. If the authors can supply a rigorous proof of the decomposition, the paper would be a worthwhile didactic contribution to an applied-probability or teaching-oriented venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nI read Johnson and Atkinson's coin-tossing note. The genuinely solid part is the elementary treatment of doubles and triples: the recursion calculations in Sections 2 and 3 are correct and do give 4, 6, 8, and the pattern continues. The table of waiting times for strings up to length six matches what you get from the standard formula, and the observation that all the averages are even is right.\n\nWhat is not new is the 'new algorithm' in Section 4. Equation (27) is exactly the Conway leading-number / autocorrelation formula (Li 1980; Guibas and Odlyzko 1981). Once you recognize that, the evenness result is immediate because the sum is over positive powers of two. The paper's failure to cite that literature is the main editorial problem; it also makes the novelty claim in the abstract inaccurate.\n\nThe bigger mathematical soft spot is Eq. (26). The paper asserts for a general pattern Tm that sigma_n = sum c_j tau_{j+n} with c_j in {0,1}, but it only demonstrates this on one example (T=10101) and an informal description of c_j that depends on the string Sn, not just on T. No proof is given that the classes are disjoint and exhaustive for arbitrary self-overlapping patterns. The theorem is true, but as written the proof has a real gap. The appendix's derivation of Eq. (30) also leans on Eq. (26) via the claim that sigma_n/2^n tends to 0, so the convergence is not established independently.\n\nMinor: the referencing is thin. Feller and Gardner are fine popular citations, but for the main result the prior work should be acknowledged.\n\nBottom line: this is a usable teaching note for an undergraduate probability course. It does not open a new research direction, and it should not be presented as a new result. If it came into my inbox, I would desk-reject it as a research submission, or, if the venue has a teaching-notes track, send it there with a request to cite Li and Guibas-Odlyzko and to turn Eq. (26) into a real proof. Do not spend referee time on it as a research paper.","headline":"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.","tokens_in":9363,"tokens_out":2563,"would_cite":false,"duration_ms":27870,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60G40","91A60","91A80"],"pacs":[],"model":"deepseek-v4-flash","headline":"For any fixed string of heads and tails, the average number of tosses until it first appears is always an even integer.","keywords":["coin tossing","waiting time","pattern occurrence","expected value","even integer","self-overlap","Fibonacci numbers","gambler's fallacy"],"falsifier":"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.","tokens_in":8248,"feed_emoji":"🪙","tokens_out":6683,"duration_ms":66639,"temperature":0.7,"pith_summary":"This paper answers a classic question: if you keep tossing a fair coin, how many tosses, on average, until a specified pattern such as TH or HH first appears? It works through the simple cases of doubles and some triples, then introduces a counting algorithm that handles arbitrary patterns. The central result is that for every binary pattern $T_m$ of length $m$, the expected waiting time is an even integer, computed as $N = \\sum_{j=1}^m c_j 2^j$ with $c_m = 1$ and each other $c_j$ equal to 0 or 1. This explains the numerical values (4 for TH, 6 for HH, 8 for HTT and HHT, 42 for 10101) and gives a method that can be carried out by hand even for long strings.","feed_headline":"Average wait for any coin pattern is an even integer","feed_subtitle":"A hand-computable formula assigns each head-tail string a waiting time like 4, 6, 8, or 42 tosses.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[],"fun_headline_variants":["Average tosses to any coin pattern is always even","Every coin string's average wait time is an even integer","Coin pattern waits: always even integers, hand-computable","Even integers only: how long to wait for a coin sequence","Hand-computable rule: coin pattern waits are even"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Average tosses to any coin pattern is always even","Every coin string's average wait time is an even integer","Coin pattern waits: always even integers, hand-computable","Even integers only: how long to wait for a coin sequence","Hand-computable rule: coin pattern waits are even"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001278,"raw_usage":{"total_tokens":5206,"prompt_tokens":906,"completion_tokens":4300,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":4218}},"tokens_in":522,"tokens_out":4300,"duration_ms":29005,"temperature":1.0,"reasoning_tokens":4218,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:18:30.719423+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}