Independent random cascades on Galton-Watson trees

Consider an independent random cascade acting on the positive Borel measures defined on the boundary of a Galton-Watson tree. Assuming an offspring distribution with finite moments of all orders, J. Peyrière computed the fine scale structure of an independent random cascade on Galton-Watson trees. In this paper we use developments in the cascade theory to relax and clarify the moment assumptions on the offspring distribution. Moreover a larger class of initial measures is covered and, as a result, it is shown that it is the Hölder exponent of the initial measure which is the critical parameter in the Peyrière theory.

     

Bounded branching process and and/or tree evaluation

We study the tail distribution of supercritical branching processes for which the number of offspring of an element is bounded. Given a supercritical branching process {Z_n} with a bounded offspring distribution, we derive a tight bound, decaying super-exponentially fast as c increases, on the probability Pr[Z_n > cE(Z_n)], and a similar bound on the probability Pr[Z_n ≤ E(Z_n)/c] under the assumption that each element generates at least two offspring. As an application, we observe that the execution of a canonical algorithm for evaluating uniform AND/OR trees in certain probabilistic models can be viewed as a two-type supercritical branching process with bounded offspring, and show that the execution time of this algorithm is likely to concentrate around its expectation, with a standard deviation of the same order as the expectation.     

人口数相依的两性分支过程的极限性质

本文研究了后代分布依赖于人口数的两性Galton-Watson分支过程, 在对后代分布的适当假设下,对于上临界的情况, 我们研究了有关过程的几乎处处收敛的极限性质.     

A class of two-sex branching processes with reproduction phase in a random environment

We model the demographic dynamics of populations with sexual reproduction where the reproduction phase occurs in a non-predictable environment and we assume the immigration/out-migration of mating units in the population. We introduce a general class of two-sex branching processes where, in each generation, the number of mating units which take part in the reproduction phase is randomly determined and the offspring probability distribution changes over time in a random environment. We provide several probabilistic results about the limit behaviour of populations whose dynamics is modelled by such a class of stochastic processes. In particular, we provide sufficient conditions for the almost sure extinction of the population or for its survival with a positive probability. As illustration, we include some simulated examples.     

Bayesian non-parametric estimation for age-dependent branching processes

The purpose of this paper is to obtain Bayes estimators for both the offspring and life-length distribution in the context of a Bellman-Harris age-dependent branching process. We take a non-parametric approach by letting the prior random distributions, for the offspring and life-length distributions, be independent Dirichlet processes. Our primary results concern the derivation of Bayes estimators, under weighted squared error loss for each distribution. We also indicate some of their asymptotic properties and briefly discuss the modifications that become necessary when the initial information is such that the prior random distribution cannot be taken to be independent.     

Critical multitype branching processes with infinite variance

The exponential limit law for the critical multitype Bienaymé-Galton-Watson process is extended to a class of offspring distributions some or all of whose second moments are infinite. Several asymptotic consequences pertaining to transition probabilities and invariant measures are derived.     

A fuzzy logic-based hybrid estimation of distribution algorithm for distributed permutation flowshop scheduling problems under machine breakdown

As the research interest in distributed scheduling is growing, distributed permutation flowshop scheduling problems (DPFSPs) have recently attracted an increasing attention. This paper presents a fuzzy logic-based hybrid estimation of distribution algorithm (FL-HEDA) to address DPFSPs under machine breakdown with makespan criterion. In order to explore more promising search space, FL-HEDA hybridises the probabilistic model of estimation of distribution algorithm with crossover and mutation operators of genetic algorithm to produce new offspring. In the FL-HEDA, a novel fuzzy logic-based adaptive evolution strategy (FL-AES) is adopted to preserve the population diversity by dynamically adjusting the ratio of offspring generated by the probabilistic model. Moreover, a discrete-event simulator that models the production process under machine breakdown is applied to evaluate expected makespan of offspring individuals. The simulation results show the effectiveness of FL-HEDA in solving DPFSPs under machine breakdown.     

On sequential estimation for branching processes with immigration

Consider a Galton–Watson process with immigration. The limiting distributions of the nonsequential estimators of the offspring mean have been proved to be drastically different for the critical case and subcritical and supercritical cases. A sequential estimator, proposed by Sriram et al. (Ann. Statist. 19 (1991) 2232), was shown to be asymptotically normal for both the subcritical and critical cases. Based on a certain stopping rule, we construct a class of two-stage estimators for the offspring mean. These estimators are shown to be asymptotically normal for all the three cases. This gives, without assuming any prior knowledge, a unified estimation and inference procedure for the offspring mean.     

Fractal Percolation,Porosity, and Dimension

We study the porosity properties of fractal percolation sets \(E\subset \mathbb {R}^d\). Among other things, for all \(0<\varepsilon <\tfrac{1}{2}\), we obtain dimension bounds for the set of exceptional points where the upper porosity of E is less than \(\tfrac{1}{2}-\varepsilon \), or the lower porosity is larger than \(\varepsilon \). Our method works also for inhomogeneous fractal percolation and more general random sets whose offspring distribution gives rise to a Galton–Watson process.     

Branching/queueing networks: Their introduction and near-decomposability asymptotics

A new class of models, which combines closed queueing networks with branching processes, is introduced. The motivation comes from MIMD computers and other service systems in which the arrival of new work is always triggered by the completion of former work, and the amount of arriving work is variable. In the variant of branching/queueing networks studied here, a customer branches into a random and state-independent number of offspring upon completing its service. The process regenerates whenever the population becomes extinct. Implications for less rudimentary variants are discussed. The ergodicity of the network and several other aspects are related to the expected total number of progeny of an associated multitype Galton-Watson process. We give a formula for that expected number of progeny. The objects of main interest are the stationary state distribution and the throughputs. Closed-form solutions are available for the multi-server single-node model, and for homogeneous networks of infinite-servers. Generally, branching/queueing networks do not seem to have a product-form state distribution. We propose a conditional product-form approximation, and show that it is approached as a limit by branching/queueing networks with a slowly varying population size. The proof demonstrates an application of the nearly complete decomposability paradigm to an infinite state space. This revised version was published online in June 2006 with corrections to the Cover Date.     

Bisexual Galton-Watson Branching Processes in Random Environments

In this paper, we consider a bisexual Galton-Watson branching process whose offspring probability distribution is controlled by a random environment proccss. Some results for the probability generating functions associated with the process are obtained and sufficient conditions for certain extinction and for non-certain extinction are established.     

带移民的上临界分支过程在一般条件下的小值概率

本文的主要目的是在后代分布均值有限但L log L阶距无限的条件下研究带移民的上临界分支过程(Z_n)的小值概率.当后代分布均值有限且移民分布的log L阶距有限时,存在常数序列{C_n,n≥0}使得C_n~(-1)Z_n收敛到一个非负有限且非退化的随机变量,记作W.本文基于前期关于分支过程小值概率的工作,在最一般的条件下得到了W的小值概率,即P(W≤ε)在ε→0~+时的收敛速率.     

ON THE EXTINCTION OF POPULATION-SIZE-DEPENDENT BISEXUAL GALTON-WATSON PROCESSES

In this article, the population-size-dependent bisexual Galton-Watson processes are considered. Under some suitable conditions on the mating functions and the offspring distribution, existence of the limit of mean growth rate per mating unit is proved. And based on the limit, a criterion to identify whether the process admits ultimate extinct with probability one is obtained.     

A population dynamics model with strong maternal care

A two-sex age-structured nondispersing population dynamics deterministic model is presented taking into account strong maternal and weak paternal care of offspring. The model includes a weighted harmonic-mean type pair formation function and neglects the spatial dispersal and separation of pairs. It is assumed that each sex has pre-reproductive and reproductive age intervals. All adult individuals are divided into single males, single females, permanent pairs, and female-widows taking care of their offsprings after the death of their partners. All pairs are of two types: pairs without offspring under parental care at the given time and pairs taking child care. All individuals of pre-reproductive age are divided into young and juvenile groups. The young offspring are assumed to be under parental or maternal (after the death of their father) care. Juveniles can live without parental or maternal care but they cannot reproduce offsprings. It is assumed that births can only occur from couples. The model consists of nine integro-PDEs subject to the conditions of integral type. A class of separable solutions is studied, and a system for macro-moments evolving in time is derived in the case of age-independent vital ones. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 46, No. 2, pp. 215–255, April–June, 2006.     

A Population Dynamics Model with Parental Care

A model for an agestructured unlimited population dynamics with parental care of offspring is presented (migration of individuals is not taken into account). The model consists of six partial integrodifferential equations for single males, single females, pairs with offspring under parental care, pairs without offspring under parental care, and offspring of the male and female sex. A class of separable solutions is constructed.     

Convergence of critical multitype Galton-Watson branching processes

Allowing an offspring probability distribution that has infinite variances, we establish the convergence in finite-dimensional distributions of normalized critical multitype Galton-Watson branching processes with increasing initial population size in the two cases of not conditioning and of conditioning on non-extinction of the processes in the nth generation. Furthermore, if the offspring probability distribution has only finite variances, we show that some linear functions of the above processes weakly converge to the diffusions given by Feller, and by Lamperti and Ney.     

A Note on “State Spaces of the Snake and Its Tour—Convergence of the Discrete Snake” by J.-F. Marckert and A. Mokkadem

In State spaces of the snake and its tour—Convergence of the discrete snake the authors showed a limit theorem for Galton–Watson trees with geometric offspring distribution. In this note it is shown that their result holds for all Galton–Watson trees with finite offspring variance.     

Construction and regularity of measure-valued markov branching processes

A construction is given for a general class of measure-valued Markov branching processes. The underlying spatial motion process is an arbitrary Borel right Markov process, and state-dependent offspring laws are allowed. It is shown that such processes are Hunt processes in the Ray weak* topology, and have continuous paths if and only if the total mass process is continuous. The entrance spaces of such processes are described explicitly. Research supported in part by NSF Grant DMS 87-21237.     

Some new limit theorems for the critical branching process allowing immigration

Some limit theorems are obtained for the population size of a critical Bienaymé-Galton-Watson process allowing immigration and where the variance of the offspring distribution is infinite. An application is given to a limit theorem for the situation where the immigration does not occur but the population size is conditioned on non-extinction until the remote future. This complements a well-known result of Slack.     

A conditional limit theorem for tree-indexed random walk

We consider Galton–Watson trees associated with a critical offspring distribution and conditioned to have exactly n$n$ vertices. These trees are embedded in the real line by assigning spatial positions to the vertices, in such a way that the increments of the spatial positions along edges of the tree are independent variables distributed according to a symmetric probability distribution on the real line. We then condition on the event that all spatial positions are nonnegative. Under suitable assumptions on the offspring distribution and the spatial displacements, we prove that these conditioned spatial trees converge as n→∞$n\to \infty$, modulo an appropriate rescaling, towards the conditioned Brownian tree that was studied in previous work. Applications are given to asymptotics for random quadrangulations.