-
作者：Ganesh, AJ; O'Connell, N
作者单位：University of London; Birkbeck University London; Hewlett-Packard
摘要：If a FIFO queue is fed by several input streams that; jointly satisfy a sample path large deviation principle (LDP) with linear geodesics, then the cumulative departures (up to a large time) also satisfy the LDP with a rate function which depends in a relatively simple way on the rate function corresponding to the inputs: this was demonstrated in a recent paper by the second author. It; suggests the possibility of an iterative scheme which would allow one to determine the large deviation behav...
-
作者：Bai, ZD; Chao, CC; Hwang, HK; Liang, WQ
作者单位：National University of Singapore; Academia Sinica - Taiwan; National Sun Yat Sen University
摘要：We derive a general asymptotic formula for the variance of the number of maxima in a set of independent and identically distributed random vectors in R-d, where the components of each vector are independently and continuously distributed. Applications of the results to algorithmic analysis are also indicated.
-
作者：Burdzy, K; Khoshnevisan, D
作者单位：University of Washington; University of Washington Seattle; Utah System of Higher Education; University of Utah
摘要：Let D be the Wiener sausage of width epsilon around two-sided Brownian motion. The components of two-dimensional reflected Brownian motion in D converge to one-dimensional Brownian motion and iterated Brownian motion, respectively, as epsilon goes to 0.
-
作者：Fontes, LRG; Isopi, M; Kohayakawa, Y; Picco, P
作者单位：Universidade de Sao Paulo; Sapienza University Rome; Aix-Marseille Universite; Centre National de la Recherche Scientifique (CNRS)
摘要：We derive upper and lower bounds for the spectral gap of the random energy model under Metropolis dynamics which are sharp in exponential order. They are based on the Variational characterization of the gap. For the lower bound, a Poincare inequality derived by Diaconis and Stroock is used. The scaled asymptotic expression is a linear function of the temperature. The corresponding function for a global version of the dynamics exhibits phase transition instead. We also study the dependence of l...
-
作者：Holroyd, AE
作者单位：University of Cambridge
摘要：We consider a percolation configuration on a general lattice in which edges are included independently with probability p. We study the rigidity properties of the resulting configuration, in the sense of generic rigidity in d dimensions. We give a mathematically rigorous treatment of the problem, starting with a definition of an infinite rigid component. We prove that, for a broad class of lattices, there exists an infinite rigid component for some p strictly below unity. For the particular ca...
-
作者：Lezaud, P
作者单位：Universite de Toulouse; Universite Toulouse III - Paul Sabatier
摘要：This paper develops bounds on the distribution function of the empirical mean for irreducible finite-state Markov chains. One approach, explored by Gillman, reduces this problem to bounding the largest eigenvalue of a perturbation of the transition matrix for the Markov chain. By using estimates on eigenvalues given in Kato's book Perturbation Theory for Linear Operators, we simplify the proof of Gillman and extend it to nonreversible finite-state Markov chains and continuous time. We also set...
-
作者：Lyons, R; Zumbrun, K
作者单位：Indiana University System; Indiana University Bloomington
摘要：We study the class of tree-growing search strategies introduced by Lent and Mahmoud, searches for which data are stored in a deterministic sequence of tree structures (e.g., linear search in forward order). Specifically, we study the conditions under which the number of comparisons needed to sort a sequence of randomly ordered numbers is asymptotically normal. Our main result is a sufficient condition for normality in terms of the growth rate of tree height alone; this condition is easily comp...
-
作者：Ciucu, M
作者单位：Institute for Advanced Study - USA
摘要：We consider the following problem. A deck of 2n cards labeled consecutively from 1 on top to 2n on bottom is face down on the table. The deck is given k dovetail shuffles and placed back on the table, face down. A guesser tries to guess at the cards one at a time, starting from top. The identity of the card guessed at is not revealed, nor is the guesser told whether a particular guess was correct or not. The goal is to maximize the number of correct guesses. We show that, for k greater than or...
-
作者：Schonmann, RH; Tanaka, NI
作者单位：University of California System; University of California Los Angeles; Universidade de Sao Paulo
摘要：We study patterns of the phase diagram of ferromagnetic Ising models on graphs under an external magnetic field. We provide an example of a tree with only two types of vertices on which for a range of values of the external field there is a unique Gibbs distribution at low enough and at high enough temperatures, while at intermediate temperatures there is phase coexistence (in other words, a reentrance transition takes place).
-
作者：Pelletier, M
作者单位：Universite Gustave-Eiffel
摘要：We study convergence rates of R-d-valued algorithms, especially in the case of multiple targets and simulated annealing. We precise, for example, the convergence rate of simulated annealing algorithms, whose weak convergence to a distribution concentrated on the potential's minima had been established by Gelfand and Mitter or by Hwang and Sheu.
