We investigate vertex levels of containment in a random hypergraph grown in the spirit of a recursive tree. We consider a local profile tracking the evolution of the containment of a particular vertex over time, and a global profile concerned with counts of the number of vertices of a particular containment level.

For the local containment profile, we obtain the exact mean, variance, and probability distribution in terms of standard combinatorial quantities such as generalized harmonic numbers and Stirling numbers of the first kind. Asymptotically, we observe phases: the early vertices have an asymptotically normal distribution, intermediate vertices have a Poisson distribution, and late vertices have a degenerate distribution.

As for the global containment profile, we establish an asymptotically normal distribution for the number of vertices at the smallest containment level as well as their covariances with the number of vertices at the second smallest containment level and the variances of these numbers. The orders in the variance–covariance matrix establish concentration laws.

We consider a multiclass single-server queueing network as a model of a packet switching network. The rates packets are sent into this network are controlled by queues which act as congestion windows. By considering a sequence of congestion controls, we analyse a sequence of stationary queueing networks. In this asymptotic regime, the service capacity of the network remains constant and the sequence of congestion controllers act to exploit the network's capacity by increasing the number of packets within the network. We show that the stationary throughput of routes on this sequence of networks converges to an allocation that maximises aggregate utility subject to the network's capacity constraints. To perform this analysis, we require that our utility functions satisfy an exponential concavity condition. This family of utilities includes weighted α-fair utilities for α > 1.

Let (Yn, Nn)n≥1 be independent and identically distributed bivariate random variables such that the Nn are positive with finite mean ν and the Yn have a common heavy-tailed distribution F. We consider the process (Zn)n≥1 defined by Zn = Yn - Σn-1, where It is shown that the probability that the maximum M = maxn≥1Zn exceeds x is approximately as x → ∞, where F' := 1 - F. Then we study the integrated tail of the maximum of a random walk with long-tailed increments and negative drift over the interval [0, σ], defined by some stopping time σ, in the case in which the randomly stopped sum is negative. Finally, an application to risk theory is considered.

Based on pathwise duality constructions, several new results on truncated queues and storage systems of the G/M/1 type are derived by transforming the workload (content) processes into certain ‘dual’ M/G/1-type processes. We consider queueing systems in which (a) any service requirement that would increase the total workload beyond the capacity is truncated so as to keep the associated sojourn time below a certain constant, or (b) new arrivals do not enter the system if they have to wait more than one time unit in line. For these systems, we derive the steady-state distributions of the workload and the numbers of customers present in the systems as well as the distributions of the lengths of busy and idle periods. Moreover, we use the duality approach to study finite capacity storage systems with general state-dependent outflow rates. Here our duality leads to a Markovian finite storage system with state-dependent jump sizes whose content level process can be analyzed using level crossing techniques. We also derive a connection between the steady-state densities of the non-Markovian continuous-time content level process of the G/M/1 finite storage system with state-dependent outflow rule and the corresponding embedded sequence of peak points (local maxima).

Let $(\xi_k,\eta_k)_{k\in\mathbb{N}}$ be independent identically distributed random vectors with arbitrarily dependent positive components. We call a (globally) perturbed random walk a random sequence $T\,{:\!=}\, (T_k)_{k\in\mathbb{N}}$ defined by $T_k\,{:\!=}\, \xi_1+\cdots+\xi_{k-1}+\eta_k$ for $k\in\mathbb{N}$ . Consider a general branching process generated by T and let $N_j(t)$ denote the number of the jth generation individuals with birth times $\leq t$ . We treat early generations, that is, fixed generations j which do not depend on t. In this setting we prove counterparts for $\mathbb{E}N_j$ of the Blackwell theorem and the key renewal theorem, prove a strong law of large numbers for $N_j$ , and find the first-order asymptotics for the variance of $N_j$ . Also, we prove a functional limit theorem for the vector-valued process $(N_1(ut),\ldots, N_j(ut))_{u\geq0}$ , properly normalized and centered, as $t\to\infty$ . The limit is a vector-valued Gaussian process whose components are integrated Brownian motions.

We analyse an additive-increase and multiplicative-decrease (also known as growth–collapse) process that grows linearly in time and that, at Poisson epochs, experiences downward jumps that are (deterministically) proportional to its present position. For this process, and also for its reflected versions, we consider one- and two-sided exit problems that concern the identification of the laws of exit times from fixed intervals and half-lines. All proofs are based on a unified first-step analysis approach at the first jump epoch, which allows us to give explicit, yet involved, formulas for their Laplace transforms. All eight Laplace transforms can be described in terms of two so-called scale functions associated with the upward one-sided exit time and with the upward two-sided exit time. All other Laplace transforms can be obtained from the above scale functions by taking limits, derivatives, integrals, and combinations of these.

We investigate the average similarity of random strings as captured by the average number of ‘cousins’ in the underlying tree structures. Analytical techniques including poissonization and the Mellin transform are used for accurate calculation of the mean. The string alphabets we consider are m-ary, and the corresponding trees are m-ary trees. Certain analytic issues arise in the m-ary case that do not have an analog in the binary case.

We study collision probabilities concerning the simple balls-and-bins problem developed by Wendl (2003). In this article we give the factorial moment of the number of collisions. Moreover, we obtain a Poisson approximation for the number of collisions using the Chen-Stein method.

We give a simple method to approximate multidimensional exponentially tempered stable processes and show that the approximating process converges in the Skorokhod topology to the tempered process. The approximation is based on the generation of a random angle and a random variable with a lower-dimensional Lévy measure. We then show that if an arbitrarily small normal random variable is added, the marginal densities converge uniformly at an almost linear rate, providing a critical tool to assess the performance of existing particle tracking codes.

The goal is to identify the class of distributions to which the distribution of the maximum of a Lévy process with no negative jumps and negative mean (equivalently, the stationary distribution of the reflected process) belongs. An explicit new distributional identity is obtained for the case where the Lévy process is an independent sum of a Brownian motion and a general subordinator (nondecreasing Lévy process) in terms of a geometrically distributed sum of independent random variables. This generalizes both the distributional form of the standard Pollaczek-Khinchine formula for the stationary workload distribution in the M/G/1 queue and the exponential stationary distribution of a reflected Brownian motion.

Web servers have to be protected against overload since overload can lead to a server breakdown, which in turn causes high response times and low throughput. In this paper, a stochastic model for breakdowns of server systems due to overload is proposed and an admission control policy which protects Web servers by controlling the amount and rate of work entering the system is studied. Requests from the clients arrive at the server following a nonhomogeneous Poisson process and each requested job takes a random time to be completed. It is assumed that the breakdown rate of the server depends on the number of jobs which are currently being performed by the server. Based on the proposed model, the reliability function and the breakdown rate function of the server system are derived. Furthermore, the long-run expected number of jobs completed per unit time is derived as the efficiency measure, and the optimal admission control policy which maximizes the efficiency will be discussed.

In this paper we consider a one dimensional stochastic system described by an elliptic equation. A spatially varying random coefficient is introduced to account for uncertainty or imprecise measurements. We model the logarithm of this coefficient by a Gaussian process and provide asymptotic approximations of the tail probabilities of the derivative of the solution.

Consider a well-shuffled deck of cards of n different types where each type occurs m times. In a complete feedback game, a player is asked to guess the top card from the deck. After each guess, the top card is revealed to the player and is removed from the deck. The total number of correct guesses in a complete feedback game has attracted significant interest in the past few decades. Under different regimes of m, n, the expected number of correct guesses, under the greedy (optimal) strategy, has been obtained by various authors, while there are not many results available about the fluctuations. In this paper we establish a central limit theorem with Berry–Esseen bounds when m is fixed and n is large. Our results extend to the case of decks where different types may have different multiplicity, under suitable assumptions.

In this paper we consider the stationary PH/M/c queue with deterministic impatience times (PH/M/c+D). We show that the probability density function of the virtual waiting time takes the form of a matrix exponential whose exponent is given explicitly by system parameters.

In clinical trials with two treatment arms, Efron's biased coin design, Efron (1971), sequentially assigns a patient to the underrepresented arm with probability p > ½. Under this design the proportion of patients in any arm converges to ½, and the convergence rate is n-1, as opposed to n-½ under some other popular designs. The generalization of Efron's design to K ≥ 2 arms and an unequal target allocation ratio (q1, . . ., qK) can be found in some papers, most of which determine the allocation probabilities ps in a heuristic way. Nonetheless, it has been noted that by using inappropriate ps, the proportion of patients in the K arms never converges to the target ratio. We develop a general theory to answer the question of what allocation probabilities ensure that the realized proportions under a generalized design still converge to the target ratio (q1, . . ., qK) with rate n-1.

Let ℒ be the set of probability measures concentrated on { − 1, 0, 1, 2, …}. Then, if μ0 is in ℒ, there exists at most one μ1 in ℒ, with μ0≠ μ1, such that for all n = 1, 2, ….

Paz (1963), (1971) has shown that for an n × n stochastic matrix P the property that some power of P has a positive ergodic coefficient is decidable. In particular he shows that α (Pk) > 0 for some k, only if it is positive for k = ½n(n – 1). However he states that it is not known whether this bound is sharp. In this paper a sharp bound is given, namely k =½(n – 1)2 + ½ or ½(n − 1)2 + 1 depending on whether n is even or odd. The proof of this is based on some results from number theory.

A multitype urn scheme with random replacements is considered. Each time a ball is picked, another ball is added, and its type is chosen according to the transition probabilities of a reducible Markov chain. The vector of frequencies is shown to converge almost surely to a random element of the set of stationary measures of the Markov chain. Its probability distribution is characterized as the solution to a fixed point problem. It is proved to be Dirichlet in the particular case of a single transient state to which no return is possible. This is no longer the case, however, as soon as returns to transient states are allowed.

A multitype branching process is presented in the framework of marked trees and its structure is studied by applying the strong branching property. In particular, the Markov property and the expression for the generator are derived for the process whose components are the numbers of particles of each type. The filtering of the whole population, observing the number of particles of a given type, is discussed. Weak uniqueness for the filtering equation and a recursive structure for the linearized filtering equation are proved under a suitable assumption on the reproduction law.