Search

Suppose that X 1, …, X n are random variables with the same known marginal distribution F but unknown dependence structure. In this paper we study the smallest possible value of P(X 1 + · · · + X n < s) over all possible dependence structures, denoted by m n,F (s). We show that m n,F (ns) → 0 for s no more than the mean of F under weak assumptions. We also derive a limit of m n,F (ns) for any s ∈ R with an error of at most n -1/6 for general continuous distributions. An application of our result to risk management confirms that the worst-case value at risk is asymptotically equivalent to the worst-case expected shortfall for risk aggregation with dependence uncertainty. In the last part of this paper we present a dual presentation of the theory of complete mixability and give dual proofs of theorems in the literature on this concept.

This paper is on conditioned weak limit theorems for imbedded waiting-time processes of an M/G/1 queue. More specifically we study functional limit theorems for the actual waiting-time process conditioned by the event that the number of customers in a busy period exceeds n or equals n. Attention is also paid to the actual waiting-time process with random time index. Combined with the existing literature on the subject this paper gives a complete account of the conditioned limit theorems for the actual waiting-time process of an M/G/1 queue for arbitrary traffic intensity and for a rather general class of service-time distributions. The limit processes that occur are Brownian excursion and meander, while in the case of random time index also the following limit occurs: Brownian excursion divided by an independent and uniform (0, 1) distributed random variable.

Several different orderings for the comparison of point processes have been introduced and their relationships discussed in Whitt [9], Daley [2] and Deng [4]. It is of some interest to know whether these orderings, in general, are preserved under various operations on point processes. Some results concerning limit operations were given in Deng [4]. In the present paper, we first further introduce some convex and concave orderings for counting processes, and survey the relationships among all orderings mentioned in [9], [4] and this paper. Then we focus our attention on the study of the conditions for the preservation of orderings under the operations of superposition, thinning, shift, and random change of time.

We investigate the Zagreb index, one of the topological indices, of random recursive trees in this paper. Through a recurrence equation, the first two moments of Zn, the Zagreb index of a random recursive tree of size n, are obtained. We also show that the random process {Zn − E[Zn], n ≥ 1} is a martingale. Then the asymptotic normality of the Zagreb index of a random recursive tree is given by an application of the martingale central limit theorem. Finally, two other topological indices are also discussed in passing.

In the present paper an almost-sure renewal theorem for branching random walks (BRWs) on the real line is formulated and established. The theorem constitutes a generalization of Nerman's theorem on the almost-sure convergence of Malthus normed supercritical Crump-Mode-Jagers branching processes counted with general characteristic and Gatouras' almost-sure renewal theorem for BRWs on a lattice.

In this paper, we give an analytic solution for graphs with n nodes and E edges for which the probability of obtaining a given graph G is specified in terms of the degree sequence of G. We describe how this model naturally appears in the context of load balancing in communication networks, namely Peer-to-Peer overlays. We then analyse the degree distribution of such graphs and show that the degrees are concentrated around their mean value. Finally, we derive asymptotic results on the number of edges crossing a graph cut and use these results $(i)$ to compute the graph expansion and conductance, and $(ii)$ to analyse the graph resilience to random failures., Comment: 18 pages

In this paper we study the asymptotic tail probabilities of sums of subexponential, nonnegative random variables, which are dependent according to certain general structures with tail independence. The results show that the subexponentiality of the summands eliminates the impact of the dependence on the tail behavior of the sums.

Consider N players, respectively owning x1, x2, …, xN monetary units, who play a sequence of games, winning from and losing to each other integer amounts according to fixed rules. The sequence stops as soon as (at least) one player is ruined. We are interested in the ruin process of these N players, i.e. in the probability that a given player is ruined first, and also in the expected ruin time. This problem is called the N-player ruin problem. In this paper, the problem is set up as a multivariate absorbing Markov chain with an absorbing state corresponding to the ruin of each player. This is then discussed in the context of phase-type distributions where each phase is represented by a vector of size N and the distribution has as many absorbing points as there are ruin events. We use this modified phase-type distribution to obtain an explicit solution to the N-player problem. We define a partition of the set of transient states into different levels, and on it give an extension of the folding algorithm (see Ye and Li (1994)). This provides an efficient computational procedure for calculating some of the key measures.

In this paper we consider stochastic recursive equations of sum type, , and of max type, , where Ai, bi, and b are random, (Xi) are independent, identically distributed copies of X, and denotes equality in distribution. Equations of these types typically characterize limits in the probabilistic analysis of algorithms, in combinatorial optimization problems, and in many other problems having a recursive structure. We develop some new contraction properties of minimal Ls-metrics which allow us to establish general existence and uniqueness results for solutions without imposing any moment conditions. As an application we obtain a one-to-one relationship between the set of solutions to the homogeneous equation and the set of solutions to the inhomogeneous equation, for sum- and max-type equations. We also give a stochastic interpretation of a recent transfer principle of Rösler from nonnegative solutions of sum type to those of max type, by means of random scaled Weibull distributions.

This paper investigates the rate of convergence to the probability distribution of the embedded M/G/1 and GI/M/n queues. We introduce several types of ergodicity including l-ergodicity, geometric ergodicity, uniformly polynomial ergodicity and strong ergodicity. The usual method to prove ergodicity of a Markov chain is to check the existence of a Foster–Lyapunov function or a drift condition, while here we analyse the generating function of the first return probability directly and obtain practical criteria. Moreover, the method can be extended to M/G/1- and GI/M/1-type Markov chains.

The central limit theorem for random walks on ℤ in an i.i.d. space-time random environment was proved by Bernabei et al. for almost all realization of the environment, under a small randomness assumption. In this paper, we prove that, in the nearest-neighbour case, when the averaged random walk is symmetric, the almost sure central limit theorem holds for an arbitrary level of randomness.

Let {X k , k ≥ 1} be a sequence of independent, identically distributed nonnegative random variables with common distribution function F and finite expectation μ > 0. Under the assumption that the tail probability is consistently varying as x tends to infinity, this paper investigates precise large deviations for both the partial sums S n and the random sums S N(t), where N(·) is a counting process independent of the sequence {X k , k ≥ 1}. The obtained results improve some related classical ones. Applications to a risk model with negatively associated claim occurrences and to a risk model with a doubly stochastic arrival process (extended Cox process) are proposed.

In this paper, we consider Galton–Watson trees conditioned by size. We show that the number of k-ancestors (ancestors that have k children) of a node u is (almost) proportional to its depth. The k, j-ancestors are also studied. The methods rely on the study of ladder variables on an associated random walk. We also give an application to finite branching random walks.

The paper characterizes matrices which have a given system of vectors orthogonal with respect to a given probability distribution as its right eigenvectors. Results of Hoare and Rahman are unified in this context, then all matrices with a given orthogonal polynomial system as right eigenvectors under the constraint a0j = 0 for j ≥ 2 are specified. The only stochastic matrices P = {pij} satisfying p00 + p01 = 1 with the Hahn polynomials as right eigenvectors have the form of the Moran mutation model.

This paper considers the occurrence of patterns in sequences of independent trials from a finite alphabet; Gani and Irle (1999) have described a finite state automaton which identifies exactly those sequences of symbols containing the specific pattern, which may be thought of as the word of interest. Each word generates a particular Markov chain. Motivated by a result of Guibas and Odlyzko (1981) on stochastic monotonicity for the random times when a particular word is completed for the first time, a new level-crossing ordering is introduced for stochastic processes. A process {Yn : n = 0, 1, …} is slower in level-crossing than a process {Zn }, if it takes {Yn } stochastically longer than {Zn } to exceed any given level. This relation is shown to be useful for the comparison of stochastic automata, and is used to investigate this ordering for Markov chains in discrete time.

Technology developed in a predecessor paper (Chen and Seneta (1996)) is applied to provide, in a unified manner, a sharpening of bivariate Bonferroni-type bounds on P(v 1≥r, v 2≥u) obtained by Galambos and Lee (1992; upper bound) and Chen and Seneta (1986; lower bound).

The random triangle model was recently introduced as a random graph model that captures the property of transitivity that is often found in social networks, i.e. the property that given that two vertices are second neighbors, they are more likely to be neighbors. For parameters p ∊ [0,1] and q ≥ 1, and a finite graph G = (V, E), it assigns to elements η of {0,1} E probabilities which are proportional to where t(η) is the number of triangles in the open subgraph. In this paper the behavior of the random triangle model on the two-dimensional triangular lattice is studied. By mapping the system onto an Ising model with external field on the hexagonal lattice, it is shown that phase transition occurs if and only if p = (q−1)−2/3 and q > q c for a critical value q c which turns out to equal It is furthermore demonstrated that phase transition cannot occur unless p = p c (q), the critical value for percolation of open edges for given q. This implies that for q ≥ q c , p c (q) = (q−1)−2/3.

This paper deals with the recurrence of branching random walks on polynomially growing graphs. Amongst other things, we demonstrate the strong recurrence of tree indexed random walks determined by the resistance properties of spherically symmetric graphs. Several branching walk models are considered to show how the branching mechanism influences the recurrence behaviour.

In this paper we study the asymptotic behavior of the tail of the stationary backlog distribution in a single server queue with constant service capacity c, fed by the so-called M/G/∞ input process or Cox input process. Asymptotic lower bounds are obtained for any distribution G and asymptotic upper bounds are derived when G is a subexponential distribution. We find the bounds to be tight in some instances, e.g. when G corresponds to either the Pareto or lognormal distribution and c − ρ < 1, where ρ is the arrival rate at the buffer.

Erlang's functionB(λ,C) gives the blocking probability that occurs when Poisson traffic of intensity λ is offered to a link consisting ofCcircuits. However, when dimensioning a telecommunications network, it is more convenient to use the inverseC(λ,B) of Erlang's function, which gives the number of circuits needed to carry Poisson traffic λ with blocking probability at mostB. This paper derives simple bounds forC(λ,B). These bounds are close to each other and the upper bound provides an accurate linear approximation toC(λ,B) which is asymptotically exact in the limit as λ approaches infinity withBfixed

This paper considers queues with a Markov renewal arrival process and a particular transition matrix for the underlying Markov chain. We study the effect that the transition matrix has on the waiting time of the nth customer as well as on the stationary waiting time. The main theorem generalizes results of Szekli et al. (1994a) and partly confirms their conjecture. In this context we show the importance of a new stochastic ordering concept.

Suppose that n arcs with random lengths having distributions F1, F2, · ··, Fn are placed uniformly and independently on a circle. This paper presents inequalities which tell how certain distributions and probabilities change as the variability of the distributions Fl, F2, ··, Fn is increased. A distribution F is considered to be more variable than G if f h(x)dF(x) ≧ h(x)dG(x) for all convex functions h.

The exact solution for the transient distribution of the queue length and busy period of the M/M/1 queue in terms of modified Bessel functions has been proved in a variety of ways. Methods of the past range from spectral analysis (Lederman and Reuter (1954)), combinatorial arguments (Champernowne (1956)), to generating functions coupled with Laplace transforms (Clarke (1956)). In this paper, we present a novel approach that ties the computation of these transient distributions directly to the random sample path behavior of the M/M/1 queue. The use of Laplace transforms is minimized, and the use of generating functions is eliminated completely. This is a method that could prove to be useful in developing a similar transient analysis for queueing networks.

On a circle of unit circumference arcs of length a are placed at random. Let N α be equal to the necessary number of arcs to cover at least the length 1 − p, 0 ≦ p < 1, of the circumference at least m (≧1) times. In the present paper limit distributions of Nα are derived when α → 0. Some results for spacings are also obtained.

The problem of interest is to determine the optimal ordering so as to minimize the long run average cost. Clearly if the P sub i were known the optimal ordering would simply be to order the elements in decreasing order of the P sub i's. In fact even if the P sub i's were unknown we could do as well asymptotically by ordering the elements at each unit of time in decreasing order of the number of previous requests for them. In this paper we first consider the case in which the only memory allowed at any time is the ordering of the elements at that time; in other words, the only type of reordering rules we allow are ones in which the reordered permutation of elements at any time is only allowed to depend on the present ordering and the position of the element requested. We also consider the above problem under the previse that additional memory is allowed. In particular we allow the decision-maker to utilize such rules as 'only make a change (according to some preassigned rule) if the same element has been requested k times in a row.' We show that as k approaches infinity we can do as well as if we knew the values of the P sub i, and in addition we show that the convergence is monotone.

Let X(t) be a continuous time Markov process on the integers such that, if σ is a time at which X makes a jump, X(σ)– X(σ–) is distributed independently of X(σ–), and has finite mean μ and variance. Let q(j) denote the residence time parameter for the state j. If tn denotes the time of the nth jump and Xn ≡ X(tb), it is easy to deduce limit theorems for from those for sums of independent identically distributed random variables. In this paper, it is shown how, for μ > 0 and for suitable q(·), these theorems can be translated into limit theorems for X(t), by using the continuous mapping theorem.

A conjecture of Palásti [11] that the limiting packing density β d in a space of dimension d equals β d where ß is the limiting packing density in one dimension continues to be studied, but with inconsistent results. Some recent correspondence in this journal [7], [8], [13], [14], [15], [16], [18], [19], [20] as well as some other papers indicate a lively interest in the subject. In a prior study [3], we demonstrated that the conjectured value in two dimensions was smaller than the actual density. Here we demonstrate that this is also so in three and four dimensions and that the discrepancy increases with dimension.

This paper gives an elementary proof that, under some general assumptions, the number of parts a convex set in Rd is divided into by a set of independent identically distributed hyperplanes is asymptotically normally distributed. An example is given where the distribution of hyperplanes is 'too singular' to satisfy the assumptions, and where a different limiting distribution appears. GEOMETRICAL PROBABILITY; RANDOM DIVISIONS 1. Preliminaries A set of hyperplanes in Rd is said to be in a general position if every subset of at most d hyperplanes has linearly independent normals, and if not more than d of them intersect in any point.

One of the major difficulties in attempting to apply known queueing theory results to real problems is that almost always these results assume a time-stationary Poisson arrival process, whereas in practice the actual process is almost invariably non-stationary. In this paper we consider single-server infinite-capacity queueing models in which the arrival process is a non-stationary process with an intensity function ∧(t), t ≧ 0, which is itself a random process. We suppose that the average value of the intensity function exists and is equal to some constant, call it λ, with probability 1. We make a conjecture to the effect that ‘the closer {∧(t), t ≧ 0} is to the stationary Poisson process with rate λ ' then the smaller is the average customer delay, and then we verify the conjecture in the special case where the arrival process is an interrupted Poisson process.

In this paper the concavity property for the distribution of a geometric random sum (geometric compound) X, + · ·· + XN is established under the assumption that Xi are i.i.d. and have a DFR distribution. From this and the fact that the actual waiting time in GI/G/1 queues can be written as a geometric random sum, the concavity of the waiting-time distribution in GI/G/1 queues with a DFR service-time distribution is derived. The DFR property of the idle-period distribution in specialized GI/G/1 queues is also mentioned.

The general part of the Borel-Cantelli lemma says that for any sequence of events (An) defined on a probability space (Ω, Σ, P), the divergence of ΣnP(An) is necessary for P(An i.o.) to be one (see e.g. [1]). The sufficient direction is confined to the case where the An are independent. This paper provides a simple counterpart of this lemma in the sense that the independence condition is replaced by for some . We will see that this property of (An) may frequently be assumed without loss of generality. We also disclose a useful duality which allows straightforward conclusions without selecting independent sequences. A simple random walk example and a new result in the theory of ϕ -branching processes will show the tractability of the method.

A well-known result in the theory of random walks states that E{X 2} is finite if and only if E{Z+ } and E{Z_} are both finite (Z + and Z_ being the ladder heights and X a typical step-length) in which case E{X 2} = 2E{Z+ }E{Z_}. This paper contains results relating the existence of moments of X of order ß to the existence of the moments of Z + and Z_ of order ß – 1. The main result is that if β > 2 E{|X|β} < ∞ if and only if and are both finite.

1. (Y) for all non-negative, non-decreasing convex functions φ (X is convexly smaller than Y) if and only if, for all . 2. Let H be the Hardy–Littlewood maximal function HY (x) = E(Y – X | Y > x). Then HY (Y) is the smallest random variable exceeding stochastically all random variables convexly smaller than Y. 3. Let X 1 X 2 · ·· Xn be random variables with given marginal distributions, let I 1, I 2, ···, Ik be arbitrary non-empty subsets of {1,2, ···, n} and let M = max (M is the completion time of a PERT network with paths Ij , and delay times Xi .) The paper introduces a computation of the convex supremum of M in the class of all joint distributions of the Xi 's with specified marginals, and of the ‘bottleneck probability' of each path.

Let {Xk : k ≧ 1} be a sequence of independent, identically distributed random variables with EX 1 = μ < 0. Form the random walk {Sn : n ≧ 0} by setting S 0 = 0, Sn = X 1 + … + Xn, n ≧ 1. Let T denote the hitting time of the set (–∞, 0] by the random walk. The principal result in this paper is to show (under appropriate conditions on the distribution of X 1) that Sn , conditioned on T > n converges weakly to a limit random variable, S∗, and to find the Laplace transform of the distribution of S∗. We also investigate a collection of random walks with mean μ < 0 and conditional limits S∗ (μ), and show that S∗ (μ), properly normalized, converges to a gamma distribution of second order as μ ↗ 0. These results have applications to the GI/G/1 queue, collective risk theory, and the gambler's ruin problem.

Let P= {p 1,···, PN } be a finite discrete probability distribution. Then the entropy of the distribution P, introduced by Shannon [12], is defined as Throughout this paper ∑ will stand for and logarithms will be taken to the base D (D > 1).

This paper studies the existence, in a stable GI/M/1 queue, of the limit as t → ∞ of the distribution of the virtual waiting time process at time t conditioned on the event that at no time in the interval [0, t] the queue has become empty. The conditional limit distribution obtained when the traffic intensity is strictly less than one is the weighted sum of an exponential and a gamma distribution. Similar conditional limit distributions are obtained for the queue size process and the waiting time process as defined by Prabhu (1964).

The subject of this paper is the study of the distribution of integrals of the type where {X(t); t ≧ 0} is some appropriately defined continuous-time parameter stochastic process, and f is a suitable non-negative function of its arguments. This subject has also sometimes been labelled as “the occupation time or the sojourn time problem” in literature. These integrals arise in several domains of applications such as in the theory of inventories and storage (see Moran [14], Naddor [15]), in the study of the cost of the flow-stopping incident involved in the automobile traffic jams (see Gaver [8], Daley [3], Daley and Jacobs [4]). The author encountered such integrals while studying certain stochastic models suitable for the study of response time distributions arising in various live situations. In fact in [19], it was shown that such a distribution is equivalent to the study of an integral of the type (1). Again, in the study of response of host to injection of virulent bacteria, Y(t) with f(X(t), t) = bX(t), with b > 0, could be regarded as a measure of the total amount of toxins produced by the bacteria during (0, t), assuming a constant toxin-excretion rate per bacterium. Here X(t) denotes the number of live bacteria at time t, the growth of which is governed by a birth and death process (see Puri [16], [17] and [18]).

The random packing of geometric objects in one-, two- or three-dimensions may afford useful insights into the structure of crystals, liquids, absorbates on crystals, and in higher dimensions, into problems of pattern recognition. Random packing has accordingly received increasing attention in recent years. Two principal packing procedures have been formulated and each gives rise to different packing ratios. In one case, all possible configurations of a sphere-packed volume are assumed to be equally likely. In the other and most widely reported case, there is random sequential addition of spheres to the volume until it is packed. This is the situation we study in this paper. Most of the work to date has been limited to the theoretical study of the one-dimensional lattice or to continuous cases particularly in the limit for long lines. The higher dimensional cases have resisted theoretical attack but have been studied by computer simulation by Palasti [12] and Solomon [14] and by physical simulation by Bernal and Scott (see [14]).