In a tree, a level consists of all those nodes that are the same distance from the root. We derive asymptotic approximations to the correlation coefficients of two level sizes in random recursive trees and binary search trees. These coefficients undergo sharp sign-changes when one level is fixed and the other is varying. We also propose a new means of deriving an asymptotic estimate for the expected width, which is the number of nodes at the most abundant level. Crucial to our methods of proof is the uniformity achieved by singularity analysis.

Let v(x, t) denote the displacement of an infinitely long, idealized string performing damped vibrations caused by white noise.

Upper and lower bounds for the distribution of maxsv(x, s) and maxxv(x, t) are presented. The results are obtained by adapting Lévy-type inequalities and exploiting a connection of v(x, t) with the Ornstein-Uhlenbeck process through Slepian's theorem.

The case of forced-damped vibrations is also analysed. Finally, a section is devoted to the case of a semi-infinite string performing damped vibrations.

Let ξ1, ξ2,… be a Poisson point process of density λ on (0,∞)d, d ≥ 1, and let ρ, ρ1, ρ2,… be i.i.d. positive random variables independent of the point process. Let C := ⋃i≥1 {ξi + [0,ρi]d}. If, for some t > 0, (0,∞)d ⊆ C, then we say that (0,∞)d is eventually covered by C. We show that the eventual coverage of (0,∞)d depends on the behaviour of xP(ρ > x) as x → ∞ as well as on whether d = 1 or d ≥ 2. These results may be compared to those known for complete coverage of ℝd by such Poisson Boolean models. In addition, we consider the set ⋃{i≥1:Xi=1} [i,i+ρi], where X1, X2,… is a {0,1}-valued Markov chain and ρ1, ρ2,… are i.i.d. positive-integer-valued random variables independent of the Markov chain. We study the eventual coverage properties of this random set.

For arbitrary stationary sequences of random variables satisfying a mild mixing condition, distributional approximations are established for functionals of clusters of exceedances over a high threshold. The approximations are in terms of the distribution of the process conditionally on the event that the first variable exceeds the threshold. This conditional distribution is shown to converge to a nontrivial limit if the finite-dimensional distributions of the process are in the domain of attraction of a multivariate extreme-value distribution. In this case, therefore, limit distributions are obtained for functionals of clusters of extremes, thereby generalizing results for higher-order stationary Markov chains by Yun (2000).

Upper record values and times and inter-record times are studied in their rôles as embedded structures in discrete time extremal processes. Various continuous time approximations to the discrete-time processes are analysed, especially as processes over their state spaces. Discrete time processes, suitably normalized after crossing a threshold T, are shown to converge to limiting continuous time processes as T → ∞ under suitable assumptions on the underlying CDF F, for example, when 1 — F varies regularly at ∞, and more generally. Discrete time extremal processes viewed as processes over their state spaces are noted to have an interesting interpretation in terms of processes of population growth.

Recent research on topics related to geometrical probability is reviewed. The survey includes articles on random points, lines, flats, and networks in Euclidean spaces, pattern recognition, random coverage and packing, random search, stereology, and probabilistic aspects of integral geometry.

A population model is constructed which combines the ideas of a discrete time branching process with random environments and a continuous time non-homogeneous Markov branching process. The extinction problem is considered and necessary and sufficient conditions for extinction are determined. Also discussed are limit theorems for what corresponds to the supercritical case.

In a unified approach, this paper presents distributional properties of a Voronoi tessellation generated by a homogeneous Poisson point process in the Euclidean space of arbitrary dimension. Probability density functions and moments are given for characteristics of the ‘typical’ edge in lower-dimensional section hyperplanes (edge lengths, adjacent angles). We investigate relationships between edges and their neighbours, called Poisson points or centres; namely angular distributions, distances, and positions of neighbours relative to the edge. The approach is analytical, and the results are given partly explicitly and partly as integral expressions, which are suitable for the numerical calculations also presented.

In this paper, optimal stopping problems for semi-Markov processes are studied in a fairly general setting. In such a process transitions are made from state to state in accordance with a Markov chain, but the amount of time spent in each state is random. The times spent in each state follow a general renewal process. They may depend on the present state as well as on the state into which the next transition is made.

Our goal is to maximize the expected net return, which is given as a function of the state at time t minus some cost function. Discounting may or may not be considered. The main theorems (Theorems 3.5 and 3.11) are expressions for the optimal stopping time in the undiscounted and discounted case. These theorems generalize results of Zuckerman [16] and Boshuizen and Gouweleeuw [3]. Applications are given in various special cases.

The results developed in this paper can also be applied to semi-Markov shock models, as considered in Taylor [13], Feldman [6] and Zuckerman [15].

A queueing network with arbitrary topology, state dependent routing and flow control is considered. Customers may enter the network at any queue and they are routed through it until they reach certain queues from which they may leave the system. The routing is based on local state information. The service rate of a server is controlled based on local state information as well. A distributed policy for routing and service rate control is identified that achieves maximum throughput. The policy can be implemented without knowledge of the arrival and service rates. The importance of flow control is demonstrated by showing that, in certain networks, if the servers cannot be forced to idle, then no maximum throughput policy exists when the arrival rates are not known. Also a model for exchange of state information among neighboring nodes is presented and the network is studied when the routing is based on delayed state information. A distributed policy is shown to achieve maximum throughput in the case of delayed state information. Finally, some implications for deterministic flow networks are discussed.

The branching random field is studied under general branching and diffusion laws. Under a renormalization transformation it is shown that at finite fixed time the branching random field converges in law to a generalized Gaussian random field with independent increments. Very mild moment conditions are imposed on the branching process. Under more restrictive conditions on the branching and diffusion processes, the existence of a steady state distribution is proven in the critical case. A central limit theorem is proven for the renormalized steady state, but the limiting Gaussian random field no longer has independent increments. The covariance kernel is now a multiple of the potential kernel of the diffusion process.

This paper deals with Poisson processes on an arbitrary measurable space. Using a direct approach, we derive formulae for moments and cumulants of a vector of multiple Wiener-Itô integrals with respect to the compensated Poisson process. Also, we present a multivariate central limit theorem for a vector whose components admit a finite chaos expansion of the type of a Poisson U-statistic. The approach is based on recent results of Peccati et al. (2010), combining Malliavin calculus and Stein's method; it also yields Berry-Esseen-type bounds. As applications, we discuss moment formulae and central limit theorems for general geometric functionals of intersection processes associated with a stationary Poisson process of k-dimensional flats in .

This paper discusses two-terminal series-parallel networks occurring in Applied Probability and other contexts where the mathematical theory of reliability is developed. Eighty years ago Mac Mahon successfully discussed the number of different structures built of n identical components [1]; later Knödel [3] and Carlitz and Riordan [4] in the 1950's investigated the number of different structures built of n different components. However, in many new applications, engineers and statisticians have to study structures having n components with a specification defining various types of components and stating how many identical components of each kind should be used. This general problem is investigated in Section 7 whilst in Sections 1–6 results obtained earlier are presented and it is shown there how modern approaches to combinatorics (particularly Pólya's Enumerative Combinatorial Analysis) can simplify some reasoning of previous authors.

Haploid population models with non-overlapping generations and fixed population size N are considered. It is assumed that the family sizes ν1,…,νN within a generation are exchangeable random variables. Rates of convergence for the finite-dimensional distributions of a properly time-scaled ancestral coalescent process are established and expressed in terms of the transition probabilities of the ancestral process, i.e., in terms of the joint factorial moments of the offspring variables ν1,…,νN.

The Kingman coalescent appears in the limit as the population size N tends to infinity if and only if triple mergers are asymptotically negligible in comparison with binary mergers. In this case, a simple upper bound for the rate of convergence of the finite-dimensional distributions is derived. It depends (up to some constants) only on the three factorial moments E((ν1)2), E((ν1)3) and E((ν1)2(ν2)2), where (x)k := x(x-1)…(x-k+1). Examples are the Wright-Fisher model, where the rate of convergence is of order N-1, and the Moran model, with a convergence rate of order N-2.

We consider a problem proposed by S. Alpern (European Journal of Operational Research (1997)) of how two players can optimally rendezvous while at the same time evading an enemy searcher. This problem can be modelled as a two-person, zero-sum game between the rendezvous team R (with agents R1, R2) and the searcher S. This paper gives the first solution to such a rendezvous-evasion game by considering a version that is discrete in time and space, as in the pure rendezvous problem of Anderson and Weber (Journal of Applied Probability28, pp. 839–851). R1,R2 and S start at different locations among the n identical locations where there is no common labelling and at each integer time they may rellocate to any one of the n locations. When some location is occupied by more than one player, the game ends. If S is at this location, S (maximizer) wins and the payoff is 1; otherwise R(minimizer) wins and the payoff is 0. The value of the game is the probability that Swins under optimal play. We assume that R1 and R2 can jointly randomize their strategies. When n equals 3, the value of the game is . We also prove that the value of the game is bounded above by asymptotically. If, in addition, the players share a common notion of a directed cycle containing all the nlocations (while still able to move between any two locations), the value of the game is ((1 – 2/n)n–1 + l)/2. Finally, we prove that with this extra information, R can secure a strictly lower value for all n.

Motivated by stability questions on piecewise-deterministic Markov models of bacterial chemotaxis, we study the long-time behavior of a variant of the classic telegraph process having a nonconstant jump rate that induces a drift towards the origin. We compute its invariant law and show exponential ergodicity, obtaining a quantitative control of the total variation distance to equilibrium at each instant of time. These results rely on an exact description of the excursions of the process away from the origin and on the explicit construction of an original coalescent coupling for both the velocity and position. Sharpness of the obtained convergence rate is discussed.

We consider the asymptotic variance of the departure counting process D(t) of the GI/G/1 queue; D(t) denotes the number of departures up to time t. We focus on the case where the system load ϱ equals 1, and prove that the asymptotic variance rate satisfies limt→∞varD(t) / t = λ(1–2/π)(ca2 + cs2), where λ is the arrival rate, and ca2 and cs2 are squared coefficients of variation of the interarrival and service times, respectively. As a consequence, the departures variability has a remarkable singularity in the case in which ϱ equals 1, in line with the BRAVO (balancing reduces asymptotic variance of outputs) effect which was previously encountered in finite-capacity birth-death queues. Under certain technical conditions, our result generalizes to multiserver queues, as well as to queues with more general arrival and service patterns. For the M/M/1 queue, we present an explicit expression of the variance of D(t) for any t.

Reversible spatial birth-death processes are studied with simultaneous jumps of multi-components. A relationship is established between (i) a product-form solution, (ii) a partial symmetry condition on the jump rates and (iii) a solution of a deterministic concentration equation. Applications studied are reversible networks of queues with batch services and blocking and clustering processes such as those found in polymerization chemistry. As illustrated by examples, known results are hereby unified and extended. An expectation interpretation of the transition rates is included.

This paper considers a Markovian bulk-arriving queue modified to allow both mass arrivals when the queue is idle and mass departures which allow for the possibility of removing the entire workload. Properties of queues which terminate when the server becomes idle are developed first, since these play a key role in later developments. Results for the case of mass arrivals, but no mass annihilation, are then constructed with specific attention being paid to recurrence properties, equilibrium queue-size structure, and waiting-time distribution. A closed-form expression for the expected queue size and its Laplace transform are also established. All of these results are then generalised to allow for the removal of the entire workload, with closed-form expressions being developed for the equilibrium size and waiting-time distributions.