REVIEW 3 major objections 5 minor 6 references
Collective marks and first passage times
T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For a finite Markov chain, first-passage time generating functions solve a single linear system built from the one-step transition probabilities.
desk verdict Correct but standard: collective marks repackage first-step analysis, and the moment shortcut needs an irreducibility assumption; the claims should be trimmed to an expository note. 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 collective-marks reading of a probability generating function: for a path whose steps are marked independently with probability $z$, $\psi(z)$ is the probability that every step receives a mark. Applied to the first step out of state $i$, this yields the linear system in Theorem 2.1, with unknowns $\psi_{1j}(z),\dots,\psi_{nj}(z)$ for a fixed target $j$ and coefficients made of one-step transition probabilities times $z$. Solving that system produces closed-form rational pgfs, and differentiating the system before substituting $z=1$ produces linear equations for first-passage moments.
What would settle it
Take the two-state chain with $p_{11}=1$, $p_{12}=0$, $p_{21}=1$, $p_{22}=0$, so state 1 is absorbing and state 2 returns to 1. The Theorem 2.1 equation for $\psi_{12}(z)$ reduces to $\psi_{12}(z)=z\,\psi_{12}(z)$, forcing $\psi_{12}(z)=0$; since $\psi_{12}(1)=0\neq 1$, this concrete case settles that the unqualified 'moments from derivatives at $z=1$' statement requires a reachability condition.
Extended reading notes
Core claim
The central discovery, stated as Theorem 2.1, is the identity $\psi_{ij}(z)=p_{ij}z+\sum_{k\neq j}p_{ik}z\,\psi_{kj}(z)$ for the first-passage probability generating function of a finite Markov chain. The proof marks every step of the path independently with probability $z$ and reads $\psi_{ij}(z)$ as the probability that all steps of the first path from $i$ to $j$ are marked; conditioning on the first step gives the summed identity. For fixed $j$, the $n$ equations in $\psi_{1j}(z),\dots,\psi_{nj}(z)$ form a linear system whose coefficients are one-step transition probabilities multiplied by $z$, and solving it yields a closed-form rational pgf. The paper works out the three-state case explicitly and then differentiates the system at $z=1$ to obtain moment equations, which is how the method produces moments without first expanding the full pgf.
Load-bearing premise
The argument assumes that the first-passage time from $i$ to $j$ is finite almost surely, so $\psi_{ij}(1)=1$ and derivatives at $z=1$ are ordinary moments; the statement breaks down when $j$ cannot be reached from $i$.
Editorial extensions
If this is right
- For any finite chain and fixed target state $j$, all first-passage pgfs are obtained at once by solving one linear system, and the solution is a rational function of $z$.
- Mean first-passage times and higher moments can be found by differentiating the system and setting $z=1$, bypassing the need to solve for the full pgf first.
- The second-passage time pgf is $\psi_{ij}(z)\psi_{jj}(z)$; repeating the convolution argument gives the $k$-th passage pgf as $\psi_{ij}(z)\psi_{jj}(z)^{k-1}$.
- The three-state closed form in Theorem 2.2 is the small case of the general linear-system solution, so the method scales by solving larger systems.
Reading between the lines
- When state $j$ is unreachable from $i$, the same linear system yields $\psi_{ij}(1)<1$, so the first-passage time is defective; implementations should check reachability before reading moments from derivatives at $z=1$.
- The denominator of every first-passage pgf is $\det(I-zP^{(j)})$, so the poles of the generating function are the reciprocals of the eigenvalues of the substochastic transition matrix among states other than $j$; this ties first-passage tail decay to the spectral gap of that matrix.
- Because the proof only uses the first-step decomposition and independent marking of steps, the system should extend to Markov chains with step-dependent durations by replacing each factor $z$ with the generating function of the step duration.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a method, based on the collective-marks interpretation of probability generating functions, for computing the pgfs and moments of first-passage times for finite Markov chains. Theorem 2.1 gives a linear system of equations for the first-passage pgfs ψ_ij(z), Theorem 2.2 solves this system explicitly for three-state chains, and Section 4 differentiates the system at z=1 to obtain moments. Section 5 extends the idea to second-passage times by multiplying the relevant first-passage pgfs. The paper claims a closed form for a fixed number of states and illustrates the method on a three-state example.
Significance. If properly qualified, the collective-marks derivation is a clean pedagogical route to a standard and useful result: the first-passage pgfs are obtained as rational functions of z by solving a linear system. The paper's strengths are its self-contained derivation, the absence of fitted parameters or assumed conclusions, and the worked three-state example, which the Maple expansion confirms. However, the contribution is essentially a restatement of known first-passage equations in collective-marks language, and the moment-extraction procedure in Section 4 requires an additional recurrence/reachability hypothesis that the paper never states. With that hypothesis added, the method is correct for irreducible finite chains; without it, the central claim that moments can be obtained by differentiating the system at z=1 fails.
major comments (3)
- [Section 4, paragraph after Theorem 2.1] The claim that 'ψ_ij(1)=1 and ψ'_ij(1)=μ_ij' is not true for a general finite Markov chain. If state j is not reachable from i, or if the chain may enter a closed class not containing j with positive probability, then ψ_ij(1)=q<1 and the first-passage time is infinite with positive probability, so the ordinary mean is infinite while ψ'_ij(1)=∑ k f_ij(k) is finite. For example, with P=[[1,0],[0,1]] and target j=2 from i=1, the system from Theorem 2.1 reduces to ψ_12=zψ_12, which gives no information after differentiation at z=1. The moment procedure therefore needs an explicit assumption—irreducibility, or at least that j is reached a.s. from every state that can be reached from i—before it is valid. This is load-bearing because obtaining moments is a central advertised application.
- [Theorem 2.1 and its proof] The theorem is stated for 'the probability generating function for the first passage random variable', which presupposes that hitting j occurs with probability one. For non-communicating states, the first-passage time is defective, and the series ∑ f_ij(k)z^k is still well defined but not a pgf in the usual sense. The equation ψ_ij(z)=p_ij z+∑_{k≠j}p_ik z ψ_kj(z) remains valid as a formal power series identity, and the proof's phrase 'the process moves to state j eventually' should be softened to 'if the process ever reaches j'. Adding a sentence distinguishing the formal identity from the probabilistic interpretation would remove this ambiguity.
- [Section 5, Theorem 5.1] The decomposition Y_ij=X_ij+X_jj is correct under the strong Markov property, but it also requires that the second passage time is a.s. finite, i.e., that the return time X_jj is finite a.s. In a finite reducible chain with transient j, second passage may never occur. The theorem should either be stated under the same irreducibility assumption used in Section 4, or explicitly allow defective generating functions.
minor comments (5)
- [Example 3.1, ψ33 computation] The expression 'ψ_32 z ψ_23(z)' should be 'p_32 z ψ_23(z)'; the numeric value in the next line confirms that p_32=0.4 was intended.
- [Section 4, opening sentence] 'tractible' should be 'tractable'.
- [Note (d), Section 2] 'the the resulting expressions' contains a duplicated article; it should read 'the resulting expressions'.
- [References] Reference [5] misspells 'Carolina' as 'Carloina', and the Acknowledgments contain 'Reseach' for 'Research'; these should be corrected.
- [Theorem 2.2 and Example 3.1] The denominator in Theorem 2.2 is written as '1 − (p11 + p22)z + (p11p22 − p12p21)z^2', which is correct, but the subsequent example uses numbers that satisfy this; please double-check that the displayed p-values in Example 3.1 are formatted consistently with the transition matrix P after OCR-like spacing issues are fixed.
Circularity Check
No circularity: the first-passage pgf system is derived from the Markov property via collective marks, with no fitted parameters, self-citations, or assumption of the target result.
full rationale
The paper's derivation chain is self-contained. Theorem 2.1 obtains ψ_ij(z) = p_ij z + ∑_{k≠j} p_ik z ψ_kj(z) directly from the collective-marks probabilistic interpretation and the one-step Markov property, so the system is derived rather than imposed. Theorem 2.2 then solves a two-equation instance of that derived system, and the moments in Section 4 are obtained by differentiating the same derived system and evaluating at z=1. No parameter is fitted to the outputs, and no load-bearing claim is justified by a self-citation; all references are to external literature. The main mathematical gaps are assumption issues, not circularity: Section 4's statement 'Of course, ψ_ij(1)=1 and ψ'_ij(1)=μ_ij' presumes that first passage is almost surely finite, which is not guaranteed for arbitrary finite Markov chains, and Theorem 5.1 treats X_ij and X_jj as independent without justification. These are correctness or rigor concerns, but the conclusions are not equivalent to the paper's inputs by construction. Accordingly, the circularity score is 0.
Assumptions & free parameters
assumptions (3)
- domain assumption Markov property: given the present state, the future is independent of the past.
- domain assumption Collective marks interpretation: the probability generating function ψ(z) equals the probability that every step of a realization receives a mark when each step is marked independently with probability z.
- ad hoc to paper The first-passage pgfs satisfy a uniquely solvable linear system for fixed j, without explicit handling of non-communicating states or defective pgfs.
Cite this review
Pith. "Pith review of Collective marks and first passage times." pith.science (2026). https://pith.science/paper/IPXFQHTC
@misc{pith2026190804370,
author = {Pith},
title = {Pith review of: Collective marks and first passage times},
year = {2026},
howpublished = {\url{https://pith.science/paper/IPXFQHTC}},
note = {Machine review of arXiv:1908.04370}
}
read the original abstract
Probability generating functions for first passage times of Markov chains are found using the method of collective marks. A system of equations is found which can be used to obtain moments of the first passage times.
Reference graph
Works this paper leans on
-
[1]
A.S. Alfa. Applied Discrete-time Queues , second edition. Springer. 2014
work page 2014
-
[2]
Hunter, Mathematical Techniques of Applied Probability Vol
J.J. Hunter, Mathematical Techniques of Applied Probability Vol. 1 . Aca- demic Press. 1983
work page 1983
-
[3]
E. Kao. An Introduction to Stochastic Processes . Duxbury Press. 1996
work page 1996
- [4]
-
[5]
J.T. Runnenburg. On the use of Collective Marks in Queueing Theor y. In W.L. Smith and W.E. Wilkinson, editors, Congestion Theory. pp. 399-4 38. University of North Carloina Press. 1965
work page 1965
-
[6]
D. Van Dantzig. Sur methode des fonctions generatrices. Colloq ues inter- nationaux du CNRS, 13: 29-45, 1949
work page 1949
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.