-
作者：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...
-
作者：Chan, Hock Peng; Lai, Tze Leung
作者单位：National University of Singapore; Stanford University
摘要：Large deviation theory has provided important clues for the choice of importance sampling measures for Monte Carlo evaluation of exceedance probabilities. However, Glasserman and Wang [Ann. Appl. Probab. 7 (1997) 731-746] have given examples in which importance sampling measures that are consistent with large deviations can perform much worse than direct Monte Carlo. We address this problem by using certain mixtures of exponentially twisted measures for importance sampling. Their asymptotic op...
-
作者：Connor, Stephen B.; Kendall, Wilfrid S.
作者单位：University of Warwick
-
作者：Hairer, M.; Stuart, A. M.; Voss, J.
作者单位：University of Warwick
摘要：In many applications, it is important to be able to sample paths of SDEs conditional on observations of various kinds. This paper studies SPDEs which solve such sampling problems. The SPDE may be viewed as an infinite-dimensional analogue of the Langevin equation used in finite-dimensional sampling. In this paper, conditioned nonlinear SDEs, leading to nonlinear SPDEs for the sampling, are studied. In addition, a class of preconditioned SPDEs is studied, found by applying a Green's operator to...
-
作者：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...
-
作者：Jeanblanc, Monique; Kloeppel, Susanne; Miyahara, Yoshio
作者单位：Universite Paris Saclay; Nagoya City University; Technische Universitat Wien
摘要：Let L be a multidimensional Levy process under P in its own filtration. The p-minimal martingale measure Q(q) is defined as that equivalent local martingale measure for 8 (L) which minimizes the f(q)-divergence E[(dQ/dp)(q)] for fixed q epsilon (-infinity, 0) boolean OR (1, infinity). We give necessary and sufficient conditions for the existence of Qq and an explicit formula for its density. For q = 2, we relate the sufficient conditions to the structure condition and discuss when the former a...
-
作者：Kargin, Vladislav
作者单位：New York University
摘要：Let S-N be the sum of vector-valued functions defined on a finite Markov chain. An analogue of the Bemstein-Hoeffding inequality is derived for the probability of large deviations Of SN and relates the probability to the spectral gap of the Markov chain. Examples suggest that this inequality is better than alternative inequalities if the chain has a sufficiently large spectral gap and the function is high-dimensional.
-
作者：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...
-
作者：Mairesse, Jean; Matheus, Frederic
作者单位：Universite Paris Cite; Centre National de la Recherche Scientifique (CNRS)
摘要：Consider the braid group B-3 = < a, b vertical bar aba = bab > and the nearest neighbor random walk defined by a probability v with support {a, a(-1), b, b(-1)}. The rate of escape of the walk is explicitly expressed in function of the unique solution of a set of eight polynomial equations of degree three over eight indeterminates. We also explicitly describe the harmonic measure of the induced random walk on B-3 quotiented by its center. The method and results apply, mutatis mutandis, to near...
-
作者：MacPhee, Iain; Menshikov, Mikhail; Petritis, Dimitri; Popov, Serguei
作者单位：Durham University; Universidade de Sao Paulo; Universite de Rennes
摘要：We study a model of a polling system, that is, a collection of d queues with a single server that switches from queue to queue. The service time distribution and arrival rates change randomly every time a queue is emptied. This model is mapped to a mathematically equivalent model of a random walk with random choice of transition probabilities, a model which is of independent interest. All our results are obtained using methods from the constructive theory of Markov chains. We determine conditi...
