REVIEW 6 minor 8 references
On a Variation of Gambler's Ruin Problem
T0 review · 0 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read For a Markovian text, the ruin probability of a two-word game equals the ruin probability of an embedded correlated random walk, and the expected duration follows from one additional linear system.
desk verdict A clean, correct extension of gambler's ruin to two-word pattern games over Markovian text; the new duration formula makes it worth a serious referee. 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 object is the pair of embedded chains. The first, $X_k$, is a two-state Markov chain taking values $+1$ and $-1$ that records whether the $k$-th completed hit is $U$ or $D$; it carries the ruin probability because $S_{\tau_k}$ equals its partial sum. The second, $Z_k$, is the look-back chain whose state is the longest suffix of the text that is a single letter or a prefix of $U$ or $D$; this is the chain on which first-step analysis is actually performed. Hitting probabilities for $Z_k$ give the transition matrix of $X_k$, and conditional mean waiting times between hits give $a$ and $b$. The key identity is formula (2), which expresses the mean game duration $E(\tau)$ as an affine function of $\alpha$, $E(T)$, and the conditional inter-hit means, obtained via a martingale-difference decomposition of the inter-hit times.
What would settle it
Run the fair-coin example with $U=11$ and $D=01$, $A=3$ and $B=5$: the paper's formula gives $\alpha=(B-1/2)/(A+B)=4.5/8=0.5625$ and $E(\tau)=2AB+B-A+1=30+5-3+1=33$. An exact enumeration or a long simulation of the letter chain that disagrees with these numbers would refute the reduction; agreement would confirm it.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that the two-word gambling problem reduces to the gambler's ruin problem for a correlated random walk. If $X_k$ is $+1$ when the $k$-th completed hit is $U$ and $-1$ when it is $D$, then $S_{\tau_k}=X_1+\cdots+X_k$, so the win probability $\alpha$ equals $P(X_1+\cdots+X_T=A)$ for the embedded walk stopped at $A$ or $-B$. For the duration, Proposition 2 states $E(\tau)=E(\gamma_1)+a[(A+B-2)\alpha-(B-1)]+b[E(T)-1]$, where $\gamma_j$ are the times between completed hits, $a$ and $b$ are conditional mean inter-hit times, and $T$ is the number of hits. The quantities $E(\gamma_1)$, $a$, $b$, and the transition probabilities of $X_k$ are obtained by first-step analysis on a finite prefix chain whose states are letters plus prefixes of $U$ and $D$, reducing everything to two linear systems of the form $(I-Q)^{-1}$ times a known vector. The method works for any irreducible letter chain satisfying a positivity condition, not only for i.i.d. sources, and it handles overlapping occurrences.
Load-bearing premise
The central assumption is that $U$ and $D$ are incomparable as words: neither contains the other as a contiguous subword, so each completed occurrence ends exactly one tracked word and the embedded chain is well defined.
Editorial extensions
If this is right
- The ruin probability $\alpha$ for any admissible word pair is found by solving a linear system whose size is at most the alphabet size plus the total number of prefixes of $U$ and $D$.
- The expected time to reach either boundary is finite whenever the embedded two-state chain is aperiodic, and formula (2) gives it directly from $\alpha$ and $E(T)$.
- The method applies to texts produced by any irreducible Markov chain, not just independent letter sequences, making it usable for dependent sources.
- For binary alphabets with a strictly positive transition matrix, periodicity of the embedded chain happens exactly for alternating words of the forms $y^t(1-y)^s$ and $(1-y)^s y^t$ with $s=1$ or $t=1$; outside these cases the game ends almost surely.
- For alphabets with at least three letters and a strictly positive transition matrix, the embedded chain is aperiodic for every admissible pair, so the game always terminates almost surely.
Reading between the lines
- If one word were a subword of the other, a single text position could end both words, so the embedded chain $X_k$ would not be well defined; extending the method would require splitting such combined occurrences, which the paper does not attempt.
- The same prefix-state machinery should extend to three or more tracked words, replacing the two-state chain by a larger finite-state chain; the linear-system size would remain polynomial in the total word lengths.
- The affine structure of the duration formula suggests that similar mean-waiting-time identities hold for other delayed or zero-increment correlated walks, beyond the literal word game.
- The open characterization of letter chains for which every admissible word pair gives finite $\tau$ could be attacked by classifying periodic embeddings of two-state chains; the paper settles the binary case and shows larger alphabets behave differently.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies a gambler's ruin problem in which letters generated by a finite-state Markov chain carry scores: each occurrence of a word U adds 1 and each occurrence of a distinct word D subtracts 1, with overlapping occurrences counted. The authors construct two embedded Markov chains: a two-state chain X_k indicating whether the k-th occurrence word is U or D, and a larger look-back chain Z_k on prefix states. They show that the win probability equals the ruin probability of the correlated random walk generated by X_k, and they derive Proposition 2, an exact formula for the expected duration E(τ) in terms of the win probability α, the mean embedded duration E(T), and conditional mean inter-occurrence times. First-step analysis is used to compute the transition probabilities and expected inter-arrival times, a fair-coin example is worked out, and Section 7 characterizes when the embedded chain is aperiodic.
Significance. The reduction is clean and the main formula (2) is an explicit, parameter-free identity that reduces a two-word text problem to the classical gambler's ruin problem for correlated random walks. The paper is honest about its scope: it assumes neither word is a subword of the other and identifies the aperiodicity condition needed for finiteness. The worked example is consistent with direct computation, and the first-step analysis is transparent. The main value is methodological: the paper gives a systematic embedding that handles Markovian text and overlapping occurrences, and it supplies a duration formula that cannot be obtained from the two-state chain alone. I have no load-bearing technical objection; the issues below are local and can be addressed in revision.
minor comments (6)
- [Section 2] In the definition of D_i, the indicator uses u_1,...,u_M instead of d_1,...,d_M; this is a typo that should be corrected for clarity.
- [Section 4] The Optional Stopping Theorem is invoked without verifying its conditions. The argument is standard because the embedded chain X is finite-state and, when aperiodic, T has finite expectation and the martingale differences are bounded, but a sentence stating these conditions would make the proof self-contained.
- [Sections 3 and 5] The proof of Proposition 1 is only sketched as 'straightforward.' Since the unique recurrent class claim is used in Lemma 1, a few lines showing that every state in Δ~ can reach {U,D} with positive probability would strengthen the exposition.
- [Sections 3-6] The paper relies on Mohan (1955) for the values of α and E(T) of the embedded correlated random walk but never states the relevant formulas or the linear equations that determine them. For self-containedness, the authors should either quote the needed result from Mohan or derive the first-step equations for α and E(T) directly.
- [Section 7] The equivalence between 'aperiodic' and 'strictly positive transition matrix' is stated without qualification; it is true for an irreducible two-state Markov chain and should be phrased as such.
- [Proposition 2] There is a typo in the statement: 'ia aperiodic' should read 'is aperiodic.'
Circularity Check
No significant circularity: the gambler's-ruin reduction and duration formula are derived from first-step analysis and external benchmarks, not from fitted inputs or load-bearing self-citation.
full rationale
The paper's central steps are exact identities and first-step analyses rather than circular reductions. In Section 3, the embedded chain X_k is defined directly from the hitting times of U and D, giving S_{tau_k}=X_1+...+X_k; this is a construction, not an assumption equivalent to the target. The ruin probability alpha is then expressed as P(X_1+...+X_T=A), with T defined by the correlated random walk, matching Mohan (1955), an external reference. Section 4 derives E(tau) via the strong Markov property, optional stopping, and a linear conditional-expectation relation E(gamma_{j+1}|X_j)=aX_j+b; the constants a and b are computed from the embedded chain's first-step equations, not fitted to the duration. Section 5 solves for the needed hitting probabilities and expected return times using I-Q invertibility and linear equations (3)-(4). The self-citation to Pozdnyakov (2025) is explicitly comparative and not load-bearing: the paper states that the martingale approach there cannot be used for different words and instead employs first-step analysis. The assumptions that neither word is a subword of the other and that {X_k} is aperiodic are stated limitations, and Section 7 openly leaves a full characterization open, which is a scope limitation, not circularity. No fitted parameter is renamed as a prediction, and no central claim reduces by construction to its own inputs.
Assumptions & free parameters
assumptions (6)
- domain assumption The original letter sequence {Y_i} is a time-homogeneous irreducible finite Markov chain.
- domain assumption The words U and D are distinct, neither is a subword of the other, and both have positive probability of occurring.
- standard math Strong Markov property and optional stopping theorem for martingale differences.
- standard math Perron-Frobenius theorem and basic properties of nonnegative matrices.
- standard math Mohan's gambler's ruin formulas for correlated random walks.
- domain assumption The embedded two-state chain {X_k} is aperiodic.
Cite this review
Pith. "Pith review of On a Variation of Gambler's Ruin Problem." pith.science (2026). https://pith.science/paper/IMHHSEJK
@misc{pith2026250600990,
author = {Pith},
title = {Pith review of: On a Variation of Gambler's Ruin Problem},
year = {2026},
howpublished = {\url{https://pith.science/paper/IMHHSEJK}},
note = {Machine review of arXiv:2506.00990}
}
abstract
Assume that letters (from a finite alphabet) in a text form a Markov chain. We track two distinct words, $U$ and $D$. A gambler gains 1 point for each occurrence of $U$ (including overlapping occurrences) and loses 1 point for each occurrence of $D$ (also including overlapping occurrences). We determine the probability of gaining $A$ points before losing $B$ points, where $A$ and $B$ are integers. Additionally, we find the expected waiting time until one of the two events -- gaining $A$ points or losing $B$ points -- occurs.
Reference graph
Works this paper leans on
-
[1]
W. Feller (1968). An introduction to probability theory and its applications. V ol. I \/ . John Wiley & Sons, Inc., New York-London-Sydney, third edition
work page 1968
-
[2]
H. U. Gerber and S.-Y. R. Li (1981). The occurrence of sequence patterns in repeated experiments and hitting times in a markov chain. Stochastic Process. Appl.\/ 11 , 101--108
work page 1981
- [3]
-
[4]
A. Gut (2013). The gambler's ruin problem with delays. Statist. Probab. Lett.\/ 83 , 2549--2552
work page 2013
-
[5]
M. E. Lladser (2007). Minimal markov chain embeddings of pattern problems. In 2007 Information Theory and Applications Workshop\/ , pp. 251--255
work page 2007
-
[6]
C. Mohan (1955). The gambler's ruin problem with correlation. Biometrika\/ 42 , 486--493
work page 1955
-
[7]
V. Pozdnyakov (2025). Martingale approach to gambler's ruin problem for correlated random walks. J. Appl. Probab.\/ 62 , to appear
work page 2025
-
[8]
J. M. Steele (2001). Stochastic calculus and financial applications\/ , volume 45 of Applications of Mathematics (New York)\/ . Springer-Verlag, New York
work page 2001
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.