Mixing time for an epidemic model on graphs with external sources of infection

Wasiur R. KhudaBukhsh; Yangrui Xiang

arxiv: 2501.07738 · v2 · pith:NUZQF3D7new · submitted 2025-01-13 · 🧮 math.PR · math-ph· math.MP· math.ST· q-bio.PE· stat.TH

Mixing time for an epidemic model on graphs with external sources of infection

Wasiur R. KhudaBukhsh , Yangrui Xiang This is my paper

Pith reviewed 2026-05-23 04:56 UTC · model grok-4.3

classification 🧮 math.PR math-phmath.MPmath.STq-bio.PEstat.TH

keywords mixing timenoisy SIS modelepidemic processesrandom graphsMarkov chainsErdos-Renyi graphsGalton-Watson trees

0 comments

The pith

The mixing time of the noisy SIS epidemic model on graphs is Theta(n log n) under suitable parameter assumptions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the mixing time of a Susceptible-Infected-Susceptible epidemic process on graphs that includes external sources of infection, referred to as the noisy SIS model. It establishes that this mixing time is of order Theta(n log n) with respect to the number of vertices n when the infection, recovery, and external infection rates meet certain conditions. The analysis extends to random graph families including Erdos-Renyi graphs, random regular multigraphs, and Galton-Watson trees by first identifying high-probability structural features of these graphs and then conditioning on typical realizations to obtain the same Theta(n log n) bound with high probability. A reader would care because the mixing time controls how quickly the epidemic state distribution approaches its long-run equilibrium, directly affecting forecasts of infection levels in large populations.

Core claim

Under suitable assumptions on the parameters of the dynamics, the mixing time of the noisy SIS model is of the order Theta(n log n) with respect to the number of vertices n. By identifying high-probability structural properties of these graphs and conditioning on typical realizations, the mixing time remains of order Theta(n log n) with high probability on random graph families including Erdos-Renyi graphs, random regular multigraphs, and Galton-Watson trees.

What carries the argument

The noisy SIS model, whose mixing-time bound is obtained by conditioning on high-probability structural properties of the underlying graph.

If this is right

The mixing time of the noisy SIS model is Theta(n log n) on graphs meeting the parameter assumptions.
The same Theta(n log n) bound holds with high probability for Erdos-Renyi graphs after conditioning on typical realizations.
The same Theta(n log n) bound holds with high probability for random regular multigraphs after conditioning on typical realizations.
The same Theta(n log n) bound holds with high probability for Galton-Watson trees after conditioning on typical realizations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The conditioning technique on structural properties might extend the result to other random graph models not studied here.
If the external infection rate grows with n, the mixing time order could change.
Numerical simulation of the chain on moderate-sized graphs could check whether the n log n scaling appears in practice.

Load-bearing premise

The infection rate, recovery rate, and external infection rate satisfy suitable assumptions that make the Theta(n log n) mixing-time bound hold.

What would settle it

Finding a graph family satisfying the parameter assumptions where the mixing time scales as n to a power other than 1 or as log n would falsify the central claim.

read the original abstract

We study the mixing time of a Susceptible--Infected--Susceptible (SIS) model on graphs with external sources of infection, which we refer to as the noisy SIS model. Under suitable assumptions on the parameters of the dynamics, we show that the mixing time is of the order $\Theta(n\log n)$ with respect to the number of vertices $n$. We further investigate the model on random graph families, including Erd{\"o}s--R{\'e}nyi graphs, random regular multigraphs, and Galton--Watson trees. By identifying high-probability structural properties of these graphs and conditioning on typical realizations, we prove that the mixing time remains of order $\Theta(n\log n)$ with high probability.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper pins down Θ(n log n) mixing times for the noisy SIS model on general graphs and carries the same order over w.h.p. to ER, random regular, and Galton-Watson graphs via conditioning on typical structure.

read the letter

The main takeaway is that under explicit conditions on the infection, recovery, and external infection rates, the continuous-time noisy SIS chain mixes in Θ(n log n) steps on any graph, and the same order holds with high probability on the listed random-graph families after conditioning on their high-probability expansion or regularity properties. The conditioning step is measure-theoretically valid and does not loop back on itself. The random-graph extension is the clearest incremental contribution; the general-graph bound looks like a direct application of standard coupling or conductance arguments once the external source term is added. The stress-test note confirms the parameter assumptions are stated in the theorems and suffice for ergodicity and positive probabilities, so the central claim does not rest on hidden fitting or unjustified extrapolation. The work is incremental rather than foundational, but the execution appears careful and the random-graph handling is the right way to state the result. Minor soft spot is that the precise range of the rate assumptions is not visible from the abstract, though nothing indicates they are vacuous or only cover trivial regimes. Without the full proofs I cannot check the lower-bound argument or constant factors, but the provided information shows no internal inconsistency or missing step. This is aimed at researchers who work on mixing times for interacting particle systems or epidemic models on networks. A reader already familiar with coupling methods on graphs will find a clean, usable reference. It is coherent on its own terms and shows honest engagement with the existing mixing-time literature, so it deserves a serious referee even if the revisions are light.

Referee Report

0 major / 2 minor

Summary. The paper studies the mixing time of the noisy SIS epidemic model (Susceptible-Infected-Susceptible dynamics with external infection sources) on finite graphs. Under suitable assumptions on the infection, recovery, and external-infection rates, it claims to prove that the mixing time is Θ(n log n) in the number of vertices n. It further extends the result to three random-graph families (Erdős–Rényi, random regular multigraphs, Galton–Watson trees) by identifying high-probability structural properties (expansion, degree regularity, tree-likeness) and conditioning on typical realizations, showing that the Θ(n log n) bound continues to hold with high probability.

Significance. If the central coupling or conductance argument is correct, the result supplies a sharp, explicit mixing-time bound for a natural variant of the SIS process that incorporates external noise; this is useful for both theoretical analysis of epidemic equilibria and for algorithmic sampling on networks. The conditioning technique for random graphs is standard and cleanly executed, allowing the deterministic-graph bound to transfer to random ensembles without circularity. The manuscript therefore contributes a precise, falsifiable statement about convergence rates that can be checked against the stated parameter regime.

minor comments (2)

The introduction and abstract invoke 'suitable assumptions on the parameters' without quoting the explicit inequalities that appear in the main theorems; a one-sentence summary of the regime (e.g., infection rate bounded away from zero and external rate positive) would improve readability.
Notation for the continuous-time chain, the stationary measure, and the total-variation distance should be introduced once in a dedicated 'Notation' paragraph rather than piecemeal.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, positive assessment of its significance, and recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation relies on standard Markov chain mixing time techniques (coupling arguments under explicit parameter conditions ensuring positive transition probabilities and ergodicity) combined with conditioning on high-probability structural properties of the random graphs (expansion, degree regularity, tree-likeness). These steps are measure-theoretically valid and independent of the target mixing-time bound; no parameter is fitted to data and then renamed as a prediction, no self-citation chain is load-bearing for the central claim, and the result does not reduce to its inputs by definition. The argument is self-contained against external benchmarks such as standard coupling lemmas and random-graph concentration inequalities.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on unspecified suitable assumptions on the model parameters; no free parameters, invented entities, or additional axioms are mentioned in the abstract.

axioms (1)

domain assumption suitable assumptions on the parameters of the dynamics
Invoked in the abstract to establish the mixing-time bound for both general graphs and random-graph families.

pith-pipeline@v0.9.0 · 5667 in / 1258 out tokens · 39764 ms · 2026-05-23T04:56:49.823830+00:00 · methodology

Mixing time for an epidemic model on graphs with external sources of infection

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)