Branching random walks and contact processes on homogeneous trees

Summary. Branching random walks and contact processes on the homogeneous tree in which each site has d+1 neighbors have three possible types of behavior (for d≧ 2): local survival, local extinction with global survival, and global extinction. For branching random walks, we show that if there is local extinction, then the probability that an individual ever has a descendent at a site n units away from that individual’s location is at most d ^{− n/2} , while if there is global extinction, this probability is at most d ⁻ⁿ . Next, we consider the structure of the set of invariant measures with finite intensity for the system, and see how this structure depends on whether or not there is local and/or global survival. These results suggest some problems and conjectures for contact processes on trees. We prove some and leave others open. In particular, we prove that for some values of the infection parameter λ, there are nontrivial invariant measures which have a density tending to zero in all directions, and hence are different from those constructed by Durrett and Schinazi in a recent paper. Received: 26 April 1996/In revised form: 20 June 1996     

Branching random walks,stable point processes and regular variation

Using the theory of regular variation, we give a sufficient condition for a point process to be in the superposition domain of attraction of a strictly stable point process. This sufficient condition is used to obtain the weak limit of a sequence of point processes induced by a branching random walk with jointly regularly varying displacements. Because of heavy tails of the step size distribution, we can invoke a one large jump principle at the level of point processes to give an explicit representation of the limiting point process. As a consequence, we extend the main result of Durrett (1983) and verify that two related predictions of Brunet and Derrida (2011) remain valid for this model.     

Branching processes and random mappings of finite sets

Mathematical Notes -     

Uniform recursive trees: Branching structure and simple random downward walk

As models for spread of epidemics, family trees, etc., various authors have used a random tree called the uniform recursive tree. Its branching structure and the length of simple random downward walk (SRDW) on it are investigated in this paper. On the uniform recursive tree of size n, we first give the distribution law of ζn,m, the number of m-branches, whose asymptotic distribution is the Poisson distribution with parameter . We also give the joint distribution of the numbers of various branches and their covariance matrix. On Ln, the walk length of SRDW, we first give the exact expression of P(Ln=2). Finally, the asymptotic behavior of Ln is given.     

Structure theorems for generalized random processes

Generalized random processes are classified by various types of continuity. Representation theorems of a generalized random process on {M _p } on a set with arbitrary large probability, as well as representations of a correlation operator of a generalized random process on {M _p } and L ^r (R), r > 1, are given. Especially, Gaussian generalized random processes are proven to be representable as a sum of derivatives of classical Gaussian processes with appropriate growth rate at infinity. Examples show the essence of all the proposed assumptions. In order to emphasize the differences in the concept of generalized random processes defined by various conditions of continuity, the stochastic differential equation y′(ω; t) = f(ω; t) is considered, where y is a generalized random process having a point value at t = 0 in the sense of Lojasiewicz. This paper was supported by the project Functional analysis, ODEs and PDEs with singularities, No. 144016, financed by the Ministry of Science, Republic of Serbia.     

Expectation transfer between branching processes and random trees

An approach for translating results on expected parameter values from subcritical Galton–Watson branching processes to simply generated random trees under the uniform model is outlined. As an auxiliary technique for asymptotic evaluations, we use Flajolet's and Odlyzko's transfer theorems. Some classical results on random trees are re-derived by the mentioned approach, and some new results are presented. For example, the asymptotic behavior of linearly recursive tree parameters is described and the asymptotic probability of level k to contain exactly one node is determined. © 1993 John Wiley & Sons, Inc.     

Limiting distributions and estimation in generalized Polya random walk scheme

Asymptotic behavior of distributions generated by Polya random walks is investigated. Unbiased estimators of these distributions are constructed for closed first-arrival plans.Translated from Statisticheskie Metody Otsenivaniya i Proverki Gipotez, pp. 20–36, 1986.     

Branching in branch-and-price: a generic scheme

Developing a branching scheme that is compatible with the column generation procedure can be challenging. Application specific and generic schemes have been proposed in the literature, but they have their drawbacks. One generic scheme is to implement standard branching in the space of the compact formulation to which the Dantzig-Wolfe reformulation was applied. However, in the presence of multiple identical subsystems, the mapping to the original variable space typically induces symmetries. An alternative, in an application specific context, can be to expand the compact formulation to offer a wider choice of branching variables. Other existing generic schemes for use in branch-and-price imply modifications to the pricing problem. This is a concern because the pricing oracle on which the method relies might become obsolete beyond the root node. This paper presents a generic branching scheme in which the pricing oracle of the root node remains of use after branching (assuming that the pricing oracle can handle bounds on the subproblem variables). The scheme does not require the use of an extended formulation of the original problem. It proceeds by recursively partitioning the subproblem solution set. Branching constraints are enforced in the pricing problem instead of being dualized via Lagrangian relaxation, and the pricing problem is solved by a limited number of calls to the pricing oracle. This generic scheme builds on previously proposed approaches and unifies them. We illustrate its use on the cutting stock and bin packing problems. This is the first branch-and-price algorithm capable of solving such problems to integrality without modifying the subproblem or expanding its variable space.     

Pathwidth, trees, and random embeddings

We prove that, for every integer k≥1, every shortest-path metric on a graph of pathwidth k embeds into a distribution over random trees with distortion at most c=c(k), independent of the graph size. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair [12] states that for every minor-closed family of graphs F, there is a constant c(F) such that the multi-commodity max-flow/min-cut gap for every flow instance on a graph from F is at most c(F). The preceding embedding theorem is used to prove this conjecture whenever the family F does not contain all trees.     

Branching structure of uniform recursive trees

The branching structure of uniform recursive trees is investigated in this paper. Using the method of sums for a sequence of independent random variables, the distribution law of ηn, the number of branches of the uniform recursive tree of size n are given first. It is shown that the strong law of large numbers, the central limit theorem and the law of iterated logarithm for ηn follow easily from this method. Next it is shown that ηn and ξn, the depth of vertex n, have the same distribution, and the distribution law of ζn,m, the number of branches of size m, is also given, whose asymptotic distribution is the Poisson distribution with parameter λ= 1/m. In addition, the joint distribution and the asymptotic joint distribution of the numbers of various branches are given. Finally, it is proved that the size of the biggest branch tends to infinity almost sure as n→∞.     

Surviving particles for subcritical branching processes in random environment

The asymptotic behavior of a subcritical Branching Process in Random Environment (BPRE) starting with several particles depends on whether the BPRE is strongly subcritical (SS), intermediate subcritical (IS) or weakly subcritical (WS). In the (SS+IS) case, the asymptotic probability of survival is proportional to the initial number of particles, and conditionally on the survival of the population, only one initial particle survives a.s$a.s$. These two properties do not hold in the (WS) case and different asymptotics are established, which require new results on random walks with negative drift. We provide an interpretation of these results by characterizing the sequence of environments selected when we condition on the survival of particles. This also raises the problem of the dependence of the Yaglom quasistationary distributions on the initial number of particles and the asymptotic behavior of the Q-process associated with a subcritical BPRE.     

Maxima of random properties of particles in supercritical branching processes

Maxima of i.i.d. random variables are considered in the case when the growth of a sample is described by a supercritical branching process without degeneration. Limit theorems on distributions of maxima are proved. Some examples are presented. A connection with maximum-semistable laws is revealed.     

Branching random walk with a critical branching part

We consider the branching treeT(n) of the first (n+1) generations of a critical branching process, conditioned on survival till time βn for some fixed β>0 or on extinction occurring at timek _n withk _n /n→β. We attach to each vertexv of this tree a random variableX(v) and define , where π(0,v) is the unique path in the family tree from its root tov. FinallyM _n is the maximal displacement of the branching random walkS(·), that isM _n =max{S(v):v∈T(n)}. We show that if theX(v), v∈T(n), are i.i.d. with mean 0, then under some further moment conditionn ^−1/2 M _n converges in distribution. In particular {n ^−1/2 M _n } _n⩾1 is a tight family. This is closely related to recent results about Aldous' continuum tree and Le Gall's Brownian snake.     

On large‐girth regular graphs and random processes on trees

We study various classes of random processes defined on the regular tree T_d that are invariant under the automorphism group of T_d. The most important ones are factor of i.i.d. processes (randomized local algorithms), branching Markov chains and a new class that we call typical processes. Using Glauber dynamics on processes we give a sufficient condition for a branching Markov chain to be factor of i.i.d.     

Branching Markov processes and related asymptotics

Models for Markov processes indexed by a branching process are presented. The new class of models is referred to as the branching Markov process (BMP). The law of large numbers and a central limit theorem for the BMP are established. Bifurcating autoregressive processes (BAR) are special cases of the general BMP model discussed in the paper. Applications to parameter estimation are also presented.