In this work, we use rigorous probabilistic methods to study the asymptotic degree distribution, clustering coefficient, and diameter of geographical attachment networks. As a type of small-world network model, these networks were first proposed in the physical literature, where they were analyzed only with heuristic arguments and computational simulations.

The elasticity of life expectancy is an important feature in life tables. It is also known as life table entropy in the areas of demography and biology, and as normalized cumulative residual entropy in reliability theory. The elasticity of life expectancy provides useful information on studying the way in which small variations in the force of mortality (or hazard rate) affects the life expectancy. In this paper, a perturbation analysis of the hazard rate to the expected interepoch intervals in a non-homogeneous Poisson process is applied, and further interpretations are given by using a normalized version of the generalized cumulative residual entropy. Properties of the elasticity, including ordering results, bounds and empirical estimation, are obtained. Moreover, the dynamic version of the elasticity is studied, and some monotonicity and characterization results are given.

In this paper, we propose a novel method for constructing upper bounds of the quasi-stationary distribution of SIS processes. Using this method, we obtain an upper bound that is better than the state-of-the-art upper bound. Moreover, we prove that the fixed point map Φ [7] actually preserves the equilibrium reversed hazard rate order under a certain condition. This allows us to further improve the upper bound. Some numerical results are presented to illustrate the results.

In this work, the relationship between the extreme value distributions of the parent and its weighted counterpart distribution is studied. Sufficient conditions are provided in terms of the weight w(x) under which the weighted and parent distributions belong to the same attractor (Fréchet, Weibull, or Gumbel) and the relation of the corresponding shape parameters of the limiting distributions is presented. Additionally, a biased sampling corrected extreme value index is proposed, when the extreme value index is estimated from a biased sample. Finally, some simulation results are presented that suggest the superiority of a biased sample in estimating the extreme value index.

G-Network queueing network models, and in particular the random neural network (RNN), are useful tools for decision making in complex systems, due to their ability to learn from measurements in real time, and in turn provide real-time decisions regarding resource and task allocation. In particular, the RNN has led to the design of the cognitive packet network (CPN) decision tool for the routing of packets in the Internet, and for task allocation in the Cloud. Thus in this paper, we present recent research on how to dynamically create the means for quality of service (QoS) to end users of the Internet and in the Cloud. The approach is based on adapting the decisions so as to benefit users as the conditions in the Internet and in Cloud servers vary due to changing traffic and workload. We present an overview of the algorithms that were designed based on the RNN, and also detail the experimental results that were obtained in three areas: (i) traffic routing for real-time applications, which have strict QoS constraints; (ii) routing approaches, which operate at the overlay level without affecting the Internet infrastructure; and (iii) the routing of tasks across servers in the Cloud through the Internet.

We show how the importance sampling identity can often be used to efficiently bound tail probabilities, illustrating with the normal, Poisson, and gamma random variables.

We consider a problem in which jobs continually arrive to a set of n processors that are arranged in an ordered list. When a job arrives the first processor in line attempts to process it; if it is unsuccessful then the next in line attempts it, and so on. Each time that processor j attempts to process a job it is, independently of all else, successful with (an unknown) probability pj. After a job has been completed or all n attempts have failed then, based on the result, we can reorder the processors before the next job arrives, with the objective being to minimize the average number of attempts per job. This paper compares the transposition rule and the move to the front rule.

We revisit the probability that any two consecutive events in a Poisson process N on [0, t] are separated by a time interval that is greater than s (<t) (a particular scan statistic probability) and the closely related probability (recently introduced by Todinov [8], who denotes it as pMFFOP) that before any event of N in [0, t], there exists an event-free interval greater than s. Both probabilities admit simple explicit expressions, which, however, become intractable for very large values of t/s. Our main objective is to demonstrate that these probabilities can be approximated extremely well for large values of t/s by some very tractable and attractive expressions (actually, already for t larger than a few multiples of s).

In this paper, we develop a general approach to compute the probabilities of unresolved clones in random pooling designs. This unified and systematic approach gives better insight for handling the dependency issue among the columns and among the rows. Consequently, we identify some faster computation formulas for four random pooling designs proposed in the literature, and we derive some probability distribution functions of the number of unresolved clones that were not available before.

A simulation method is developed for computing average reward optimal policies, for a finite state and action Markovian decision process. It is shown that the method is consistent; i.e., it produces solutions arbitrarily close to the optimal. Various types of estimation errors and confidence bounds are examined. Finally, it is shown that the probability distribution of the number of simulation cycles required to compute an e-optimal policy satisfies a large deviations property.

Recent advances from the theory of multivariate stochastic orderings can be used to formalize the “folk theorem” that positive correlations lead to larger buffer levels at a discrete-time infinite capacity multiplexer queue. In particular, it is known that if the input traffic is larger than its independent version in the supermodular (sm) ordering, then their corresponding buffer contents are similarly ordered in the increasing convex (icx) ordering.

A sufficient condition for the aforementioned sm comparison is the stochastic increasingness in sequence (SIS) property of the input traffic. In this article, we provide conditions for the stationary on–off source to be SIS. We then use this result to find conditions under which the superposition of independent on–off sources and the M|G|∞ input model are each sm greater than their respective independent version. Similar but weaker SIS conditions are also obtained for renewal on–off processes.

A number of data items (1,2,…,n) are to be maintained in a structure which consists of several linear lists. Successive requests to access items are independent random variables, and the probability that a particular request is for item i is pi. The cost of accessing the jth item from the front of a list is j. For a single list, the move-to-front rule (MF) has been extensively studied and has been shown to provide good performance. In some actual circumstances, MF is the only physically realizable or convenient policy. We extend the study of move-to-front by examining the case where items are kept in several lists. Following its access, an item must be replaced at the front of one of the lists. In certain cases, assuming the pi's are known, the policy which minimizes the average retrieval cost takes a particularly simple form: no item is ever moved from the list in which it is placed initially.

It is well known that for a stochastically monotone Markov chain {Jn}n≥1 a function γ(n) = Cov[f (J1),g(Jn)] is decreasing if f and g are increasing. We prove this property for a special subclass of nonmonotone double stochastic Markov chains.

We propose two random network models for complex networks, which are treelike and always grow very fast. One is the uniform model and the other is the preferential attachment model, and both of them depends on a parameter 0<p<1. We first briefly discuss the network sizes, each of which can be corresponding to a supercritical branching process. And then we mainly study the degree distributions of both models. The asymptotic degree distribution of the first one with any parameter 0<p<1 is a geometric distribution with parameter 1/2, whereas that of the second one, which depends on p, can be uniquely determined by a functional equation of its probability generating function.

We give a computable bound on the rate of convergence of the occupation measure for the Gibbs sampler to the stationary distribution.

There are n customers that need to be served by m parallel servers (n≥m). Customer i will only wait in queue for an exponentially distributed time with rate λi before departing the system. The service time on server j is exponentially distributed with rate μj for all customers, and upon completion of service of customer i a positive reward ri is earned. The non-preemptive problem is to choose, after each service completion, which currently in queue customer to serve next. The preemptive problem is to decide when to preempt a service, and to choose, after each service completion or preemption, which currently in queue customer to serve next. The objective of both problems is to maximize the expected total return. We give conditions under which a list policy is optimal for both problems.

We present results on the finite-time behavior of the discrete-time, finite-space version of the simulated annealing algorithm. The asymptotic and finite-time behavior of the annealing algorithm under slow cooling will be shown to depend on the largest eigenvalue of a certain matrix. To illustrate the utility of our results, we study the slowly cooled annealing algorithm applied to the maximum matching problem and demonstrate a polynomial randomized approximation property of the algorithm.

A cloud provider hosts virtual machines (VMs) of different types, with different resource requirements. There are bounds on the total amounts of each kind of resource that are available. Requests arrive in batches of different sizes. Under the ‘complete blocking’ policy, a request is accepted only if all the VMs in its batch can be accommodated. The ‘partial blocking’ policy would accept a request if there is room for at least one of the VMs in the batch. Blocked requests are lost, with an associated loss of revenue. The trade-offs between costs and benefits are evaluated by means of appropriate models, for which novel solutions based on fixed-point iterations are proposed. The applicability of those solutions is extended, by means of simplifications, to very large-scale systems. Numerical examples and comparisons with simulations are presented.

The relaxation time for an ergodic Markov process is a measure of the time until ergodicity is reached from its initial state. In this paper the relaxation time for an ergodic truncated birth-death process is studied. It is shown that the relaxation time for such a process on states {0,1, …, N} is the quasi-stationary exit time from the set {,2, …, N{0,1,…, N, N + 1} with two-sided absorption at states 0 and N + 1. The existence of such a dual process has been observed by Siegmund [15] for stochastically monotone Markov processes on the real line. Exit times for birth- death processes with two absorbing states are studied and an efficient algorithm for the numerical evaluation of mean exit times is presented. Simple analytical lower bounds for the relaxation times are obtained. These bounds are numerically accessible. Finally, the sensitivity of the relaxation time to variations in birth and death rates is studied.

In this article we consider a two-person red-and-black game with lower limit. More precisely, assume each player holds an integral amount of chips. At each stage, each player can bet an integral amount between a fixed positive integer ℓ and his possession x if x ≥ ℓ; otherwise, he bets all of his own fortune. He might win his opponent's stakes with a probability that is a function of the ratio of his bet to the sum of both players' bets and is called a win probability function. The goal of each player is to maximize the probability of winning the entire fortune of his opponent by gambling repeatedly with suitably chosen stakes. We will give some suitable conditions on the win probability function such that it is a Nash equilibrium for the subfair player to play boldly and for the superfair player to play timidly.