-
作者：Kim, Jeong Han; Montenegro, Ravi; Peres, Yuval; Tetali, Prasad
作者单位：Yonsei University; National Institute for Mathematical Sciences (NIMS), Republic of Korea; Microsoft; University of Massachusetts System; University of Massachusetts Lowell; University System of Georgia; Georgia Institute of Technology
摘要：We show a Birthday Paradox for self-intersections of Markov chains with uniform stationary distribution. As an application, we analyze Pollard's Rho algorithm for finding the discrete logarithm in a cyclic group G and find that if the partition in the algorithm is given by a random oracle, then with high probability a collision occurs in Theta(root vertical bar G vertical bar) steps. Moreover, for the parallelized distinguished points algorithm on J processors we find that Theta(root vertical ...
-
作者：Kyprianou, A. E.; Pardo, J. C.; Rivero, V.
作者单位：University of Bath
摘要：Understanding the space time features of how a Levy process crosses a constant barrier for the first time, and indeed the last time, is a problem which is central to many models in applied probability such as queueing theory, financial and actuarial mathematics, optimal stopping problems, the theory of branching processes, to name but a few. In Doney and Kyprianou [Ann. Appl. Probab. 16 (2006) 91-106] a new quintuple law was established for a general Levy process at first passage below a fixed...
-
作者：Bramson, Maury; Dai, J. G.; Harrison, J. M.
作者单位：University of Minnesota System; University of Minnesota Twin Cities; University System of Georgia; Georgia Institute of Technology; Stanford University
摘要：Consider a semimartingale reflecting Brownian motion (SRBM) Z whose state space is the d-dimensional nonnegative orthant. The data for such a process are a drift vector theta, a nonsingular d x d covariance matrix Sigma, and a d x d reflection matrix R that specifies the boundary behavior of Z. We say that Z is positive recurrent, or stable, if the expected time to hit an arbitrary open neighborhood of the origin is finite for every starting state. In dimension d = 2, necessary and sufficient ...
-
作者：Dembo, Amir; Montanari, Andrea
作者单位：Stanford University; Stanford University; Stanford University
摘要：We consider ferromagnetic Ising models on graphs that converge locally to trees. Examples include random regular graphs with bounded degree and uniformly random graphs with bounded average degree. We prove that the cavity prediction for the limiting free energy per spin is correct for any positive temperature and external field. Further, local marginals can be approximated by iterating a set of mean field (cavity) equations. Both results are achieved by proving the local convergence of the Bol...
-
作者：Goldstein, Larry; Penrose, Mathew D.
作者单位：University of Southern California; University of Bath
摘要：We give error bounds which demonstrate optimal rates of convergence in the CLT for the total covered volume and the number of isolated shapes, for germ-grain models with fixed grain radius over a binomial point process of n points in a toroidal spatial region of volume n. The proof is based on Stein's method via size-biased couplings.
-
作者：Armendariz, Ines
摘要：We introduce a one-dimensional stochastic system where particles perform independent diffusions and interact through pairwise coagulation events, which occur at a nontrivial rate upon collision. Under appropriate conditions on the diffusion coefficients, the coagulation rates and the initial distribution of particles, we derive a spatially inhomogeneous version of the mass flow equation as the particle number tends to infinity. The mass flow equation is in one-to-one correspondence with Smoluc...
-
作者：Barrera, Javiera; Fontbona, Joaquin
作者单位：Universidad Adolfo Ibanez; Universidad de Chile; Universidad de Chile
摘要：We explicitly compute the limiting transient distribution of the search-cost in the move-to-front Markov chain when the number of objects tends to infinity, for general families of deterministic or random request rates. Our techniques are based on a law of large numbers for random partitions, a scaling limit that allows us to exactly compute limiting expectation of empirical functionals of the request probabilities of objects. In particular, we show that the limiting search-cost can be split a...
-
作者：Dolera, Emanuele; Regazzini, Eugenio
作者单位：University of Pavia
摘要：In Dolera, Gabetta and Regazzini [Ann. Appl. Probab. 19 (2009) 186-201] it is proved that the total variation distance between the solution f(., t) of Kac's equation and the Gaussian density (0, sigma(2)) has an upper bound which goes to zero with an exponential rate equal to 1/4 as t -> +infinity. In the present paper, we determine a lower bound which decreases exponentially to zero with this same rate, provided that a suitable symmetrized form of f(0) has nonzero fourth cumulant kappa(4). Mo...
-
作者：Haas, Benedicte
作者单位：Universite PSL; Universite Paris-Dauphine
摘要：The subject of this paper is a fragmentation equation with nonconservative solutions, some mass being lost to a dust of zero-mass particles as a consequence of an intensive splitting. Under some assumptions of regular variation on the fragmentation rate, we describe the large time behavior of solutions. Our approach is based on probabilistic tools: the solutions to the fragmentation equation are constructed via nonincreasing self-similar Markov processes that continuously reach 0 in finite tim...
-
作者：Del Moral, Pierre; Doucet, Arnaud
作者单位：Universite de Bordeaux; University of British Columbia; University of British Columbia; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; Universite de Bordeaux; Centre National de la Recherche Scientifique (CNRS); Inria
摘要：We present a new class of interacting Markov chain Monte Carlo algorithms for solving numerically discrete-time measure-valued equations. The associated stochastic processes belong to the class of self-interacting Markov chains. In contrast to traditional Markov chains, their time evolutions depend on the occupation measure of their past values. This general methodology allows us to provide a natural way to sample from a sequence of target probability measures of increasing complexity. We deve...
