-
作者：Lent, Janice; Mahmoud, Hosam M.
作者单位：George Washington University
摘要：Using the concept of a tree-growing'' search strategy, we prove that for most practical insertion sorting algorithms, the number of comparisons needed to sort n keys has asymptotically normal behavior. We prove and apply a sufficient condition for asymptotically normal behavior. The condition specifies a relationship between the variance of the number of comparisons and the rate of growth in height of the sequence of trees that the search strategy grows.''
-
作者：Penrose, Mathew D.
作者单位：Durham University
摘要：We prove that for continuum percolation in R-d, parametrized by the mean number y of points connected to the origin, as d -> infinity with y fixed the distribution of the number of points in the cluster at the origin converges to that of the total number of progeny of a branching process with a Poisson(y) offspring distribution. We also prove that for sufficiently large d the critical points for the existence of infinite occupied and vacant regions are distinct. Our results resolve conjectures...
-
作者：Chen, Hong
作者单位：University of British Columbia
摘要：Dupuis and Williams proved that a sufficient condition for the positive recurrence and the existence of a unique stationary distribution for a semimartingale reflecting Brownian motion in an orthant (SRBM) is that all solutions of an associated deterministic Skorohod problem are attracted to the origin. In this paper, we derive a sufficient condition under which we can construct an explicit linear Lyapunov function for the Skorohod problem. Thus, this implies a sufficient condition for the sta...
-
作者：Kirschenhofer, Peter; Prodinger, Helmut
作者单位：Technische Universitat Wien
摘要：In this tutorial, statistics on the number of people who tie for first place are considered. It is demonstrated that the so-called Rice's method from the calculus of finite differences is a very convenient tool both to rederive known results as well as to gain new ones with ease.
-
作者：Lund, Robert B.; Meyn, Sean P.; Tweedie, Richard L.
作者单位：University System of Georgia; University of Georgia; University of Illinois System; University of Illinois Urbana-Champaign; Colorado State University System; Colorado State University Fort Collins
摘要：Let {Phi(t), t >= 0} be a Markov process on the state space [0, infinity) that is stochastically ordered in its initial state. Examples of such processes include server workloads in queues, birth-and-death processes, storage and insurance risk processes and reflected diffusions. We consider the existence of a limiting probability measure pi or and an exponential convergence rate alpha > 0 such that lim (t -> infinity) e(alpha t)sup(Lambda)vertical bar P-x [Phi(t) is an element of A] - pi(A)ver...
-
作者：Hajek, Bruce
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：A set of nodes and a set of consumers are given, and to each consumer there corresponds a subset of the nodes. Each consumer has a demand, which is a load to be distributed among the nodes corresponding to the consumer. The load at a node is the sum of the loads placed on the node by all consumers. The load is balanced if no single consumer can shift some load from one node to another to reduce the absolute difference between the total loads at the two nodes. The model provides a setting to st...
-
作者：Rhee, Wansoo T.; Talagrand, Michel
作者单位：University System of Ohio; Ohio State University; University System of Ohio; Ohio State University; Sorbonne Universite; Centre National de la Recherche Scientifique (CNRS)
摘要：A packing of a collection of subintervals of [0,1] is a pairwise disjoint subcollection of the intervals; its wasted space is the measure of the set of points not covered by the packing. Consider n random intervals, I-1,...,I-n , chosen by selecting endpoints independently from the uniform distribution. We strengthen and simplify the results of Coffman, Poonen and Winkler, and we show that, for some universal constant K and for each t >= 1, with probability greater than or equal to 1 - 1/n(t),...
-
作者：Baccelli, Francois; Schmidt, Volker
作者单位：Ulm University
摘要：We give a Taylor series expansion for the mean value of the canonical stationary state variables of open (max, +)-linear stochastic systems with Poisson input process. Probabilistic expressions are derived for coefficients of all orders, under certain integrability conditions. The coefficients in the series expansion are the expectations of polynomials, known in explicit form, of certain random variables defined from the data of the (max, +)linear system. These polynomials are of independent c...
-
作者：Katehakis, Michael N.; Rothblum, Uriel G.
作者单位：Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick; Technion Israel Institute of Technology
摘要：We express Gittins indices for multi-armed bandit problems as Laurent expansions around discount factor 1. The coefficients of these expansions are then used to characterize stationary optimal policies when the optimality criteria are sensitive-discount optimality (otherwise known as Blackwell optimality), average-reward optimality and average-overtaking optimality. We also obtain bounds and derive optimality conditions for policies of a type that continue playing the same bandit as long as th...
-
作者：Ferrari, P. A.; Kesten, H.; Martinez, S.
作者单位：Universidade de Sao Paulo; Cornell University; Universidad de Chile
摘要：We prove that certain (discrete time) probabilistic automata which can be absorbed in a null state have a normalized quasi-stationary distribution (when restricted to the states other than the null state). We also show that the conditional distribution of these systems, given that they are not absorbed before time n, converges to an honest probability distribution; this limit distribution is concentrated on the configurations with only finitely many active or occupied sites. A simple example t...
