Search

A general model of a branching Markov process on ℝ is considered. Sufficient and necessary conditions are given for the random variable M=supt≥0max1≤k≤N(t)Ξk(t) to be finite. Here Ξk(t) is the position of the kth particle, and N(t) is the size of the population at time t. For some classes of processes (smooth branching diffusions with Feller-type boundary points), this results in a criterion stated in terms of the linear ODEσ2(x)2f″(x)+a(x)f′(x)=λ(x)(1−k(x))f(x). Here σ(x) and a(x) are the diffusion coefficient and the drift of the one-particle diffusion, respectively, and λ(x) and k(x) the intensity of branching and the expected number of offspring at point x, respectively. Similarly, for branching jump Markov processes the conditions are expressed in terms of the relations between the integral μ(x)∫π(x,dy)(f(y)−f(x)) and the product λ(x)(1−k(x))f(x), where λ(x) and k(x) are as before, μ(x) is the intensity of jumping at point x, and π(x,dy) is the distribution of the jump from x to y.

This paper considers a family of independent identically distributed random variables that are indexed by the edges of a graph. The maximum of sums of such variables along the paths of the graph is studied. We show that if one graph covers another one, then the maximum of sums for the first graph is stochastically greater than that for the second graph.

A model of a queueing network is proposed which leads to a stochastic equation generalizing a standard Lindley equation for a single FCFS server. We study the problem of the existence and uniqueness of a stationary solution to this equation and its connection with random processes on a Cayley tree.

A model of centralized symmetric message-switched networks is considered, where the messages having a common address must be served in the central node in the order which corresponds to their epochs of arrival to the network. The limitN → ∞ is discussed, whereN is the branching number of the network graph. This procedure is inspired by an analogy with statistical mechanics (the mean-field approximation). The corresponding limit theorems are established and the limiting probability distribution for the network response time is obtained. Properties of this distribution are discussed in terms of an associated boundary problem.

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.

R.L. Dobrushin (1929-1995) made substantial contributions to Queueing Network Theory (QNT). A review of results from QNT which arose from his ideas or were connected to him in other ways is given. We also comment on various related open problems.

This chapter continues [5]–[7], and its main concepts originally arose from problems in queueing network theory. In the course of later development, the relations with the theory of branching processes were discovered. We are very glad to note that the subject of this chapter is closely related to the problems which were and are the focus of attention of Professor E. B. Dynkin; see [1] and references therein. One author (F.I.K) was a student of Evgenii Borisovich; the others had opportunities to attend his lecture courses and seminars which always had an enormous impact on listeners and participants (not to mention the experience of being examined by him, remembered by everyone for life). We hope that these results will develop further in the direction of Professor Dynkin’s interest.

Consider an oriented, half-infinite, random tree, with origin O, and edges directed from O. The number of edges going out of a given vertex does not depend on the ‘past’ and has a fixed distribution. Given a ‘realization’ of a tree, we associate, with its edges e, iid variables ξ e . We find necessary and sufficient conditions for P(X < ∞) = 1 where \( X = \sup \sum\limits_{{e \in S}} {{\xi_e}} \) and the supremum is over all finite paths S on a tree which starts at O. Various modifications of this result are discussed as well as its connections with stochastic equations.

A Brownian particle walks on a line, with negative drift coefficient. After an exponential lifetime it dies giving birth to a certain number of ‘descendants’ each of which then proceeds independently, following the same rule. We first re-derive a necessary and sufficient condition for P(X’ < ∞) = 1 and P(X < ∞) = 1 where X and X’ are the suprema of the deviation of particles in the positive direction taken, respectively, over the infinite time interval ℝ + = [0, ∞) and over all epochs of death (in a slightly weaker form, a similar result may be deduced from an earlier paper by (McKean 1975)). We then check that functions P(X < x) and P(X’ < x) give (unique) maximal solutions to certain stochastic equations and we prove the existence of other solutions to these equations.

One gives a limit theorem for the joint distribution of the stationary waiting times of customers in the queues of a multiphase queueing system, functioning in a heavy traffic regime. One proves that the joint distribution function of the waiting times is a solution of a problem with a directional derivative for an elliptic differential equation in a polyhedral angle.