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.

We show that winning the game New Age Solitaire only depends on the number of rising sequences in the deck used. The probability of winning for the special case of a new deck that is shuffled using the GSR shuffle (and two variants) are studied. We show that this game pinpoints the Achilles' heel of the GSR shuffle as is demonstrated using the variation distance.

We prove that the effective resistances of spherically symmetric random trees dominate in mean the effective resistances of random trees corresponding branching processes in varying environments and having the same growth law of spherically symmetric trees. We conjecture that the statement does not necessarily hold true in the case of stochastic domination and give an idea of constructing a counterexample.

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.

It is known that a threshold policy (or trunk reservation policy) is optimal for Erlang's loss system under certain assumptions. This paper examines the robustness of this policy under departures from the standard assumption of Poisson arrivals and shows that the optimal policy has a generalized trunk reservation form.

Standard server assignment policies for multi-server queueing stations include the noncollaborative policy, where the servers work in parallel on different jobs; and the fully collaborative policy, where the servers work together on the same job. However, if each job can be decomposed into subtasks with no precedence relationships, then we consider a form of server coordination named task assignment where the servers work in parallel on different subtasks of the same job. We identify the task assignment policy that maximizes the long-run average throughput of a queueing station with finite internal buffers when blocked servers can be idled or reassigned to either replace or collaborate with other servers on unblocked subtasks. We then compare the server coordination policies and show that the task assignment is best when the servers are highly specialized; otherwise, the fully collaborative or noncollaborative policies are preferable depending on whether the synergy level among the servers is high or not. We also provide numerical results that quantify our previous comparison. Finally, we address buffer allocation in longer lines where there are precedence relationships between some of the tasks, and present numerical results that suggest our comparisons for one queueing station generalize to longer lines.

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.

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 paper, we analyze the end-to-end delay performance of a tandem queueing system with mobile queues. Due to state-space explosion, there is no hope for a numerical exact analysis for the joint-queue-length distribution. For this reason, we present an analytical approximation that is based on queue-length analysis. Through extensive numerical validation, we find that the queue-length approximation exhibits excellent performance for light traffic load.

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 give a computable bound on the rate of convergence of the occupation measure for the Gibbs sampler to the stationary distribution.

This paper studies a periodic-review single-commodity setup-cost inventory model with backorders and holding/backlog costs satisfying quasiconvexity assumptions. We show that the Markov decision process for this inventory model satisfies the assumptions that lead to the validity of optimality equations for discounted and average-cost problems and to the existence of optimal (s, S) policies. In particular, we prove the equicontinuity of the family of discounted value functions and the convergence of optimal discounted lower thresholds to the optimal average-cost lower threshold for some sequence of discount factors converging to 1. If an arbitrary nonnegative amount of inventory can be ordered, we establish stronger convergence properties: (i) the optimal discounted lower thresholds converge to optimal average-cost lower threshold; and (ii) the discounted relative value functions converge to average-cost relative value function. These convergence results previously were known only for subsequences of discount factors even for problems with convex holding/backlog costs. The results of this paper also hold for problems with fixed lead times.

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.

It has long been observed that independent laboratories differ in reporting the results of repeated experiments. The problem is to detect those laboratories that might be considered aberrant. Previous analyses have been based on an analysis of variance framework or on subset selection for the detection of aberrant laboratories. The present procedure is also based on an ANOVA model but uses a Bayesian estimate of the number of aberrant laboratories. Subsequent to the determination of the aberrant laboratories, a linear model is used to separate sampling and laboratory effects.

We consider in this article an urn and ball problem with replacement, where balls are with different colors and are drawn uniformly from a unique urn. The numbers of balls with a given color are independent and identically distributed random variables with a heavy tailed probability distribution—for instance a Pareto or a Weibull distribution. We draw a small fraction p≪1 of the total number of balls. The basic problem addressed in this article is to know to which extent we can infer the total number of colors and the distribution of the number of balls with a given color. By means of Le Cam's inequality and the Chen–Stein method, bounds for the total variation norm between the distribution of the number of balls drawn with a given color and the Poisson distribution with the same mean are obtained. We then show that the distribution of the number of balls drawn with a given color has the same tail as that of the original number of balls. Finally, we establish explicit bounds between the two distributions when each ball is drawn with fixed probability p.

In a family, parameterized by θ, of non-negative random variables with finite, positive second moment, Taylor's law (TL) asserts that the population variance is proportional to a power of the population mean as θ varies: σ2 (θ) = a[μ(θ)]b, a > 0. TL, sometimes called fluctuation scaling, holds widely in science, probability theory, and stochastic processes. Here we report diverse examples of TL with b = 2 (equivalent to a constant coefficient of variation) arising from a difference of random variables in normed vector spaces of dimension 1 and larger. In these examples, we compute a exactly using, in some cases, a simple, new technique. These examples may prove useful in future models that involve differences of random variables, including models of the spatial distribution and migration of human populations.

In the fall of 1948 in my course on Least Squares in the Department of Mathematical Statistics at Columbia University (and in the spring in Correlation and Chi-Square), I was particularly impressed by one of the students— Gerald J. Lieberman. I was disappointed that this promising student left Columbia after one year, but it was not long until our paths met again. It is a pleasure to dedicate this paper to my colleague and close friend!

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.