Branching bound for contact-process survival 2026-10-14
With recovery rate one, the number of infected sites in a nearest-neighbour contact process has death rate equal to its size and birth rate at most times its size. It is dominated by a linear birth-death branching process with these per-particle rates. In particular, from one infection its expected size is at most , so its survival probability is zero when . This proves the displayed lower bound on the critical rate.
Galton-Watson process Created 2026-09-24 Updated 2026-10-13
A Galton-Watson process is a branching process that counts individuals by generation. Start with one ancestor, , and let all offspring counts be independent and identically distributed random variables taking nonnegative integer values with a common offspring distribution. ThenThe empty sum is zero: zero is an absorbing state, so once a generation is empty every later generation is empty. The same offspring distribution applies to every individual in every generation. [ref]
https://ocw.mit.edu/courses/18-445-introduction-to-stochastic-processes-spring-2015/27aaeb9eb9a9cecce93d9ad74413ddf5_MIT18_445S15_lecture19.pdf. Hao Wu, MIT 18.445, Lecture 19, slides 3–4
For a concrete offspring distribution, take , , , and for . An individual has no children with probability , one with probability , and two with probability . The offspring expected value is . A possible sequence of generation sizes is : two children need not lead to a permanently growing family.
The probability generating function gives the exact generation probability distributions through branching-process generating-function iteration. With and , the second generation hasThus and . The figure shows full generation probability mass functions, computed by polynomial function composition, through generation six; no simulated frequencies are used.
The contrast is striking: the expected generation size in a Galton-Watson process grows as , while the branching extinction probability is . By generation six, although . Larger surviving families carry the rising expected value; that mean is an average over possible families, not a forecast of one family's path. The Galton-Watson extinction fixed point turns an unbounded number of future generations into a single equation for this probability.
The historical question was the disappearance of surnames passed through male descendants. In Watson and Galton, On the Probability of the Extinction of Families, pages 139–140, Francis Galton formulates a constant-law model counting sons who reach adulthood, and Watson computes later generation probability distributions by composing generating functions. Those are assumptions of their model, rather than a claim that actual human reproduction follows this offspring distribution.
Mean-field percolation exponents 2026-10-07
The mean-field predictions model large clusters by branching processes. Rigorous results apply in specified high-dimensional or sufficiently spread-out regimes, using tools such as lace expansion and the percolation triangle condition. The full list involves different observables; the triangle condition alone should not be presented as proving every spatial exponent. With these exponents , whereas , explaining the failure of naive hyperscaling relation above six.
“Failed to take off” needs an operational definition; the two separated groups in the histograms suggest a low peak or an early end. For example, classify a run as a failure if its peak is below ten infected individuals, or alternatively if its extinction time is below ten days:
failed_by_peak = stats[:,0] < 10
failed_by_time = stats[:,1] < 10
print(failed_by_peak.mean(), failed_by_time.mean())Both definitions give in this run. Here they also classify the same 255 realizations, although agreement is not guaranteed for other simulations or cutoffs. These are empirical failure fractions for the stated rules, not exact model constants.
The early branching process approximation provides a useful check: while susceptible depletion is negligible, gives eventual extinction probability about from one initial infection. Allowing for the initial susceptible fraction gives a rate ratio ; both approximations are compatible with this simulation, but neither defines the finite-population cutoff exactly.
Past exam of the mathematics course of the University of Cambridge 2002 ia Paper 2 12F a Solution Created 2026-09-24 Updated 2026-10-14
A branching process models reproduction through successive generations. In the Galton-Watson process used here, every individual independently produces a nonnegative integer number of offspring with a common offspring distribution; these reproduction counts are independent across individuals and generations. If is the generation size, thenwhere the have that distribution and the empty sum is zero. Thus zero is absorbing: once a generation is empty, every subsequent generation is empty.
Past exam of the mathematics course of the University of Cambridge 2002 ia Paper 2 12F c Solution Created 2026-09-24 Updated 2026-10-14
The binomial series givesThus and, for ,with the factors after omitted for . The signs follow from . As , the series has nonnegative terms and its sum increases to , so monotone convergence gives . These are therefore genuine probabilities on the nonnegative integers, proving that is a probability generating function. Its expected value is infinite, since ; finiteness of the mean is not required for this branching process.
Write . The composition formula gives , with . Consequently , and summing the geometric series yields the explicit generation generating functionThis is the fractional-power offspring generating function and its iterates.
Past exam of the mathematics course of the University of Cambridge 2002 ia Paper 2 12F d Solution Created 2026-09-24 Updated 2026-10-14
Evaluation of the probability generating function at zero selects the constant coefficient, soTo identify this limit with ultimate extinction, let . The absorbing-zero property of the branching process gives . Ultimate extinction means that some finite generation is empty, namely . Continuity of probability on increasing events therefore givesThis set argument is essential: it uses absorption, rather than inferring extinction merely from a numerical limit of generation probabilities.
Past exam of the mathematics course of the University of Cambridge 2002 iii Paper 28 2 Solution Created 2026-10-03 Updated 2026-10-14
Use the contact process convention that each infected vertex recovers at rate one and sends infection arrows to each neighbour at rate . Starting from a finite set, the process stays finite and is nonexplosive: its total birth rate is at most times its current size, so a linear-rate branching process dominates the number of births. The bound involving presupposes the branching-tree case .
For a nonempty finite infected set , put , let count its internal edges, and let count edges with exactly one endpoint in . Each such boundary edge contributes infection rate , even when several lead to the same vacant vertex. Since the induced graph is a forest, , and the edge boundary of a finite forest in a regular tree givesA recovery multiplies by , while an infection multiplies it by . Therefore its infinitesimal generator isSubstituting the boundary lower bound givesAt the absorbing empty set the generator is zero, rather than this nonempty-set expression. If , the generator is nonpositive in every state. Both and its generator are bounded, since is bounded and . Applying Dynkin's formula over successive time intervals with the Markov property proves the exponential cardinality supermartingale for the contact process on a tree. In particular,If is the extinction time, , so . Choosing proves global survival whenever . Obtaining a strict improvement of the threshold requires an additional comparison.
Here is a two-vertex branching comparison for contact-process survival. Delete one edge incident to a starting vertex and retain its forward rooted subtree, so every vertex has children. Partition it into cells as follows: pair each cell root with one distinguished child ; the other children of and all children of become roots of child cells, and repeat recursively. Each cell thus has child cells.
Suppress arrows back from a child cell into its parent, allow each child cell to be activated only once, and let infection inside each two-vertex cell evolve with the usual recoveries and reinfections until both vertices are healthy. A child cell is activated at its root by the first outgoing arrow to it while the corresponding parent vertex is infected. This process is contained in the original infection process under the graphical representation of the contact process: only infection paths have been removed. The Poisson clocks inside a child cell and on its outgoing edges have not previously been used. The Strong Markov property and independence of the clocks therefore make different cells' offspring counts independent and identically distributed. Dependence among different children of the same cell does not matter. The cell genealogy is a Galton-Watson process.
Let be the probability that a cell, initially infected only at , sends an arrow along one specified outgoing edge from before internal extinction. Let be the corresponding probability for one specified outgoing edge from , and let be the probability of success for the first target when both cell vertices are initially infected. First-step conditioning on the three nonempty pair states givesFor example, from the state with only infected, recovery at rate one fails, an internal arrow at rate leads to the two-infected state, and the target arrow at rate succeeds. From the state with only infected, the target cannot be reached until is infected. Symmetry identifies this latter success probability with . Solving these equations yieldsBy linearity of expectation, the offspring mean is . At the comparison rate ,These finite-state probabilities are continuous in . Hence some still has . The branching-process extinction criterion gives positive probability of infinitely many activated cells. Nonexplosion prevents infinitely many activations in bounded time, and each activation is connected to its ancestor by an infection path. Thus infection survives for all time on that event. The global survival threshold of the contact process consequently satisfiesRetaining reinfection inside pairs is what supplies the strict improvement; a comparison that permits only one infection per vertex would give merely the non-strict bound.
For the local-survival estimate, set and . Each vertex has one neighbour of weight and neighbours of weight . Recoveries remove their vertex weights. Ignoring the restriction that an infection target must be vacant only increases the birth contribution, soThese weights have finite expectations on finite time intervals: a birth-only branching process with the same spatial arrows has expected weight at most . This justifies localization and the expectation identity for the generator. If , Dynkin's formula and the integrating-factor form of the Gronwall inequality giveFor , take , which minimizes and makes it . Starting from then givesIn particular the expected total occupation time of is finite. Its recovery clock has rate one, so the expected number of recovery marks that occur while is infected equals this occupation-time integral and is finite. Each infection episode ends almost surely at a recovery. Infection at unbounded times would therefore require infinitely many such recoveries, an event of probability zero. This height-weighted local extinction bound for the contact process provesThis is a bound for the local survival threshold of the contact process, not just a bound on single-time infection probabilities. For the degree-two tree , the same local conclusion follows by choosing sufficiently close to one for each ; the displayed expression for the global threshold is not a finite numerical assertion in that case.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 37 4 a Solution Created 2026-10-03 Updated 2026-10-14
Use recovery rate one and infection rate along each directed nearest-neighbour edge. The graphical representation of the contact process places independent rate-one recovery marks at graph vertices and rate- arrows on directed edges. Infection travels along time-directed paths following arrows and avoiding recovery marks. The same clocks couple all initial configurations and preserve coordinatewise order. Denote its semigroup by .
The empty configuration is absorbing, so the lower invariant measure is . To construct the upper one, put , where is the all-infected configuration. Since , order preservation and the semigroup property implyThus these laws decrease in stochastic order. More concretely, use clocks on the entire time axis and start from all infected at time , looking at the configuration at time zero. These configurations decrease pointwise as increases: an infection arriving from an earlier start is also obtainable from the all-infected later start. Each coordinate therefore has a limit. Their joint law satisfies in weak convergence of probability measures on the compact product space.
This limit is invariant. The graphical construction is Feller: for finitely many sites and a bounded time interval, the backward ancestor exploration is almost surely finite, since its size is dominated by a finite-rate branching process. Hence a cylinder function evolved for a fixed time is continuous in the initial configuration, by approximation with finite ancestor sets. Cylinder functions uniformly approximate continuous functions on the product space. We may therefore pass to the limit into get . These are indeed the extremal invariant measures of the contact process: if is any invariant probability law of a Markov process, apply to and take limits to obtain .
For the relation with survival, reverse the graphical paths in the interval , also reversing arrows. The law is unchanged because the rates are symmetric between neighbours. The set of ancestors of a site has the law of the contact process started from . ConsequentlyThis is duality of the contact process. The events on the right decrease with time because the empty state is absorbing, and their limiting probability is . It follows thatIf , every coordinate is zero almost surely under ; a countable union over the sites gives . Conversely, if the two invariant measures coincide, this one-site marginal is zero, so . HenceA convention that divides the infection rate by the degree only rescales the parameter; the argument and equivalence are unchanged.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 38 5 Solution Created 2026-10-03 Updated 2026-10-14
For the graphical representation of the contact process, put independent death marks on each vertical time-line at rate , and independent infection arrows at rate for every ordered nearest-neighbour pair. A time-directed path moves vertically upward, cannot pass a death mark, and may follow an infection arrow. From an initial set , the infected set consists of sites reachable at time from . Thus infected sites recover at rate , and a healthy site with infected neighbours becomes infected at rate . Rates here are per ordered edge, fixing the normalization of .
With , writeCouple two infection rates by adding independent arrows of rate to the rate- construction, retaining the same deaths. Every path available at the lower rate remains available at the higher rate. Hence is nondecreasing.
For the lower bound, dominate the infection population by a linear birth-death branching process , started from one particle, with per-particle birth rate and death rate . Assign one branching particle to every infection; allow an offspring at every attempted transmission, including attempts into an already infected site, and let the extra particles continue independently. Matched deaths remove their infection. This constructs . The linear birth rate is nonexplosive, so in particular the contact process from a finite initial set is well-defined with finite population at finite times. Its branching mean solvesConsequentlyIf , let to obtain . This proves the branching bound for contact-process survival
For the upper bound use the dimension comparison for the contact process. Define the height . Construct an auxiliary infected set together with an infected representative of height for every . Initially and . Use the original graphical marks as follows.
- A death at removes from as well as removing that representative from . Other deaths change only .
- From there are exactly arrows into height and exactly arrows into height . When one of these arrows occurs and the target height is absent from , infect in the auxiliary process and use the arrow's target as its representative. That target belongs to after the arrow, whether it was newly infected or already infected.
- Arrows from other sites and arrows into an already occupied auxiliary height produce no auxiliary change.
This rule maintains a live representative for every auxiliary infection. Conditional on the full past, each active representative has death rate and outgoing-arrow rate in each of the two height directions. Representatives at distinct heights are different sites, using distinct death clocks and distinct outgoing ordered-edge clocks. Independence and memorylessness of the underlying Poisson processes give exactly the one-dimensional contact-process generatorThus has the law of the one-dimensional contact process with infection rate , even though the representatives themselves depend on the higher-dimensional history. Since implies at every time,Every for which is therefore supercritical whenever the one-dimensional survival set is nonempty; if that critical value were infinite the inequality would be trivial. Taking infima gives
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 26 4 Solution Created 2026-10-03 Updated 2026-10-07
Independent bond percolation turns a deterministic graph into a random network: each edge is open with probability , independently, and a percolation cluster is a connected component of its open subgraph. Site percolation instead randomizes vertices. On the cubic lattice the percolation probability is the order parameter and is the critical probability. A monotone coupling, using independent uniform edge labels and opening labels below , makes the growth of connectivity with transparent.
For , : self-avoiding walk counting gives , and the planar bound proved above gives an upper bound below one. Below , clusters are finite and connection probabilities decay exponentially, a percolation sharpness theorem rather than a consequence of the threshold definition alone. Above there is almost surely a unique infinite percolation cluster. At criticality, the presence of an infinite percolation cluster must be addressed for the particular model. In two dimensions there is none. The transition replaces a finite characteristic length by scale-free geometry, followed by a macroscopic connected component.
Percolation critical exponents quantify different aspects of this change. Use power-law notation for leading exponents; it may suppress amplitudes and logarithmic corrections. From the subcritical side, define the percolation susceptibility and an exponential correlation length , using a fixed norm for the one-arm rate. Above criticality the unrestricted expectation is infinite, so a finite-cluster percolation susceptibility must exclude the infinite percolation cluster. The principal observables are:
The last distribution is not the distribution seen from a uniformly chosen site: the latter is weighted by cluster size. In the scaling description this accounts for . Under the usual below-upper-critical-dimension scaling hypotheses, further scaling relations for critical exponents includeThey organize the exponents into a small number of independent quantities; they are not automatic identities following only from their definitions. A percolation cluster fractal dimension describes the mass of a large critical cluster of radius as roughly , with the scaling relation for critical exponents in this regime.
The percolation universality hypothesis is that ordinary short-range independent models in the same spatial dimension share these exponents and their continuum behavior despite differing microscopic lattices or using bonds rather than sites. The threshold itself is not universal. Long-range connections, correlations or changes of geometry can change the universality class, so the hypothesis does not include every random graph called percolation.
Two dimensions have a particularly strong geometric structure. Closed planar dual graph circuits obstruct primal open paths. The Harris-Kesten theorem fixes the square lattice bond percolation threshold at , using planar duality and crossing estimates. Self-duality alone is not a proof; uniform rectangle-crossing control is a crucial extra ingredient. The Russo-Seymour-Welsh theorem keeps critical crossing probabilities of rectangles of fixed aspect ratio bounded away from zero and one at all scales. Closed dual circuits on disjoint annular scales then rule out an infinite critical cluster and reveal why arbitrarily large finite structures persist.
Critical site percolation on the triangular lattice has rigorously established conformal invariance of planar percolation for crossing limits and an SLE description of interfaces. These results are specific to this model. The exact planar valuesare rigorously established there; its one-arm probability has exponent . In the corresponding scaling description these values give , , and . The percolation universality hypothesis predicts the same planar exponents for square lattice bond percolation, but the triangular-lattice theorem by itself does not prove that transfer. This distinction separates exact model-specific mathematics from a broader physical prediction.
Dimension changes the importance of loops and correlations between growing branches. The mean-field percolation exponents come from approximating critical clusters by branching processes. Their values are , , , , and . The predicted upper critical dimension of percolation is six. One way to see its role is the triangle diagram appearing in the percolation triangle condition: if the long-distance Fourier connectivity behaves like , its infrared contribution is proportional to . It is finite above six and logarithmically divergent at six. This motivates mean-field behavior above six and logarithmic corrections at six, without turning that heuristic into a proof for every lattice.
Lace expansion makes the mean-field picture rigorous in suitable high-dimensional regimes. For nearest-neighbor percolation, sufficiently high dimensions are covered; sufficiently spread-out models have mean-field results for every . Between two and six the exponents depend nontrivially on dimension, and exact three-dimensional values are not supplied by the planar theory. Hyperscaling relation illustrates the change: mean-field values give , while , so the naive equality fails above six. In , and no infinite percolation cluster exists for ; this is a degenerate endpoint case rather than the ordinary interior transition.
The threshold locates the transition, critical exponents describe its geometry and singularities, and the percolation universality hypothesis proposes which microscopic distinctions disappear at large scales. Planar dual graph arguments and conformal invariance of planar percolation make exceptional, while six marks the expected boundary of mean-field scaling.
A simple model is especially valuable when it overturns a clearly stated expectation and explains why, but surprise is a means to understanding rather than a requirement that every useful model be counterintuitive. The expectation must be explicit enough to test, and the model should identify which assumptions make it fail. A surprising simulation without a mechanism or a plausible connection to observations is not sufficient.
One expectation is that a deterministic system with few variables must settle to a simple, predictable state. The logistic map,provides a compact counterexample. Its positive fixed point is , and the derivative there is . Thus the fixed point is locally stable for ; changing a single parameter can destroy that stability. At , repeated iteration approaches a two-cycle near and . For typical initial conditions at , the Lyapunov exponent is , so nearby initial states separate exponentially on average until the bounded state space limits their separation. Robert M. May's analysis made the consequences of such simple difference equations particularly influential in population modeling.[ref]
Simple mathematical models with very complicated dynamics by Robert M. May. pp. 459–467, first-order maps, stability changes and complex dynamics
The broken expectation is not that determinism is false: the rule remains deterministic. Rather, an irregular trajectory need not be caused by a complicated mechanism or external stochasticity, and exact rules need not permit long-range prediction from imperfectly measured initial conditions. This does not show that every irregular population time series is chaotic. Real populations may experience demographic noise, environmental variation or overlapping generations, and the map's parameters and state must have a defensible biological interpretation. Evidence should distinguish those alternatives. Even within the mathematical example, special initial states can be periodic; the claim about concerns typical trajectories, not every point of the interval.
A second expectation is that diffusion can only erase spatial variation. In a coupled reaction-diffusion equation,diffusion smooths each species separately, yet can destabilize their coupled uniform equilibrium. Linearizing about that equilibrium gives the mode matrix . Local stability of therefore does not by itself imply stability of every spatial mode. This is the organizing insight of the Turing instability.[ref]
The chemical basis of morphogenesis by Alan Turing. §§6–9, instabilities of homogeneous reaction-diffusion systems
For a concrete dimensionless linearization, takeThe well-mixed system has trace and determinant , so its perturbations decay. Writing , the spatial mode has trace and determinantThis determinant is negative for , creating one positive eigenvalue and a growing nonuniform mode. Equal diffusivities would instead shift both eigenvalues left and could not create this two-species instability. On a finite domain, at least one of the modes allowed by the boundary conditions must lie in the unstable band. The algebra exposes exactly why the intuition about smoothing fails: differential transport changes the balance of an interacting local system.
A Turing instability establishes a possible pattern-generating mechanism, not proof that a particular animal's markings use it. One must identify candidate interacting species, measure transport and response properties, and test perturbations that alter the predicted wavelength or stability. The linear example specifies onset only; nonlinear dynamics determine whether growth saturates into a stable pattern. Its value is to convert a vague statement about morphogenesis into discriminating questions, while leaving those experimental obligations visible.
Original mathematical illustrations of changing logistic-map dynamics, sensitivity to initial conditions and diffusion-driven instability
. Details. A third expectation is that an infection with a basic reproduction number above one must produce a major outbreak. Consider the early phase as a continuous-time branching process, with independent per-infective transmission rate and recovery rate , while susceptible depletion is negligible. If is the probability of eventual extinction starting from one infective, conditioning on the first event givesTaking the smallest solution in yields when , and when . Thus still gives an early-lineage extinction probability of . A deterministic SIR model describes mean-field growth but omits this individual realization uncertainty. In a finite closed stochastic SIR model, every epidemic eventually ends; the branching calculation concerns early extinction before substantial susceptible depletion, not that eventual end or an arbitrary peak-size cutoff.
These examples show different benefits of simplicity: a stability calculation can separate predictable from sensitive dynamics, a mode calculation can uncover a new mechanism, and a probability recursion can expose what an average trajectory hides. The same discipline also explains why the word “should” needs qualification. A simple exponential-decay model that confirms a familiar expectation can still calibrate a rate, serve as a control, or expose a faulty measurement. A useful mathematical model must earn its simplifications through the question it answers. Breaking an expectation is a powerful route to discovery when the contradiction is precise, robust to reasonable assumptions and experimentally consequential; novelty alone is not a validation criterion.
The ancestor contributes one individual. Given its offspring count , the descendant family rooted at each child is an independent branching process with the same offspring distribution as the original one. Its total progeny therefore has the same distribution as . The independent reproduction choices let these descendant total progeny variables be represented by independent copies , independent of . Hence, on this family-tree construction,where the sum is zero when .
Start a branching process with one ancestor and offspring distribution for . Its probability generating function is and its mean offspring count is , making it a critical branching process. Splitting the family at the ancestor gives the total progeny recursion . The probability generating function of an independent random sum then gives , whose root satisfying is . Its limit at equals , consistent with finite total progeny almost surely; its derivative diverges there, so the expectation of is nevertheless infinite.

