Classical and Modern Branching Processes

Frontmatter

Large Deviation Rates for Supercritical and Critical Branching Processes

Abstract

This paper investigates large deviation results for the supercritical multi-type and the critical single type branching processes when conditioned on non extinction thus extending the results in [1] and [2] in two directions. We show for example that in the multitype supercritical case the probability of large deviation between the empirical population proportion and its stable limit decays geometrically. Similarly in the critical single type case the (large deviation) probability that the ratio of the population at time (n + 1) to that at time n deviates from one by more than decays at an algebraic rate. A number of similar results are presented here. Some open problems are indicated.

K. B. Athreya, A. N. Vidyashankar

How Fast Does a General Branching Random Walk Spread?

Abstract

New results on the speed of spread of the one-dimensional spatial branching process are described. Generalizations to the multitype case and to d dimensions are discussed. The relationship of the results with deterministic theory is also indicated. Finally the theory developed is used to re-prove smoothly (and improve slightly) results on certain data-storage algorithms arising in computer science.

J. D. Biggins

Boltzmann-Gibbs Weights in the Branching Random Walk

Abstract

Considering a branching random walk as a tree model for many physical disordered systems the a.s. convergence of the free energy is proved under minimal assumption (finite mean) on the partition function. The overlap of two nodes in the tree is their last common ancestor (or the common part of their branches). Under a “k log k-type” assumption the overlap of two nodes of height n picked up with Boltzmann-Gibbs weights is proved to have an explicit limit distribution. This extends a result of Joffe and simplify a proof of Derrida and Spohn.

AMS(MOS) subject classifications. Primary: 60J80, 60K35. Secondary: 60F10, 82C41.

B. Chauvin, A. Rouault

Stochastic Monotonicity and Branching Processes

Abstract

It is shown that stochastic monotonicity provides a unified treatment of simple and multitype branching processes. In the supercritical case the key to con­vergence in probability or a.s. of suitably normed branching processes is a law of large numbers for some independent copies of random variables. Applications to branching processes in varying environment are given.

Harry Cohn

Multilevel Multitype Branching Models of an Information System

Abstract

We describe a class of multilevel multitype branching particle systems and indicate how it can be applied to model a dynamical information system.

AMS(MOS) subject classifications. Primary 60K35, Secondary 68B15.

D. A. Dawson, Y. Wu

On the Shape of the Wavefront of Branching Random Walk

Abstract

We consider branching random walk on the integers with bounded steps, and study the position X _n of the left-most particle at time n. The random variables (X_n — EX_n) are uniformly tight. In the critical case there are uncountably many limitpoints. We shall explain the associated changing shape of the wavefront from the viewpoints of both weak and strong convergence. The question of whether these two methods lead to the same solution leads to some new near-constancy phenomena.

F. M. Dekking, E. R. Speer

Limiting Distributions in Branching Processes with Two Types of Particles

Abstract

Let us consider a decomposable e branching process with two types of particles T ₁, T₂ such that particles of type T ₂ can only produce particles of types T ₁ whereas particles of type T ₁ can produce particles of both types. The aim of this paper is to characterize the kind of distribution of the particles of types T₁ and T ₂ when the total number n of all particles is fixed. Especially we are interested in the limit case n — ∞. It turns out that depending on the parameters of the process a number of different limiting distributions, e.g. normal or x ² distributions, appear.

Michael Drmota, Vladimir Vatutin

Depth—First Search of Random Trees, and Poisson Point Processes

Abstract

Random planar trees can be represented by point processes in the upper positive quadrant of the plane. This proves helpful in studying the distance—from—theroot process of the depth—first search: For certain splitting trees this so—called contour process is seen to be Markovian and its jump intensities can be explicitly calculated. The representation via point processes also allows to construct locally infinite splitting trees. Moreover we show how to generate Galton—Watson branching trees with possibly infinite offspring variance out of Poisson point processes.

J. Geiger, G. Kersting

Towards Dependence in General Branching Processes

Abstract

The exponential growth of expected population size and ensuing stabilization of composition can be obtained quite generally, even in branching populations with interaction between individuals, through conditioning the contribution of each individual by a suitable, individually adapted, historical a-algebra. Then process convergence can be established provided disjoint daughter populations compete or do not have very strongly positively correlated sizes, or at least not too many of them collaborate closely.

Peter Jagers

A Criterion of Boundedness of Discrete Branching Random Walk

Abstract

A general model of a branching random walk in Z is considered, where the branching and displacements occur with probabilities determined by the position of a parent. A necessary and sufficient condition is given for the random variable

$$ M = \sup \;\max \;\;{X_{n,k}}\;\;\;n \geqslant 0,1 \leqslant k \leqslant {N_n} $$

(1)

to be finite. Here X _n,k is the position of the k-th offspring in the n-th generation. The condition is stated in terms of a naturally arising linear functional equation. A number of examples are discussed, where the condition may be verified.

F. I. Karpelevich, Y. M. Suhov

Quasistationarity in a Branching Model of Division-Within-Division

Abstract

Many biological processes include branching phenomena, which may be called division-within-division. Examples are gene amplification in cancer cells and elsewhere, plasmid dynamics in bacteria, and proliferation of viral particles in host cells. In some cases, the loss of “smaller” particles from the “large” ones leads to extinction of the latter. The logical question is then to ask about the distribution of the nonextinct particles, which mathematically leads to the consideration of quasistationarity, ie. stationarity of the process conditional on nonabsorption.

We consider a model in which the large particles follow a supercritical process, while the small ones divide subcritically. We demonstrate that the part of population of the large particles which contain at least 1 small particle may expand or decay, and that the distribution of the number of small particles in large particles tends to a limit. We also discuss biological significance of results of this type.

Marek Kimmel

Population and Density Dependent Branching Processes

Abstract

This paper gives results on branching processes in which the offspring distribution is a function of the current population size or density. Some interesting phenomena in such processes which do not occur in the classical models are given.

F. C. Klebaner

Directed Polymers in Random Media and Spin Glass Models on Trees

Abstract

Using some results of the theory of branching random walks, we give a unifying framework for the mean-field theory for models of spin glasses and directed polymers in a random medium defined on regular trees. Their phase diagram is studied in the complex plane of temperature.

F. Koukiou

A Conceptual Proof of the Kesten-Stigum Theorem for Multi-Type Branching Processes

Abstract

We give complete proofs of the theorem of convergence of types and the Kesten-Stigum theorem for multi-type branching processes. Very little analysis is used beyond the strong law of large numbers and some basic measure theory.

AMS(MOS) subject classifications. Primary 60J80.

Thomas Kurtz, Russell Lyons, Robin Pemantle, Yuval Peres

On Two Measures Defined on the Boundary of a Branching Tree

Abstract

Replying to a question of A. Joffe, we show that two random measures defined on the boundary of a Galton-Watson tree are mutually singular. We compare them in a precise way, and we extend this result to marked trees in the framework of random fractals.

AMS(MOS) subject classifications. Primary- 60J80; Secondary: 28A78, 28A80, 05CO5.

Quansheng Liu, Alain Rouault

Which Critically Branching Populations Persist?

Abstract

The question how quick the individuals must spread out in order to overcome the clumping caused by a critical branching has been studied in [GRW] and [GW2] for a class of multitype branching populations on R^d. Here, an extension of the results to the genuine multitype branching case is presented, which relies on a more detailed analysis of the individual ancestral process [LWa]. Also, several advances and open problems around the question whether a recurrent migration together with a spatially homogeneous critical branching excludes persistence of the population are discussed.

J. Alfredo López-Mimbela, Anton Wakolbinger

A Simple Path to Biggins’ Martingale Convergence for Branching Random Walk

Abstract

We give a simple non-analytic proof of Biggins’ theorem on martingale convergence for branching random walks.

Russell Lyons

Unsolved Problems Concerning Random Walks on Trees

Abstract

We state some unsolved problems and describe relevant examples concerning random walks on trees. Most of the problems involve the behavior of random walks with drift: e.g., is the speed on Galton-Watson trees monotonic in the drift parameter? These random walks have been used in Monte-Carlo algorithms for sampling from the vertices of a tree; in general, their behavior reflects the size and regularity of the underlying tree. Random walks are related to conductance. The distribution function for the conductance of Galton-Watson trees satisfies an interesting functional equation; is this distribution function absolutely continuous?

Russell Lyons, Robin Pemantle, Yuval Peres

Branching Processes with Local Dependencies

Abstract

This paper is an overview of results for branching processes with dependencies that are local in the family tree. We illustrate principal problems by giving some simple examples of Galton-Watson processes with sibling dependencies. Results for general (Crump-Mode-Jagers) processes are stated and discussed without proofs.

Peter Olofsson

Sharpness of Second Moment Criteria for Branching and Tree-Indexed Processes

Abstract

A class of branching processes in varying environments is exhibited which become extinct almost surely even though the means M_n grow fast enough so that \( \sum {M_n^{ - 1}} \) is finite. In fact, such a process is constructed for every offspring distribution of infinite variance, and this establishes the converse of a previously known fact: that if a distribution has finite variance then \( \sum {M_n^{ - 1} = \infty } \) is equivalent to almost sure extinction. This has as an immediate consequence the converse to a theorem on equipolarity of Galton-Watson trees.

Robin Pemantle

On the Recognition and Structure of Probability Generating Functions

Abstract

If

$$ M\left( s \right) = 1 - {e^{ - \pi (s)}} $$

is a probability generating function, the coefficients π j in the MacLaurin expansion π(s) comprise a harmonic renewal sequence. A simple sufficient condition is given which ensures that a non-negative sequence is harmonic renewal. This condition covers the case of the limiting conditional law of a subcritical Markov branching process.

Examples are given illustrating the limitation of the criterion. The parallel problem for continuous laws and its relation to the CB-process is discussed.

Anthony G. Pakes

Record Values of a Family of Branching Processes

Abstract

Let

$$ {{\text{X}}_{\text{1}}}\left( {\text{t}} \right){\text{, }}{{\text{X}}_{\text{2}}}\left( {\text{t}} \right), \ldots .,{\text{t}} \in {{\text{N}}_0} = \{ 0,{\text{1,}} \ldots \} $$

, be a sequence of discrete time branching processes. We introduce the following assumptions:

$$ {X_i}\left( t \right),i \geqslant 1 $$

(a)

, are independent for any fixed

$$ t \in {N_0}{\text{ and }}{X_i}\left( 0 \right) = 1,i \geqslant 1; $$

$$ P\left\{ {{X_i}\left( t \right) = k\left| {{X_i}\left( 0 \right) = 1} \right.} \right\} = {P_k},k = 0,1, \ldots ,\sum\nolimits_{k = 0}^\infty {{P_k} = 1} $$

(b)

.

Ibrahim Rahimov

Limit Skeleton for Critical Crump-Mode-Jagers Branching Processes

Abstract

Take a critical branching population stemming from an individual with the total progeny size greater than n. Pick up individuals with the total progeny size greater than n. The related genealogical subtree has a limit structure of a special Bellman-Harris branching process as n→ ∞.

Serik Sagitov

Markov Cascades

Abstract

The Kahane-Peyrière theory of homogeneous independent cascades is extended to a class of finite state Markov dependent cascades. The problems of (i) non-triviality (ii) divergence of moments and (iii) carrying dimension are completely solved for this class of models. While the authors have obtained complete solutions to problems (i) and (iii), and partial solutions to (ii) in wider generality, the focus of the present paper is on fixed points of a naturally associated random recursive equation of independent interest in diverse contexts. By essentially algebraic methods of this paper we obtain complete solutions to all three problems (i)-(iii). In particular an interesting role of a “mean-reversal” symmetry in the computation of critical parameters for survival and carrying dimension is uncovered.

Edward C. Waymire, Stanley C. Williams

Limit Theorems for Branching Processes with Random Migration Stopped at Zero

Abstract

In this paper, we study a generalization of the classical BienayméGalton-Watson branching process by allowing a random migration component stopped at zero (i.e. the state zero is absorbing). In each generation for which the population size is positive, with probability p two types of emigration are available - a random number of offsprings and a random number of families (these two random variables can be dependent); with probability q there is not any migration; with probability r an immigration of new individuals is possible, p+q+r = 1. The critical case is investigated with an extension when the initial law is attracted to a stable (p) law, p ≤ 1. The asymptotic form of the probability of non-extinction is studied and conditional limit theorems for the population size are obtained, depending on the range of an additional parameter of criticality.

George P. Yanev, Nickolay M. Yanev

Backmatter