For a random mapping model with a single attracting center (Stepanov (1971)) we study the relationship between the sizes of the central tree, the adjacent points, and the free points. Joint, marginal and conditional distributions are shown to be of well-known Lagrangian type. Exact and asymptotic moment properties are investigated with the aid of Riordan's (1968) Abel identities. In particular, the relationship between the size of the central tree and that of the central component is discussed in terms of a regression function.

In the first part of this paper, we will consider a class of Markov chains on the non-negative integers which resemble the Galton-Watson branching process, but with one major difference. If there are k individuals in the nth “generation”, and are independent random variables representing their respective numbers of offspring, then the (n + 1)th generation will contain max individuals rather than as in the branching case. Equivalently, the transition matrices Pij of the chains we will study are to be of the form where F(.) is the probability distribution function of a non-negative, integervalued random variable. The right-hand side of (1) is thus the probability that the maximum of i independent random variables distributed by F has the value j. Such a chain will be called a “maximal branching process”.

On the basis of the Karlin and McGregor result, which states that the transition probability functions of a birth and death process can be expressed via the introduction of an orthogonal polynomial system and a spectral measure, we investigate in this paper how the Laplace transforms and the distributions of different transient characteristics related to excursions of a birth and death process can be expressed by means of the basic orthogonal polynomial system and the spectral measure. This allows us in particular to give a probabilistic interpretation of the series introduced by Stieltjes to study the convergence of the fundamental continued fraction associated with the system. Throughout the paper, we pay special attention to the case when the birth and death process is ergodic. Under the assumption that the spectrum of the spectral measure is discrete, we show how the distributions of different random variables associated with excursions depend on the fundamental continued fraction, the orthogonal polynomial system and the spectral measure.

We provide sufficient conditions for the following types of random variable to have the increasing-failure-rate (IFR) property: sums of a random number of random variables; the time at which a Markov chain crosses a random threshold; the time until a random number of events have occurred in an inhomogeneous Poisson process; and the number of events of a renewal process, and of a general counting process, that have occurred by a randomly distributed time.

We show that using the FIFO service discipline at single server stations with ILR (increasing likelihood ratio) service time distributions in networks of monotone queues results in stochastically earlier departures throughout the network. The converse is true at stations with DLR (decreasing likelihood ratio) service time distributions. We use these results to establish the validity of the following comparisons:

(i) The throughput of a closed network of FIFO single-server queues will be larger (smaller) when the service times are ILR (DLR) rather than exponential with the same means.

(ii) The total stationary number of customers in an open network of FIFO single-server queues with Poisson external arrivals will be stochastically smaller (larger) when the service times are ILR (DLR) rather than exponential with the same means.

We also give a surprising counterexample to show that although FIFO stochastically maximizes the number of departures by any time t from an isolated single-server queue with IHR (increasing hazard rate, which is weaker than ILR) service times, this is no longer true for networks of more than one queue. Thus the ILR assumption cannot be relaxed to IHR.

Finally, we consider multiclass networks of exponential single-server queues, where the class of a customer at a particular station determines its service rate at that station, and show that serving the customer with the highest service rate (which is SEPT — shortest expected processing time first) results in stochastically earlier departures throughout the network, among all preemptive work-conserving policies. We also show that a cµ rule stochastically maximizes the number of non-defective service completions by any time t when there are random, agreeable, yields.

Petrovskaya and Leontovich (1982) proved a central limit theorem for sums of dependent random variables indexed by a graph. We apply this theorem to obtain asymptotic normality for the number of local maxima of a random function on certain graphs and for the number of edges having the same color at both endpoints in randomly colored graphs. We briefly motivate these problems, and conclude with a simple proof of the asymptotic normality of certain U-statistics.

In this paper we study limit theorems for the Feller game which is constructed from one-dimensional simple symmetric random walks, and corresponds to the St. Petersburg game. Motivated by a generalization of the St. Petersburg game which was investigated by Gut (2010), we generalize the Feller game by introducing the parameter α. We investigate limit distributions of the generalized Feller game corresponding to the results of Gut. Firstly, we give the weak law of large numbers for α=1. Moreover, for 0<α≤1, we have convergence in distribution to a stable law with index α. Finally, some limit theorems for a polynomial size and a geometric size deviation are given.

Simulated annealing is a popular and much studied method for maximizing functions on finite or compact spaces. For noncompact state spaces, the method is still sound, but convergence results are scarce. We show here how to prove convergence in such cases, for Markov chains satisfying suitable drift and minorization conditions.

This paper presents an algorithmic procedure to calculate the delay distribution of a type k customer in a first-come-first-served (FCFS) discrete-time queueing system with multiple types of customers, where each type has different service requirements (the MMAP[K]/PH[K]/1 queue). First, we develop a procedure, using matrix analytical methods, to handle arrival processes that do not allow batch arrivals to occur. Next, we show that this technique can be generalized to arrival processes that do allow batch arrivals to occur. We end the paper by presenting some numerical examples.

In a previous paper [4] the author studied the stochastic process {wn, n = 1,2, …}, recursively defined by with K a positive constant, τ1, τ2, … σ1, σ2, …, independent, nonnegative stochastic variables. τ1,τ2…, are identically distributed, and σ1,σ2,…, are also identically distributed variables. For this process the generating function of the Laplace-Stieltjes transforms of the joint distribution of Wn, σ2 + … + σn and τ1 + … + τn−1 has been obtained. Closely related to the process {wn, n = 1, 2,…} is the process {un, n = 1, 2,…} with {un = K + [wn + τn − K]−, n = 1,2,…; these are dual processes.

In the present paper we study the stationary distributions of the processes {wn, n= 1,2, …} and {un, n = 1,2, …}, and the distributions ot the entrance times and return times of the events “wn, n = 0” and “un = K” for some n, for discrete as well as for continuous time. For these events various taboo probabilities are also investigated. The mathematical descri ption of the processes {wn, n = 1,2, …} and {un, n= 1,2, …} gives all the necessary information about the time-dependent behaviour for the general dam model with finite capacity K, since the process {wn, n= 1,2, …} is the basic process for such dam models. In Sections 5, 6 and 7 the general theory is applied to the models M/G/1 and G/M/1. Complete explicit solutions are obtained for these models.

The present theory also leads to new and important results for the queueing system or dam model G/G/1 with infinite capacity. For instance the joint distribution of the busy period (or wet period) and of the supremum of the dam content dunng this period is obtained.

For a random variable (RV) X its moment index κ(X) ≡ sup{κ : E(|X|κ) < ∞} lies in 0 ≤ κ (X) ≤∞; it is a critical quantity and finite for heavy-tailed RVs. The paper shows that κ (min(X, Y)) ≥ κ(X) + κ (Y) for independent non-negative RVs X and Y. For independent non-negative ‘excess' RVs Xs and Ys whose distributions are the integrated tails of X and Y, κ (X) + κ (Y) ≤ κ (min(Xs, Ys)) + 2 ≤ κ (min(X, Y)). An example shows that the inequalities can be strict, though not if the tail of the distribution of either X or Y is a regularly varying function.

Let X(t) be a non-homogeneous birth and death process. In this paper we develop a general method of estimating bounds for the state probabilities for X(t), based on inequalities for the solutions of the forward Kolmogorov equations. Specific examples covered include simple estimates of Pr(X(t) < j | X(0) = k) for the M(t)/M(t)/N/0 and M(t)/M(t)/N queue-length processes.

The long-run average cost per unit time of operating a finite dam controlled by a PlM policy (Faddy (1974), Zuckerman (1977)) is determined when the cumulative input process is (a) a Wiener process with drift and (b) the integral of a Markov chain. It is shown how the cost for (a) can be obtained as the limit of the costs associated with a sequence of input processes of the type (b).

In this note characterizations of the exponential distribution are discussed, based on a generalization of the lack of memory property. The result was motivated by the notion of ‘relevation of distributions' introduced by Krakowski (1973).

The transition functions for the correlated random walk with two absorbing boundaries are derived by means of a combinatorial construction which is based on Krattenthaler's theorem for counting lattice paths with turns. Results for walks with one boundary and for unrestricted walks are presented as special cases. Finally we give an asymptotic formula, which proves to be useful for computational purposes.

If the survival function satisfies the functional equation

where e = (1, …, 1), and if the marginal distributions are exponential, then is the multivariate exponential distribution of Marshall and Olkin. The functional equation has many solutions if the requirement of exponential marginals is not imposed, but the class of possible marginals is somewhat limited (e.g., marginals must be absolutely continuous). The class of possible solutions of the equation is characterized in this paper, and several examples are obtained from models for dependence that may be of practical interest.

A diffusion model for the M/G/1 queue due to D. P. Gaver is used to obtain an approximation for the density function of the busy period. The approximation has the same mean and variance as the exact density function, and can be given explicitly when the service time is constant, or has a negative exponential or gamma distribution, or is a mixture of these types.

Sufficient conditions are given under which two simple point processes on the positive half-line can be stochastically compared as random elements of D(0,∞) or R∞+ Using a martingale approach to point processes, the conditions are proposed via a compensator function family. Appropriate versions of the processes being compared are constructed on the same probability space. The results are illustrated by replacement policies and semi-Markov point processes.

This paper examines the availability of a maintained system where the rate of deterioration is governed by an exogenous random environment. We provide a qualitative result that exposes the relationship between remaining lifetime, environment, and repairs. This result leads to simple bounds that can be used to choose inspection rates that guarantee a specified level of availability. The principal result requires no specific distributional assumptions, is intuitively appealing and can be directly applied by practitioners. Our development employs techniques from stochastic calculus.

In this paper, the componentwise increasing convex order, the upper orthant order, the upper orthant convex order, and the increasing directionally convex order for random vectors are generalized to hierarchical classes of integral stochastic order relations. The elements of the generating classes of functions possess nonnegative partial derivatives up to some given degrees. Some properties of these new stochastic order relations are studied. Particular attention is paid to the comparison of weighted sums of the respective components of ordered random vectors. By providing a unified derivation of standard multivariate stochastic orderings, the present paper shows how some well-known results derive from a common principle.