How do first-passage times behave for branching random walk on a Hamming cube?

A growing population must first produce a prescribed mutant

The paper studies when a growing population first produces a specific genotype of interest. Genotypes are sequences of length d over an alphabet of b ≥ 2 symbols, with b = 4 for RNA, so the genotype space is the Hamming cube {0, 1, …, b−1}^d, where two vertices are neighbours if they differ in exactly one coordinate. Each particle mutates at total rate one, choosing a neighbour uniformly; at a genotype with net growth rate λ, it splits at rate max(λ, 0) and dies at rate max(−λ, 0).

Selection enters because the net growth rate varies by genotype. Vertex rates are sampled independently from a fixed probability distribution and then held fixed throughout the evolution, so all particles carrying the same genotype share the same rate. This is the house-of-cards idealization of a fitness landscape: it deliberately neglects fitness correlations even between genotypes differing at a single site. Probabilities conditional on the sampled landscape are called quenched; averaging over the landscape gives the annealed law.

The quantity of interest is the first-passage time (FPT): the first time any descendant reaches the prescribed target. The distance m is the Hamming distance from the initial genotype to that target, meaning the number of coordinates in which they differ. The paper's asymptotics are uniform in m for 1 ≤ m ≤ d as d → ∞, and they are stated conditional on survival of the process.

Two questions organize the analysis. On what time scale does the target genotype first appear, and how large are the fluctuations of that first-appearance time? And can increasing mutation, while keeping the net growth rates fixed, delay its first appearance, and if so by how much? The second question is motivated by antiviral mutagenesis, where drugs such as molnupiravir increase errors during viral RNA replication to suppress viral growth, raising the concern that mutagenic treatment might also promote unwanted variants.

The reproduction law must stay below the mutation rate

The main results hold under an assumption that the reproduction law has essential supremum strictly below the deterministic mutation rate, with both the rate distribution and the mutation rate fixed as d grows. This mirrors the slow-branching regime in earlier work on the homogeneous Hamming-cube branching random walk, where the first-passage time remains of order d even for targets at bounded positive Hamming distance.

The assumption is not a technical afterthought; it is what makes the order-d time scale the relevant one. It also separates this paper from multitype branching-process studies of mutant first appearance, whose asymptotic results concern increasingly rare mutations on a fixed genotype structure, whereas here the sequence space grows while the total mutation rate stays fixed.

Reproduction and mutation events are decoupled. Mutation changes a particle's genotype without branching, while a split produces two particles with the parent's genotype. For b = 4 the mutation walk coincides with the classic Jukes–Cantor model. Keeping these two mechanisms separate is what allows the paper to ask how changing the mutation rate alone, with the growth-rate law held fixed, moves the first-passage time.

Fluctuations stay bounded around a deterministic center

The paper's central object is a deterministic center, written θ̂_{d,m}, which depends on the dimension d and the origin-target distance m but not on the sampled environment. Theorem 2.1 shows there is a deterministic constant C_ctr < ∞ such that, for all sufficiently large d, the supremum over 1 ≤ m ≤ d of |θ̂_{d,m} − d·u*(m/d)| is at most C_ctr log d. In other words, the center is pinned down to within a logarithmic correction, uniformly across all distances.

Theorem 2.2 then shows that this same center controls the actual random first-passage time. Uniformly over 1 ≤ m ≤ d, the quenched first-passage time equals θ̂_{d,m} plus a term that is tight in environment probability, and the same center gives uniform annealed tightness conditional on survival. Formally, for every ε > 0, the probability over environments that the conditional quenched law puts more than A units of mass outside a window of width A around θ̂_{d,m} vanishes as A grows and then d grows.

The distinction between quenched and annealed matters here. Quenched tightness says that for a typical sampled landscape, the fluctuations of the first-passage time under the law conditional on that landscape and on survival remain on a bounded time scale. Annealed tightness says the same center works after averaging over the landscape. Both are stated conditional on survival, and when the quenched survival probability at a vertex is zero the conditional law is defined by convention as the unconditioned law.

A notable feature is that the center is deterministic rather than environment-dependent. In one-dimensional static random-environment models, the medium displaces the front on the diffusive √n scale about its deterministic linear order, and an environment-dependent center is needed to recover order-one tightness. On the Hamming cube, the environment-dependent location of the conditional law fluctuates only on the order-one scale about a deterministic center.

Sparse distances give a two-term expansion in d and m

In the sparse-distance regime m = o(d), the paper derives a first-order expansion of the deterministic center. If m_d is a deterministic integer sequence with 1 ≤ m_d ≤ d and m_d = o(d), then θ̂_{d,m_d} = u*(0)d + r_+ m_d + o(m_d) + O(log d). The leading term is linear in the sequence length d, and the correction is linear in the Hamming distance m_d with coefficient r_+.

The coefficient r_+ is defined as the minimum over a set K* of log H(κ)/κ, where K* collects the clock components κ of the maximizing saddles at (0, u*(0)). This minimum arises because the sparse-distance calculation must allow several maximizing saddles rather than assuming a unique one; comparing their first-order responses produces r_+. The paper also records the local behaviour u*(θ) = u*(0) + r_+θ + o(θ) as θ ↓ 0.

The expansion is a statement about the deterministic center, not about a single realized first-passage time. It says that at sparse distances the order-d coefficient is u*(0) and the order-m coefficient is r_+, up to a logarithmic correction in d and a lower-order term in m. Readers comparing distances should keep the two scales separate: d sets the leading time scale, while m enters only through the sparse-regime correction.

An independent-visit proxy makes the static model tractable

The proof strategy rests on comparing the static-environment model with an independent-visit variant. In the static model, a genotype's reproduction rate is sampled once and reused on every visit. In the independent-visit variant, revisits resample the environment, which makes the model technically tractable while preserving the first-moment structure the authors need.

The comparison is quantitative. By counting revisits of the paths and their holding times, the authors obtain a conditional-mean comparison between the static first moment and the independent-visit first moment, together with bounds on the fluctuations of the static first moment about that mean. This is what allows conclusions proved for the proxy to transfer back to the static environment that the biological model actually describes.

Locating the deterministic center requires local limit estimates on discrete bridges, which identify the relevant convolution structures with a sum of independent random variables after a proper tilting. This yields log K̂_{d,m}(t) = d·F(m/d, t/d) + O(log d) near t = d·u*(m/d). Because the exponent increases at a rate bounded away from zero there, this locates θ̂_{d,m} to within O(log d).

Tightness then proceeds in three steps: compare the static and independent-visit models; obtain a positive hitting probability via a fractional Paley–Zygmund inequality, which requires an upper bound on the (1+q)-moment of the target count for a small fixed q in (0,1); and show that the success probability concentrates at its conditional environmental mean by a resampling argument. The concentration step resamples the rate at a single vertex, kills particles entering it, and controls the resulting difference using many-to-one path expansions and a martingale resampling inequality.

More mutation delays first passage, and spread growth speeds it up

The paper's comparative statics separate two parameters that readers might otherwise conflate. For the mutation rate, Corollary 2.4 fixes the branching rate law and considers two mutation rates ϱ₁ < ϱ₂ in a compact interval satisfying the supercritical condition ϱ > λ_+ and ϱ ∫ P(dλ)/(ϱ − λ) > 1. In the sparse-distance regime, the larger mutation rate has a larger leading passage-time coefficient at order d: u*^{[ϱ₂]}(θ)/ϱ₂ > u*^{[ϱ₁]}(θ)/ϱ₁ for 0 ≤ θ ≤ ε. So increasing mutation delays first passage by order d, with each process conditioned on its own survival.

For the reproduction law, a coupling argument shows that stochastically larger net growth-rate laws give stochastically smaller unconditioned first-passage times under the annealed law, so that direction is not the interesting one. The nontrivial statement is with respect to convex order. If P₁ ≤_cx P₂, meaning the two laws have the same finite mean and P₂ integrates every convex function at least as much as P₁, then θ̂_{2,d,m} ≤ θ̂_{1,d,m} for all 1 ≤ m ≤ d and u*²(θ) ≤ u*¹(θ) for 0 ≤ θ ≤ 1. If P₁ ≠ P₂ the root inequality is strict, so the leading passage-time coefficient is strictly smaller under the more spread-out law.

The two results answer different questions and should not be merged. The mutation-rate corollary is about the sparse regime and about the leading coefficient at order d in physical units, obtained after rescaling because the main theorems assume unit mutation rate. The convex-order corollary is about a mean-preserving spread of the growth-rate law and holds across all distances 1 ≤ m ≤ d, with strictness only when the two laws differ.

Nonlinear saturation delays level times by only a bounded amount

As a further application, the paper connects the branching process to the Fisher–KPP equation on the Hamming cube, which combines mutation with logistic growth at rate Λ_x and saturation through the factor (1 − w). Its linearization at zero is the parabolic Anderson equation, whose solution is the quenched first moment of the branching process. The branching representation gives w^ω ≤ v^ω in every environment, where w^ω is the nonlinear solution and v^ω its linearization.

For a level 0 < α < 1, define T_α[f](x) as the first time the solution f at vertex x reaches α. Under the additional assumption that the growth-rate law is supported on [0, λ_+], so there are no deaths, Corollary 2.6 shows that the nonlinear solution and its linearization reach any fixed level at times differing by only O_{P_env}(1), uniformly over prescribed targets at all Hamming distances. It also shows that the event where the nonlinear level time exceeds the linear one by more than A at some distance has vanishing environment probability.

The point is that the nonlinear delay remains bounded in probability, not merely negligible on the order-d scale. This contrasts with one-dimensional random media, where the known bound on the distance between nonlinear and linear spatial fronts is O(log t). The difference in setting matters: here the comparison is between times to reach a fixed level at prescribed vertices as d → ∞, rather than between spatial front positions as t → ∞.

The deterministic center is the paper's operative quantity

The most decision-relevant object in this paper is not a single simulated first-passage time but the deterministic center θ̂_{d,m} and its two-term sparse-distance expansion u*(0)d + r_+ m + o(m) + O(log d). That expansion is what lets a reader separate the contribution of sequence length from the contribution of origin-target distance: d sets the leading order, and m enters through the coefficient r_+ only in the sparse regime m = o(d).

The comparative statics then become a way to read parameter changes off that center. Holding the growth-rate law fixed and raising the mutation rate within the supercritical interval increases the leading passage-time coefficient at order d in the sparse regime, so mutagenic pressure delays first appearance rather than accelerating it. Holding the mutation walk fixed and replacing the growth-rate law by a mean-preserving spread in convex order decreases the center at every distance 1 ≤ m ≤ d, with strictness when the laws differ.

Both statements are conditional on survival and are asymptotic as d → ∞, with the growth-rate distribution and mutation rate fixed. The tightness results are stated in environment probability and in the annealed law, not pathwise for every landscape, and the Fisher–KPP corollary additionally assumes no deaths. Within those boundaries, the paper's priority is clear: the deterministic center, not the environment-dependent location, is the quantity that organizes first-passage behaviour on the Hamming cube.

Where the asymptotics apply and where they stop

The results are asymptotic in the sequence length d, with the reproduction law and the mutation rate held fixed as d grows. The essential supremum of the reproduction law must lie strictly below the mutation rate, which places the model in the slow-branching regime where first-passage times remain of order d. The statements are conditional on survival, and the quenched tightness is a statement in environment probability rather than a pathwise guarantee for every sampled landscape.

The sparse-distance expansion applies only when m = o(d); it is not claimed for distances comparable to d, where only the uniform O(log d) bound on the center is available. The mutation-rate comparative static is stated for a compact interval of rates satisfying the supercritical condition and for the sparse regime, and it concerns the leading coefficient at order d after rescaling to physical units. The convex-order result requires the two rate laws to share the same finite mean.

The Fisher–KPP level-time corollary adds the assumption that the growth-rate law is supported on [0, λ_+], excluding deaths. The model itself is an idealized house-of-cards landscape that neglects fitness correlations between neighbouring genotypes, so the results describe a tractable approximation rather than a calibrated description of any particular viral fitness landscape.

Sources used in this answer