{"id":"7970c801-e8cf-46f6-a620-08792255078c","arxiv_id":"2501.13187","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A one-sided sequential test for a known Markov chain against any unknown alternative achieves SPRT-level expected stopping times when the estimator has logarithmic regret.","lead":"This paper designs a sequential test that decides, as quickly as possible, whether a stream of observations comes from a known Markov chain or from any different one. The test uses a data-driven estimate of the unknown alternative and provably stops as fast as if that alternative were known in advance.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's stopping-time proof requires a pointwise Markov regret bound that Definition 2 does not formally define; without it, the pathwise domination step and the E[τ] bound are not established.","rationale":"I read the paper as having two main results: a type-1 error bound (solid, by Ville's inequality for any causal estimator) and the expected stopping time bound in Theorem 2 that constitutes the advertised adaptive-to-unknown-alternative property. The lynchpin of Theorem 2 is the replacement of the actual statistic L by the oracle L* at a cost r_t = O(log t). This replacement must be pathwise: the proof defines τ* as the first hitting time of a moving boundary log(1/α)+r_t and then bounds E[τ*] via a Markov Wald identity. If the regret r_t is only controlled in expectation, the event {log L*_t ≥ log(1/α)+r_t} does not imply {log L_t ≥ log(1/α)} for every path, so the domination argument fails. Definition 2, however, is written for i.i.d. distributions (q ∈ Δ^{m−1}), and the paper does not formalize the Markov analogue or prove that the Jeffreys-mixture estimator attains the stated pointwise bound. This is a genuine gap in the proof as written, not merely a disagreement with external consensus. The typos in the proof (set vs. infimum for τ*, mismatched star in the overshoot term) reinforce that the proof is not yet rigorous, but the pointwise-regret gap is the substantive issue. I agree with the reader's weakest_assumption; the reader's conditional-accept recommendation remains appropriate, since the gap appears fixable by adding the missing definition and citing/deriving the pointwise Markov regret bound. The secondary concern is the omitted proof of Remark 4 (removing the c′ assumption), which weakens the advertised generality but does not affect the central asymptotic match for the stated class.","tokens_in":12247,"tokens_out":25094,"duration_ms":247416,"concrete_test":"Analytically verify that the Markov Jeffreys mixture estimator of Eq. (7) satisfies a deterministic pointwise bound: for every ergodic Q and every sample path x_{0:t}, Σ_{i=1}^t log( Q(x_i|x_{i−1}) / \\hat{Q}_{J,i}(x_i|x_{i−1}) ) ≤ (m−1)m/2 log(t/2π) + O(1). If the redundancy bound in [9] is instead only an expected or high-probability bound, the domination τ ≤ τ* in the proof of Theorem 2 is invalid. Concretely: re-derive Theorem 2 with a formally defined Markov regret in Definition 2 and check that log L*_t − log L_t ≤ r_t holds for all t and all sample paths; if a counterexample sequence can be found where regret exceeds C log t, the theorem's bound collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 2's expected stopping time bound that matches SPRT. The proof's key step is the pathwise domination τ ≤ τ*, where τ* := inf{t : log L*_t ≥ log(1/α) + r_t} and L* is the oracle likelihood ratio. This requires r_t to be a deterministic pointwise upper bound on log L*_t − log L_t for every sample path and every t. However, Definition 2 defines regret only for i.i.d. distributions q ∈ Δ^{m−1}; no Markov analogue is stated. The Markov estimators in §III-D (Jeffreys mixture, Eq. 7) are asserted to have regret O((m−1)m/2 log(t/2π)), but the paper does not prove this holds pointwise and uniformly over all ergodic alternatives with max_{i,j} Q(j|i)/P(j|i) ≤ c′. If the bound from [9] is only in expectation or with high probability, the inequality τ ≤ τ* fails for individual paths and the E[τ] bound does not follow. The proof also contains typos—τ* is defined as a set rather than an infimum, and the overshoot term is written as E[log L*τ − log L_{τ*−1}] instead of E[log L*_{τ*} − log L*_{τ*−1}]—but these are fixable. The bounded-likelihood condition c′ < ∞ is used to control the overshoot and the drift constant in the Markov Wald identity (Eq. 5); Remark 4 claims this assumption can be removed but provides no proof, so the advertised 'no assumption on the alternative' is not delivered by the stated theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies one-sided sequential hypothesis testing for finite-state Markov chains: given a known null transition matrix P, decide whether a stream X1, X2, ... is generated by P or by some unknown alternative Q. The proposed Algorithm 1 constructs an empirical likelihood ratio L_t using a causal estimator \\hat{Q}_t and stops when L_t ≥ 1/α. The type-1 error bound follows from the nonnegative martingale property of L_t under H0 and Ville's inequality. The central performance claim (Theorem 2) is that, whenever the estimator has worst-case regret r_t = O(log t), the expected stopping time under an ergodic alternative Q satisfies E[τ] = O( log(1/(α D_M(Q||P))) / D_M(Q||P) ), asymptotically matching the SPRT that knows Q. The paper discusses the Jeffreys mixture estimator of Takeuchi and Barron for Markov chains and reports simulations comparing the sequential test with the fixed-length test of Wolfer and Kontorovich.","tokens_in":12608,"tokens_out":3946,"duration_ms":41123,"significance":"The proposed test is conceptually appealing: it decouples the stopping rule from the choice of estimator and would give a fully adaptive, composite one-sided test with oracle-SPRT performance. The type-1 error analysis via Ville's inequality is clean and does not depend on the estimator beyond producing valid conditional distributions. The paper also provides a useful discussion of why the Markov setting is harder than the i.i.d. case and an interesting comparison with fixed-length identity testing. If the expected-stopping-time result can be made rigorous, the paper would be a valuable contribution to sequential analysis and anomaly detection. However, the current manuscript does not yet supply a complete proof of the headline bound, because the Markov regret assumption is not formally defined and the key pathwise domination step is not justified.","major_comments":[{"comment":"Definition 2 defines the cumulative pointwise worst-case regret only for i.i.d. distributions q ∈ Δ^{m−1}. Theorem 2, however, invokes an analogous regret guarantee for Markov estimators {\\hat{Q}_t} without formally defining the Markov version or stating over which class of alternatives the supremum is taken. Without a deterministic, pathwise Markov regret bound—i.e., a pointwise inequality of the form log L*_t − log L_t ≤ r_t holding for every sample path and every t—the inequality τ ≤ τ* in §III-C does not follow from the stated assumptions. The paper needs to define the Markov regret precisely and either prove the O(log t) pointwise bound for the Jeffreys mixture estimator or cite a theorem in [9] that supplies it.","section":"Definition 2, §III-B and §III-C"},{"comment":"The displayed derivation leading to Eq. (4) contains a non-sequitur that is load-bearing for the expected stopping time bound. The proof defines τ* via an oracle statistic L*_t, then writes \"E[log L_{τ*}] ≤ log 1/α + E[log τ*] + C\". This mixes L and L*: the oracle stopping time controls log L*_{τ*}, not log L_{τ*}. Furthermore, the overshoot term is written as E[log L*_τ − log L_{τ*−1}], which should be E[log L*_{τ*} − log L*_{τ*−1}]. The intended inequality is likely E[log L*_{τ*}] ≤ log(1/α) + E[r_{τ*}] + O(1), with r_t = O(log t) converted to E[log τ*] via Jensen; this needs to be written out correctly, and the uniform bound on the overshoot needs a proof rather than an assertion.","section":"§III-C, Eq. (4)"},{"comment":"Remark 4 states that the bounded-likelihood assumption max_{i,j} Q(j|i)/P(j|i) ≤ c' < ∞ can be removed with \"a slightly more involved argument\", but no proof or reference is given. Since the stated Theorem 2 uses c' to bound the per-step log-likelihood increments and to apply the Markov Wald identity, the advertised claim in the Introduction that no assumption is made on the alternative is not supported by the theorem as written. The authors should either prove the c' < ∞ case rigorously with a finite overshoot argument, or temper the claims in the abstract and introduction to reflect the condition actually used.","section":"Remark 4, §III-C"},{"comment":"The paper asserts that the Jeffreys mixture estimator for Markov chains attains regret O((m−1)m/2 log(t/2π)) and cites [9], but does not specify whether the cited result is pointwise (pathwise) or in expectation and does not give a theorem number. This matters because the proof of Theorem 2 requires a pointwise deterministic regret bound for every sample path, not merely an averaged or high-probability bound. The authors should state the precise regularity and uniformity of the regret bound obtained from [9] or prove the needed pathwise bound; otherwise the substitution of r_t in the oracle-stopping-time argument is unjustified.","section":"§III-D, Jeffreys mixture claim"}],"minor_comments":[{"comment":"There is a typo in \"Our alogorithm and test work with any method...\" — \"alogorithm\" should be \"algorithm\".","section":"§III-A"},{"comment":"In the definition of τ*, the right-hand side is written as a set (\"≤ {t ≥ 1 : ... } =: τ*\"), but τ* should be defined as the infimum of that set, i.e., τ* := inf{t ≥ 1 : log L*_t ≥ log(1/α) + r_t}.","section":"§III-C, proof of Theorem 2"},{"comment":"In the display verifying the martingale property, the summation index is misprinted as \"∑_{i=j}\"; it should be \"∑_{j∈[m]}\".","section":"§III-C, martingale check"},{"comment":"The caption of Fig. 2 refers to \"Problem 8\", which is likely Eq. (8); please make the cross-reference explicit and consistent.","section":"Eq. (8) and Fig. 2"},{"comment":"The notation \"r_t((\\hat{q}_i)^t_{i=1})\" is awkward: the subscript t on the left is redundant, and the definition as a maximum over trajectories and a supremum over q is not clearly separated. A cleaner notation would help the reader distinguish the pointwise regret from its worst-case bound.","section":"Definition 2"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an interesting and timely problem, and the high-level idea is sound, but the proof of the central expected-stopping-time result needs substantial repair: a formal definition of Markov pathwise regret, a correct derivation in Eq. (4), and a decision on whether the bounded-likelihood condition is actually needed. The authors should also verify that the cited regret bound from Takeuchi and Barron is indeed pointwise; if it is only in expectation, the stated theorem is not proven by the current argument. I would not reject, because these issues appear fixable within the manuscript's scope, but the revision needs to be more than cosmetic."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper does something genuinely new: it constructs a one-sided sequential SPRT-type test for Markov chains against a composite alternative, and shows that any estimator with O(log t) regret suffices to match the expected stopping time of an oracle SPRT that knows the alternative. The type-1 error bound via Ville's inequality is clean and correct, and the regret-based adaptivity idea is a solid extension of the i.i.d. universal coding approach to Markovian data. The authors also honestly benchmark against the most relevant fixed-length identity test.\n\nThe main theorem, Theorem 2, is plausible but the proof as written has real rough edges. First, Definition 2 formally defines regret only for i.i.d. distributions, yet the theorem and the estimator discussion need a pointwise Markov analogue. The Takeuchi-Barron bound is cited, but the connection between that bound and the pathwise domination step is not stated cleanly. Second, the proof of the expected stopping time contains typos: τ* is defined as a set instead of an infimum, and the overshoot term in equation (4) mixes τ and τ* and is not properly bounded. The bounded likelihood ratio assumption c' < ∞ is used to control the overshoot, but that control is never written down. Third, Remark 4 says the bounded likelihood assumption can be removed but gives no argument, so the stated theorem does not deliver the 'no assumption on the alternative' advertised in the introduction. These are fixable in revision, but they are exactly the steps a referee needs to verify the main claim.\n\nWhat is not a problem: the type-1 error result is on solid ground; the novelty claim against the cited literature checks out; and there is no circularity or self-citation issue. The simulations illustrate the adaptivity point, though no code is provided, which is a minor reproducibility concern.\n\nThis paper deserves serious refereeing. The central idea is right and the result is useful for anomaly detection and monitoring. My recommendation: send it out, and ask the authors to tighten the definition of Markov regret, fix the stopping-time proof, and either prove or remove Remark 4.","headline":"A genuinely adaptive one-sided SPRT for Markov chains with a regret-based estimator; the proof needs cleanup but the idea and type-1 bound are solid.","tokens_in":13075,"tokens_out":5478,"would_cite":true,"duration_ms":54332,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L10","62M02","60J10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a sequential test for Markov chains using any estimator with logarithmic regret matches the expected stopping time of the SPRT that already knows the alternative.","keywords":["sequential hypothesis testing","Markov chains","SPRT","composite alternative","anomaly detection","regret bound","Jeffreys mixture","martingale"],"falsifier":"For a fixed ergodic alternative $Q$ and null $P$, run Algorithm 1 with a Jeffreys-mixture estimator for decreasing $\\alpha$; if the empirical average stopping time grows faster than $\\log(1/\\alpha)/D_M(Q\\|P)$, for instance if $E[\\tau] D_M(Q\\|P)/\\log(1/\\alpha)$ diverges, then the claimed SPRT-matching bound is false.","tokens_in":59,"feed_emoji":"⏱️","tokens_out":15493,"duration_ms":223405,"temperature":0.7,"pith_summary":"This paper asks how quickly a stream of observations from a Markov chain can be tested against a known transition matrix $P$ as the null hypothesis, when the alternative is any other ergodic chain. The authors propose a one-sided sequential test: keep sampling as long as the running likelihood ratio stays below $1/\\alpha$, and reject $P$ the first time it crosses. Because the alternative is not known, the likelihood ratio is built from a causal estimate of the data-generating chain; the test's stopping time then depends on a regret bound for that estimator. The central result is that any estimator with cumulative log-loss regret $O(\\log t)$ makes the expected stopping time under an alternative $Q$ scale as $\\log(1/(\\alpha D_M(Q\\|P)))/D_M(Q\\|P)$, matching the sample size of an oracle sequential probability ratio test (SPRT) that knows $Q$. This means anomaly detection and similar monitoring tasks can adapt to the unknown difficulty of the deviation, without knowing the deviation in advance.","feed_headline":"Adaptive test rivals oracle speed without knowing the alternative","feed_subtitle":"The rule's sample count tracks the unknown difficulty, matching the test that knows the alternative.","key_machinery":"The engine of the argument is the empirical likelihood-ratio process. Instead of an unknown alternative $Q$, the test uses a causal estimator $\\hat{Q}_t$ built from the previous samples and updates $L_t = L_{t-1} \\hat{Q}_t(X_t|X_{t-1})/P(X_t|X_{t-1})$. Under $H_0$ this quotient has conditional expectation 1, making $L_t$ a non-negative martingale, which immediately controls the false-rejection probability through Ville's inequality. Under $H_1$, the quality of $\\hat{Q}_t$ is measured by its worst-case pointwise cumulative log-loss regret $r_t = \\max \\sum_i (\\log(1/\\hat{q}_i(X_i)) - \\log(1/q(X_i)))$; when $r_t = O(\\log t)$, the test statistic is close enough to the oracle statistic $\\prod Q(X_i|X_{i-1})/P(X_i|X_{i-1})$ that the stopping time is controlled by a Markov-chain version of Wald's identity. That identity turns $E[\\log L^*_\\tau]$ into $D_M(Q\\|P) E[\\tau]$ plus a bounded drift term, producing the SPRT-matching bound. The reachability problem of rarely visited states is handled by estimators such as the Jeffreys mixture over ergodic Markov chains rather than row-by-row add-constant estimates.","core_discovery":"On its own terms, the paper establishes that a composite, one-sided sequential test can asymptotically match the simple-hypothesis SPRT. Algorithm 1 forms $L_t = \\prod_{i=1}^t \\hat{Q}_i(X_i|X_{i-1})/P(X_i|X_{i-1})$ and stops at $\\tau = \\inf\\{t: L_t \\ge 1/\\alpha\\}$, declaring $H_1$. Under $H_0$, $L_t$ is a non-negative martingale starting at 1, so Ville's inequality gives type-1 error at most $\\alpha$ for every valid estimator. If the estimator's worst-case pointwise cumulative log-loss regret is $O(\\log t)$, then for an ergodic alternative $Q$ whose likelihood ratios $Q(j|i)/P(j|i)$ are bounded by a finite constant, $E[\\tau] = O(\\log(1/(\\alpha D_M(Q\\|P)))/D_M(Q\\|P))$, where $D_M$ is the stationary-averaged KL divergence. The bound matches the expected sample size of the SPRT that knows $Q$, so the test adapts to the hardness of the alternative with no prior information.","pith_inferences":["We infer that replacing the $O(\\log t)$ regret condition with a super-logarithmic one would produce a correspondingly slower expected stopping time, so the estimator's regret is the natural tuning knob for the speed-robustness trade-off in practice.","We infer that the same statistic can be applied when the null itself is estimated from a finite warm-up sample, but then $\\alpha$ should be reinterpreted as conditional on that estimate; a formal treatment of this two-stage setting is not in the paper.","We infer a concrete testable extension: run the algorithm with a Bayesian context-tree estimator on data with variable-length memory; if such an estimator has $O(\\log t)$ regret, the SPRT-matching bound should transfer directly."],"forward_implications":["Any valid causal estimator gives type-1 error at most $\\alpha$, so the false-rejection guarantee is robust to the estimator choice.","With an $O(\\log t)$ regret estimator, the expected stopping time under an unknown alternative matches, up to constants, the SPRT that is told the alternative, so no prior knowledge of the deviation is needed.","The test is one-sided: under the null it is allowed to run indefinitely, which is the desired behavior for continuous monitoring and anomaly detection.","The bound is expressed through the stationary-averaged KL divergence $D_M(Q\\|P)$, so harder-to-detect alternatives automatically require more samples, while easy alternatives stop quickly.","Known estimators with the required regret guarantee exist in both the i.i.d. case and the Markov case, so the theorem is not vacuous."],"supporting_citations":[{"why":"Supplies the sequential probability ratio test whose threshold rule and likelihood-ratio structure the algorithm generalizes.","marker":"[3]"},{"why":"Supplies the Markov-chain predecessor of SPRT for dependent observations, which motivates the test's construction.","marker":"[2]"},{"why":"Provides the Jeffreys mixture estimator for Markov sources with cumulative regret $O(\\log t)$, showing the estimator condition in Theorem 2 is satisfiable.","marker":"[9]"},{"why":"Establishes the Markov-chain version of Wald's identity used to convert expected log-likelihood at the stopping time into $D_M(Q\\|P)$ times expected stopping time.","marker":"[14]"},{"why":"Introduces the stationary-averaged KL divergence $D_M$ in error exponents for Markov hypothesis testing, the quantity measuring alternative hardness.","marker":"[1]"},{"why":"Gives the Krichevsky-Trofimov estimator whose $O(\\log t)$ regret supplies the i.i.d. analogue of the estimator condition.","marker":"[16]"}],"fun_headline_variants":["Markov chain test matches oracle without knowing alternative","Sequential Markov chain test adapts to unknown alternatives","SPRT variant for Markov chains rivals known-distribution speed","Adaptive Markov chain testing hits oracle sample sizes","One-sided Markov chain test learns difficulty on the fly"],"cache_read_input_tokens":15232,"weakest_assumption_plain":"The load-bearing premise is that the deployed estimator has worst-case cumulative log-loss regret $O(\\log t)$ uniformly over sample paths and chain parameters, and that the alternative chain is ergodic with finite likelihood ratios $Q(j|i)/P(j|i)$; if any of these fails, the proof that the test keeps pace with the known-alternative SPRT no longer goes through.","fun_headline_variants_meta":{"raw":{"variants":["Markov chain test matches oracle without knowing alternative","Sequential Markov chain test adapts to unknown alternatives","SPRT variant for Markov chains rivals known-distribution speed","Adaptive Markov chain testing hits oracle sample sizes","One-sided Markov chain test learns difficulty on the fly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000213,"raw_usage":{"total_tokens":1463,"prompt_tokens":1029,"completion_tokens":434,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":645,"completion_tokens_details":{"reasoning_tokens":359}},"tokens_in":645,"tokens_out":434,"duration_ms":4930,"temperature":1.0,"reasoning_tokens":359,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T16:23:34.675603+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed ergodic alternative $Q$ and null $P$, run Algorithm 1 with a Jeffreys-mixture estimator for decreasing $\\alpha$; if the empirical average stopping time grows faster than $\\log(1/\\alpha)/D_M(Q\\|P)$, for instance if $E[\\tau] D_M(Q\\|P)/\\log(1/\\alpha)$ diverges, then the claimed SPRT-matching bound is false.","supporting_citations":[{"cited_title":"Sequential Analysis of Dependent Obse rvations. I,","cited_arxiv_id":null,"evidence_quote":"Supplies the Markov-chain predecessor of SPRT for dependent observations, which motivates the test's construction."},{"cited_title":"Properties o f Jeffreys mixture for Markov sources,","cited_arxiv_id":null,"evidence_quote":"Provides the Jeffreys mixture estimator for Markov sources with cumulative regret $O(\\log t)$, showing the estimator condition in Theorem 2 is satisfiable."},{"cited_title":"Extension of Wald’s first lemma to Ma rkov pro- cesses,","cited_arxiv_id":null,"evidence_quote":"Establishes the Markov-chain version of Wald's identity used to convert expected log-likelihood at the stopping time into $D_M(Q\\|P)$ times expected stopping time."},{"cited_title":"Large deviations, hypotheses testing, a nd source coding for finite Markov chains,","cited_arxiv_id":null,"evidence_quote":"Introduces the stationary-averaged KL divergence $D_M$ in error exponents for Markov hypothesis testing, the quantity measuring alternative hardness."},{"cited_title":"The performance of unive rsal encod- ing,","cited_arxiv_id":null,"evidence_quote":"Gives the Krichevsky-Trofimov estimator whose $O(\\log t)$ regret supplies the i.i.d. analogue of the estimator condition."}],"review_version":1}