General linear-fractional branching processes with discrete time

We study a linear-fractional Bienaymé–Galton–Watson process with a general type space. The corresponding tree contour process is described by an alternating random walk with the downward jumps having a geometric distribution. This leads to the linear-fractional distribution formula for an arbitrary observation time, which allows us to establish transparent limit theorems for the subcritical, critical and supercritical cases. Our results extend recent findings for the linear-fractional branching processes with countably many types.     

Slow recurrent regimes for a class of one-dimensional stochastic growth models

We classify the possible behaviors of a class of one-dimensional stochastic recurrent growth models. In our main result, we obtain nearly optimal bounds for the tail of hitting times of some compact sets. If the process is an aperiodic irreducible Markov chain, we determine whether it is null recurrent or positive recurrent and in the latter case, we obtain a subgeometric convergence of its transition kernel to its invariant measure. We apply our results in particular to state-dependent Galton–Watson processes and we give precise estimates of the tail of the extinction time.     

Bisexual Galton‐Watson Branching Process in Varying Environments

Abstract

In this paper we introduce a bisexual Galton‐Watson branching process (BGWP) in which the offspring probability distribution is different in each generation. We obtain some relations among the probability generating functions (pgf) involved in the model and, making use of mean growth rates and fractional linear functions (flf), we provide sufficient and necessary conditions for its almost sure extinction.     

Functional limit theorems for Galton–Watson processes with very active immigration

We prove weak convergence on the Skorokhod space of Galton–Watson processes with immigration, properly normalized, under the assumption that the tail of the immigration distribution has a logarithmic decay. The limits are extremal shot noise processes. By considering marginal distributions, we recover the results of Pakes (1979).     

Hereditary tree growth and Lévy forests

We introduce the notion of a hereditary property for rooted real trees and we also consider reduction of trees by a given hereditary property. Leaf-length erasure, also called trimming, is included as a special case of hereditary reduction. We only consider the metric structure of trees, and our framework is the space $\mathbb{T}$ of pointed isometry classes of locally compact rooted real trees equipped with the Gromov–Hausdorff distance. We discuss general tightness criteria in $\mathbb{T}$ and limit theorems for growing families of trees. We apply these results to Galton–Watson trees with exponentially distributed edge lengths. This class is preserved by hereditary reduction. Then we consider families of such Galton–Watson trees that are consistent under hereditary reduction and that we call growth processes. We prove that the associated families of offspring distributions are completely characterised by the branching mechanism of a continuous-state branching process. We also prove that such growth processes converge to Lévy forests. As a by-product of this convergence, we obtain a characterisation of the laws of Lévy forests in terms of leaf-length erasure and we obtain invariance principles for discrete Galton–Watson trees, including the super-critical cases.     

Random self-similar trees and a hierarchical branching process

We study self-similarity in random binary rooted trees. In a well-understood case of Galton–Watson trees, a distribution on a space of trees is said to be self-similar if it is invariant with respect to the operation of pruning, which cuts the tree leaves. This only happens for the critical Galton–Watson tree (a constant process progeny), which also exhibits other special symmetries. We extend the prune-invariance setup to arbitrary binary trees with edge lengths. In this general case the class of self-similar processes becomes much richer and covers a variety of practically important situations. The main result is construction of the hierarchical branching processes that satisfy various self-similarity definitions (including mean self-similarity and self-similarity in edge-lengths) depending on the process parameters. Taking the limit of averaged stochastic dynamics, as the number of trajectories increases, we obtain a deterministic system of differential equations that describes the process evolution. This system is used to establish a phase transition that separates fading and explosive behavior of the average process progeny. We describe a class of critical Tokunaga processes that happen at the phase transition boundary. They enjoy multiple additional symmetries and include the celebrated critical binary Galton–Watson tree with independent exponential edge length as a special case. Finally, we discuss a duality between trees and continuous functions, and introduce a class of extreme-invariant processes, constructed as the Harris paths of a self-similar hierarchical branching process, whose local minima has the same (linearly scaled) distribution as the original process.     

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.     

Predicting extinction or explosion in a Galton–Watson branching process

Based on observations $X_1,\dots ,X_n$ X 1 , … , X n of successive generations of a discrete-parameter Galton–Watson branching process, one wishes to predict whether extinction or explosion will ultimately occur. This problem can be formulated as a simple hypothesis-testing problem to which the Neyman–Pearson Lemma is directly applicable if the extinction probability is known or estimable. If it is not, valid (but conservative) tests still can be obtained.     

Biased random walks on Galton–Watson trees

Summary. We consider random walks with a bias toward the root on the family tree T of a supercritical Galton–Watson branching process and show that the speed is positive whenever the walk is transient. The corresponding harmonic measures are carried by subsets of the boundary of dimension smaller than that of the whole boundary. When the bias is directed away from the root and the extinction probability is positive, the speed may be zero even though the walk is transient; the critical bias for positive speed is determined. Received: 7 July 1995 / In revised form: 9 January 1996     

Central limit theorems for biased randomly trapped random walks on Z

We prove CLTs for biased randomly trapped random walks in one dimension. By considering a sequence of regeneration times, we will establish an annealed invariance principle under a second moment condition on the trapping times. In the quenched setting, an environment dependent centring is necessary to achieve a central limit theorem. We determine a suitable expression for this centring. As our main motivation, we apply these results to biased walks on subcritical Galton–Watson trees conditioned to survive for a range of bias values.     

Local Convergence of Large Critical Multi-type Galton–Watson Trees and Applications to Random Maps

We show that large critical multi-type Galton–Watson trees, when conditioned to be large, converge locally in distribution to an infinite tree which is analogous to Kesten’s infinite monotype Galton–Watson tree. This is proven when we condition on the number of vertices of one fixed type, and with an extra technical assumption if we count at least two types. We then apply these results to study local limits of random planar maps, showing that large critical Boltzmann-distributed random maps converge in distribution to an infinite map.     

Conditioning Galton–Watson Trees on Large Maximal Outdegree

We propose a new way to condition random trees, that is, conditioning random trees to have large maximal outdegree. Under this conditioning, we show that conditioned critical Galton–Watson trees converge locally to size-biased trees with a unique infinite spine. For the subcritical case, we obtain the local convergence to size-biased trees with a unique infinite node. We also study the tail of the maximal outdegree of subcritical Galton–Watson trees, which is essential for the proof of the local convergence.     

Infinitely many reducts of homogeneous structures

It is shown that the countably infinite dimensional pointed vector space (the vector space equipped with a constant) over a finite field has infinitely many first order definable reducts. This implies that the countable homogeneous Boolean-algebra has infinitely many reducts.     

Approximation of SDEs by Population-Size-Dependent Galton–Watson Processes

A certain class of stochastic differential equations, containing the Cox–Ingersoll–Ross model and the geometric Brownian motion, is considered. The corresponding solutions are approximated weakly by discrete-time population-size-dependent Galton–Watson processes with immigration. The long-time behavior of the limiting processes is also investigated.     

Well-posedness of Hamilton–Jacobi equations in population dynamics and applications to large deviations

We prove Freidlin–Wentzell type large deviation principles for various rescaled models in populations dynamics that have immigration and possibly harvesting: birth–death processes, Galton–Watson trees, epidemic SI models, and prey–predator models.The proofs are carried out using a general analytic approach based on the well-posedness of a class of associated Hamilton–Jacobi equations. The notable feature for these Hamilton–Jacobi equations is that the Hamiltonian can be discontinuous at the boundary. We prove a well-posedness result for a large class of Hamilton–Jacobi equations corresponding to one-dimensional models, and give partial results for the multi-dimensional setting.     

First exit time probability for multidimensional diffusions: A PDE-based approach

First exit time distributions for multidimensional processes are key quantities in many areas of risk management and option pricing. The aim of this paper is to provide a flexible, fast and accurate algorithm for computing the probability of the first exit time from a bounded domain for multidimensional diffusions. First, we show that the probability distribution of this stopping time is the unique (weak) solution of a parabolic initial and boundary value problem. Then, we describe the algorithm which is based on a combination of the sparse tensor product finite element spaces and an hp-discontinuous Galerkin method. We illustrate our approach with several examples. We also compare the numerical results to classical Monte Carlo methods.     

Local Times of Subdiffusive Biased Walks on Trees

Consider a class of null-recurrent randomly biased walks on a supercritical Galton–Watson tree. We obtain the scaling limits of the local times and the quenched local probability for the biased walk in the subdiffusive case. These results are a consequence of a sharp estimate on the return time, whose analysis is driven by a family of concave recursive equations on trees.     

On family trees and subtrees of simple branching processes

We study the probability of occurrence of certain subtrees of the family tree of a Galton Watson branching process.     

Williams’ decomposition of the Lévy continuum random tree and simultaneous extinction probability for populations with neutral mutations

We consider an initial Eve-population and a population of neutral mutants, such that the total population dies out in finite time. We describe the evolution of the Eve-population and the total population with continuous state branching processes, and the neutral mutation procedure can be seen as an immigration process with intensity proportional to the size of the population. First we establish a Williams’ decomposition of the genealogy of the total population given by a continuum random tree, according to the ancestral lineage of the last individual alive. This allows us to give a closed formula for the probability of simultaneous extinction of the Eve-population and the total population.     

Stability and busy periods in a multiclass queue with state-dependent arrival rates

We introduce a multiclass single-server queueing system in which the arrival rates depend on the current job in service. The system is characterized by a matrix of arrival rates in lieu of a vector of arrival rates. Our proposed model departs from existing state-dependent queueing models in which the parameters depend primarily on the number of jobs in the system rather than on the job in service. We formulate the queueing model and its corresponding fluid model and proceed to obtain necessary and sufficient conditions for stability via fluid models. Utilizing the natural connection with the multitype Galton–Watson processes, the Laplace–Stieltjes transform of busy periods in the system is given. We conclude with tail asymptotics for the busy period for heavy-tailed service time distributions for the regularly varying case.