{"id":"0bfbf52f-2bac-45b6-9d47-8a01ed0ed1bc","arxiv_id":"1908.04370","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":2.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"First passage time probability generating functions in finite Markov chains satisfy a linear system, which the paper solves in closed form for three states and differentiates for moments.","lead":"This paper uses the collective marks technique to derive a system of equations for the probability generating functions of first passage times in finite Markov chains. It gives a three-state closed form, a moment calculation shortcut, and a product formula for second passage times.","discovery_kind":"incremental","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 4's moment method silently assumes a.s. reachability; for reducible chains ψ_ij(1)<1 and the derivative at z=1 is not the first-passage mean.","rationale":"The central construction in Theorem 2.1 is mathematically sound; the recursive equation is the standard first-step analysis and holds as a formal power series even for defective first-passage distributions. I checked the algebra of Theorem 2.2, the numerics of Example 3.1, and the second-passage convolution in Theorem 5.1; these are correct, with Theorem 5.1 justified by the strong Markov property. The soft spot is Section 4, where the paper converts derivatives at z=1 into expectations without stating the required reachability or positive-recurrence condition. This is not merely a technicality: in reducible chains the moment equations can be underdetermined or produce the defective moment ∑ k f(k) rather than E[X]. Because the paper's examples are irreducible, the flaw does not invalidate the demonstrated cases, but it does limit the claimed general method for moments. The reader's verdict already conditions on this kind of caveat, so I recommend no change to the CONDITIONAL verdict.","tokens_in":3675,"tokens_out":13285,"duration_ms":135684,"concrete_test":"Run the Section 4 derivative algorithm on a two-state absorbing chain P=[[1,0],[0,1]], target j=2, start i=1. The system is ψ12=zψ12, ψ22=z. Differentiating and setting z=1 gives 0=0 for μ12, and ψ12(1)=0≠1, contradicting the paper's claim that ψ_ij(1)=1. As a second check, use states 1,2,3 with p12=p13=0.5, p22=p33=1, target 2: the derivative system yields μ12=0.5 while E[X12]=∞, showing the 'moments' are defective moments, not expected first passage times. Both tests settle that Section 4 requires an added irreducibility or reachability condition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2.1 is correct as a formal identity for the possibly defective pgf ψ_ij(z)=∑_{k≥1} f_ij(k)z^k, including cases where the chain may never hit j. The load-bearing gap is in Section 4. The paper states 'Of course, ψ_ij(1)=1 and ψ'_ij(1)=μ_ij' and then differentiates the linear system at z=1 to compute moments. This requires P(X_ij<∞)=1, which is not guaranteed for a general finite Markov chain. If j is unreachable from i, or reachable with probability q<1 (for example i is transient and the chain may enter a closed class not containing j with positive probability), then ψ_ij(1)=q<1 and ψ'_ij(1) equals ∑ k f_ij(k), not E[X_ij] (which is infinite under the usual ∞ convention). The derivative system can even fail to determine the moment: for P with p11=p22=1 and target j=2 from i=1, the equation ψ12=zψ12 gives only 0=0 after differentiation at z=1. Thus the claimed general moment procedure needs an explicit reachability or positive-recurrence assumption, such as irreducibility; all examples in the paper are irreducible, so they escape the issue.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":3969,"tokens_out":4377,"duration_ms":45606,"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":[{"comment":"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.","section":"Section 4, paragraph after Theorem 2.1"},{"comment":"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":"Theorem 2.1 and its proof"},{"comment":"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.","section":"Section 5, Theorem 5.1"}],"minor_comments":[{"comment":"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":"Example 3.1, ψ33 computation"},{"comment":"'tractible' should be 'tractable'.","section":"Section 4, opening sentence"},{"comment":"'the the resulting expressions' contains a duplicated article; it should read 'the resulting expressions'.","section":"Note (d), Section 2"},{"comment":"Reference [5] misspells 'Carolina' as 'Carloina', and the Acknowledgments contain 'Reseach' for 'Research'; these should be corrected.","section":"References"},{"comment":"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.","section":"Theorem 2.2 and Example 3.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is a short pedagogical note whose central identity is standard; the collective-marks framing and the worked example are nice, but the moment section's missing recurrence assumption is a genuine gap that must be fixed before publication. I would recommend the editors consider whether the journal's scope fits such a lightweight contribution, but the technical issue is fixable with a short added hypothesis and discussion."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: this is a correct but entirely standard derivation dressed up in collective marks. If you know first-step analysis, Theorem 2.1 is the same recursion as in Hunter or Kao, and the three-state closed form is just solving a 2x2 linear system. The second-passage result is a convolution. There is no new capability here.\n\nWhat the paper does well: the collective marks interpretation is a nice way to teach why the pgf equation arises — mark each step with probability z, then the product structure falls out. The 3-state example checks out, the Taylor expansion matches, and the moment trick in Section 4 (differentiate the system before substituting z=1) is a convenient shortcut for small examples. For an expository note, that's fine.\n\nThe soft spots: first, the authors oversell. The abstract says 'a system of equations is found' — that system is the standard first-step recursion. Second, Section 4 has a load-bearing gap: it states 'of course ψ_ij(1)=1 and ψ'_ij(1)=μ_ij' and then differentiates at z=1. That only holds if state j is reached a.s. from i. In a reducible chain the pgf can be defective, and the derivative at 1 is not the mean. All their examples are irreducible, so the numbers are right, but the claim as written is too general. The stress-test note puts this exactly; I agree with it. A one-line assumption like 'assume the chain is irreducible' fixes the section. There are also minor typos — ψ_32 should be p_32 in the ψ_33 computation, and a missing parenthesis in Section 4.\n\nCitation pattern looks fine: they cite Hunter, Kao, van Dantzig, Runnenburg, Kleinrock, Alfa. No self-citation issues. The math is derived, not fitted.\n\nBottom line: this is not a research contribution. It's a short pedagogical note. If the authors reframe it as such and add the reachability condition, it could make a decent classroom note for a teaching journal. I wouldn't send it to a serious probability journal; I'd desk reject with encouragement. If asked to referee a revised, more modest version, I'd accept.","headline":"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.","tokens_in":4450,"tokens_out":3026,"would_cite":false,"duration_ms":30023,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J05","60J22"],"pacs":[],"model":"deepseek-v4-flash","headline":"For a finite Markov chain, first-passage time generating functions solve a single linear system built from the one-step transition probabilities.","keywords":["Markov chains","first passage times","probability generating functions","collective marks","moments of first passage times","second passage times"],"falsifier":"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.","tokens_in":3493,"feed_emoji":"🎲","tokens_out":11014,"duration_ms":100613,"temperature":0.7,"pith_summary":"Using the collective marks method, the paper claims that the probability generating function of the first-passage time from state $i$ to state $j$ in a finite Markov chain satisfies $\\psi_{ij}(z)=p_{ij}z+\\sum_{k\\neq j}p_{ik}z\\,\\psi_{kj}(z)$. Fixing the target state $j$ makes these equations a linear system, so for any fixed number of states the first-passage pgfs are closed-form rational functions of $z$. The paper also shows that differentiating the system before solving gives linear equations for the moments, including the mean first-passage time. This matters because first-passage distributions are used to decide when to intervene in controlled stochastic processes, and the system gives them directly from one-step transition probabilities.","feed_headline":"First-passage times solved by a single linear system","feed_subtitle":"Collective marks turn first-step equations into closed-form generating functions; moments come from derivatives.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the collective marks method itself, the probabilistic marking interpretation on which the proof of Theorem 2.1 rests.","marker":"[6]"},{"why":"Provides the earlier expression $\\psi_{ij}(z)=P_{ij}(z)/(1-P_{ij}(z))$ that the paper contrasts as not a closed form.","marker":"[1]"},{"why":"Gives a queueing-theoretic treatment of collective marks, grounding the marking interpretation used throughout.","marker":"[5]"},{"why":"Chapter 7 is cited as a standard discussion of the collective marks method.","marker":"[4]"}],"fun_headline_variants":["First-passage pgfs from a single linear system","Collective marks reduce first passages to linear algebra","Moments of first passage times via collective-mark equations","One linear system gives first-passage generating functions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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$.","fun_headline_variants_meta":{"raw":{"variants":["First-passage pgfs from a single linear system","Collective marks reduce first passages to linear algebra","Moments of first passage times via collective-mark equations","One linear system gives first-passage generating functions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000612,"raw_usage":{"total_tokens":2745,"prompt_tokens":743,"completion_tokens":2002,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":359,"completion_tokens_details":{"reasoning_tokens":1941}},"tokens_in":359,"tokens_out":2002,"duration_ms":15877,"temperature":1.0,"reasoning_tokens":1941,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:43:50.224643+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Van Dantzig","cited_arxiv_id":null,"evidence_quote":"Supplies the collective marks method itself, the probabilistic marking interpretation on which the proof of Theorem 2.1 rests."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the earlier expression $\\psi_{ij}(z)=P_{ij}(z)/(1-P_{ij}(z))$ that the paper contrasts as not a closed form."},{"cited_title":"Runnenburg","cited_arxiv_id":null,"evidence_quote":"Gives a queueing-theoretic treatment of collective marks, grounding the marking interpretation used throughout."},{"cited_title":"Kleinrock","cited_arxiv_id":null,"evidence_quote":"Chapter 7 is cited as a standard discussion of the collective marks method."}],"review_version":1}