-
作者：Hayes, Thomas P.; Sinclair, Alistair
作者单位：Toyota Technological Institute - Chicago; University of California System; University of California Berkeley
摘要：We prove that any Markov chain that performs local, reversible updates on randomly chosen vertices of a bounded-degree graph necessarily has mixing time at least Omega (n log n), where n is the number of vertices. Our bound applies to the so-called Glauber dynamics that has been used extensively in algorithms for the Ising model, independent sets, graph colorings and other structures in computer science and statistical physics, and demonstrates that many of these algorithms are optimal up to c...
-
作者：Connor, Stephen B.; Kendall, Wilfrid S.
作者单位：University of Warwick
摘要：This paper generalizes the work of Kendall [Electron. Comm. Probab. 9 (2004) 140-15 11, which showed that perfect simulation, in the form of dominated coupling from the past, is always possible (although not necessarily practical) for geometrically ergodic Markov chains. Here, we consider the more general situation of positive recurrent chains and explore when it is possible to produce such a simulation algorithm for these chains. We introduce a class of chains which we name tame, for which we...
-
作者：Mischaikow, Konstantin; Wanner, Thomas
作者单位：Rutgers University System; Rutgers University New Brunswick; George Mason University
摘要：Homology has long been accepted as an important computable tool for quantifying complex structures. In many applications, these structures arise as nodal domains of real-valued functions and are therefore amenable only to a numerical study based on suitable discretizations. Such an approach immediately raises the question of how accurate the resulting homology computations are. In this paper, we present a probabilistic approach to quantifying the validity of homology computations for nodal dom...
-
作者：Massoulie, Laurent
摘要：In this article we provide a novel characterization of the proportionally fair bandwidth allocation of network capacities, in terms of the Fenchel-Legendre transform of the network capacity region. We use this characterization to prove stability (i.e., ergodicity) of network dynamics under proportionally fair sharing, by exhibiting a suitable Lyapunov function. Our stability result extends previously known results to a more general model including Markovian users routing. In particular, it imp...
-
作者：Tracy, Craig A.; Widom, Harold
作者单位：University of California System; University of California Davis; University of California System; University of California Santa Cruz
摘要：We consider the process of n Brownian excursions conditioned to be nonintersecting. We show the distribution functions for the top curve and the bottom curve are equal to Fredholm determinants whose kernel we give explicitly. In the simplest case, these determinants are expressible in terms of Painleve V functions. We prove that as n -> infinity, the distributional limit of the bottom curve is the Bessel process with parameter 1/2. (This is the Bessel process associated with Dyson's Brownian m...
-
作者：Mayer-Wolf, Eddy; Zakai, Moshe
作者单位：Technion Israel Institute of Technology; Technion Israel Institute of Technology
摘要：The model considered is that of signal plus white noise. Known connections between the noncausal filtering error and mutual information are combined with new ones involving the causal estimation error, in a general abstract setup. The results are shown to be invariant under a wide class of causality patterns; they are applied to the derivation of the causal estimation error of a Gaussian nonstationary filtering problem and to a multidimensional extension of the Yovits-Jackson formula.
-
作者：Hachem, Walid; Loubaton, Philippe; Najim, Jamal
作者单位：Universite Paris Saclay; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Universite Gustave-Eiffel; ESIEE Paris; Institut Polytechnique de Paris; Ecole Nationale des Ponts et Chaussees; Centre National de la Recherche Scientifique (CNRS); IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom Paris
摘要：Consider an N x n random matrix Y-n = (Y-ij(n)) where the entries are given by Y-ij(n) = sigma(ij)(n)/root n X-ij(n) the X-ij(n) being independent and identically distributed centered with unit variance and satisfying some mild moment assumption. Consider now a deterministic N x n matrix A(n) whose columns and rows are uniformly bounded in the Euclidean norm. Let Sigma(n) = Y-n + A(n). We prove in this article that there exists a deterministic N x N matrix-valued function T-n(z) analytic in C ...
-
作者：Yu, Feng
作者单位：University of Oxford
摘要：This paper deals with a model of sympatric speciation, that is, speciation in the absence of geographical separation, originally proposed by U. Dieckmarm and M. Doebeli in 1999. We modify their original model to obtain a Fleming-Viot type model and study its stationary distribution. We show that speciation may occur, that is, the stationary distribution puts most of the mass on a configuration that does not concentrate on the phenotype with maximum carrying capacity, if competition between phe...
-
作者：Gromoll, Christian; Kruk, Lukasz
作者单位：Stanford University; Maria Curie-Sklodowska University
摘要：This paper considers a GI/GI/1 processor sharing queue in which jobs have soft deadlines. At each point in time, the collection of residual service times and deadlines is modeled using a random counting measure on the right half-plane. The limit of this measure valued process is obtained under diffusion scaling and heavy traffic conditions and is characterized as a deterministic function of the limiting queue length process. As special cases, one obtains diffusion approximations for the lead t...
-
作者：Chi, Zhiyi
作者单位：University of Connecticut
摘要：Let (X-n, Y-n) be i.i.d. random vectors. Let W(x) be the partial sum of Yn just before that of X-n exceeds x > 0. Motivated by stochastic models for neural activity, uniform convergence of the form sup(c is an element of I) vertical bar a(c, x) Pr{W(x) >= cx} - 1 vertical bar = o(1), x -> infinity, is established for probabilities of large deviations, with a (c, x) a deterministic function and I an open interval. To obtain this uniform exact large deviations principle (LDP), we first establish...
