-
作者：Grübel, R; Stefanoski, N
作者单位：Leibniz University Hannover
摘要：We investigate the distribution of the depth of a node containing a specific key or, equivalently, the number of steps needed to retrieve an item stored in a randomly grown binary search tree. Using a representation in terms of mixed and compounded standard distributions, we derive approximations by Poisson and mixed Poisson distributions; these lead to asymptotic normality results. We are particularly interested in the influence of the key value on the distribution of the node depth. Methodol...
-
作者：Strasser, E
作者单位：Technische Universitat Wien
摘要：The present paper deals with the characterization of no-arbitrage properties of a continuous semimartingale. The first main result, Theorem 2.1, extends the no-arbitrage criterion by Levental and Skorohod [Ann. Appl. Probab. 5 (1995) 906-925] from diffusion processes to arbitrary continuous semimartingales. The second main result, Theorem 2.4, is a characterization of a weaker notion of no-arbitrage in terms of the existence of supermartingale densities. The pertaining weaker notion of no-arbi...
-
作者：Zwart, B; Borst, S; Debicki, K
作者单位：Eindhoven University of Technology; Centrum Wiskunde & Informatica (CWI); University of Wroclaw
摘要：We investigate the tail asymptotics of the supremum of X(t) + Y(t) - ct, where X = {X(t), t greater than or equal to 0} and Y = {Y(t), t greater than or equal to 0} are two independent stochastic processes. We assume that the process Y has subexponential characteristics and that the process X is more regular in a certain sense than Y. A key issue examined in earlier studies is under what conditions the process X contributes to large values of the supremum only through its average behavior. The...
-
作者：Darling, RWR; Norris, JR
作者单位：University of Cambridge
摘要：The theme of this paper is the derivation of analytic formulae for certain large combinatorial structures. The formulae are obtained via fluid limits of pure jump-type Markov processes, established under simple conditions on the Laplace transforms of their Levy kernels. Furthermore, a related Gaussian approximation allows us to describe the randomness which may persist in the limit when certain parameters take critical values. Our method is quite general, but is applied here to vertex identifi...
-
作者：Baryshnikov, Y; Yukich, JE
作者单位：AT&T; Alcatel-Lucent; Lucent Technologies; Lehigh University
摘要：We establish Gaussian limits for general measures induced by binomial and Poisson point processes in d-dimensional space. The limiting Gaussian field has a covariance functional which depends on the density of the point process. The general results are used to deduce central limit theorems for measures induced by random graphs (nearest neighbor, Voronoi and sphere of influence graph), random sequential packing models (ballistic deposition and spatial birth-growth models) and statistics of germ...
-
作者：Arora, S; Kannan, R
作者单位：Princeton University; Yale University
摘要：Mixtures of Gaussian (or normal) distributions arise in a variety of application areas. Many heuristics have been proposed for the task of finding the component Gaussians given samples from the mixture, such as the EM algorithm, a local-search heuristic from Dempster, Laird and Rubin [J. Roy. Statist. Soc. Ser B 39 (1977) 1-38]. These do not provably run in polynomial time. We present the first algorithm that provably learns the component Gaussians in time that is polynomial in the dimension. ...
-
作者：Gapeev, PV
作者单位：Russian Academy of Sciences; V.A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences
摘要：The problem of disorder seeks to determine a stopping time which is as close as possible to the unknown time of disorder when the observed process changes its probability characteristics. We give a partial answer to this question for some special cases of Levy processes and present a complete solution of the Bayesian and variational problem for a compound Poisson process with exponential jumps. The method of proof is based on reducing the Bayesian problem to an integro-differential free-bounda...
-
作者：Ata, B; Kumar, S
作者单位：Northwestern University; Stanford University
摘要：We consider a class of open stochastic processing networks, with feedback routing and overlapping server capabilities, in heavy traffic. The networks we consider satisfy the so-called complete resource pooling condition and therefore have one-dimensional approximating Brownian control problems. We propose a simple discrete review policy for controlling such networks. Assuming 2 + epsilon moments on the interarrival times and processing times, we provide a conceptually simple proof of asymptoti...
-
作者：Dietz, Z; Sethuraman, S
作者单位：Tulane University; Iowa State University
摘要：Large deviation results are given for a class of perturbed nonhomogeneous Markov chains on finite state space which formally includes some stochastic optimization algorithms. Specifically, let {P-n} be a sequence of transition matrices on a finite state space which converge to a limit transition matrix P. Let {X-n} be the associated nonhomogeneous Markov chain where P, controls movement from time n - 1 to n. The main statements are a large deviation principle and bounds for additive functional...
-
作者：Dupuis, P; Wang, H
作者单位：Brown University
摘要：Importance sampling is a variance reduction technique for efficient estimation of rare-event probabilities by Monte Carlo. In standard importance sampling schemes, the system is simulated using an a priori fixed change of measure suggested by a large deviation lower bound analysis. Recent work, however, has suggested that such schemes do not work well in many situations. In this paper we consider dynamic importance sampling in the setting of uniformly recurrent Markov chains. By dynamic we mea...
