Mostrando recursos 1 - 20 de 1.784

  1. Kac’s walk on $n$-sphere mixes in $n\log n$ steps

    Pillai, Natesh S.; Smith, Aaron
    Determining the mixing time of Kac’s random walk on the sphere $\mathrm{S}^{n-1}$ is a long-standing open problem. We show that the total variation mixing time of Kac’s walk on $\mathrm{S}^{n-1}$ is between $\frac{1}{2}n\log(n)$ and $200n\log(n)$ for all $n$ sufficiently large. Our bound is thus optimal up to a constant factor, improving on the best-known upper bound of $O(n^{5}\log(n)^{2})$ due to Jiang [Ann. Appl. Probab. 22 (2012) 1712–1727]. Our main tool is a “non-Markovian” coupling recently introduced by the second author in [Ann. Appl. Probab. 24 (2014) 114–130] for obtaining the convergence rates of certain high dimensional Gibbs samplers in continuous...

  2. Looking for vertex number one

    Frieze, Alan; Pegden, Wesley
    Given an instance of the preferential attachment graph $G_{n}=([n],E_{n})$, we would like to find vertex 1, using only “local” information about the graph; that is, by exploring the neighborhoods of small sets of vertices. Borgs et al. gave an algorithm which runs in time $O(\log^{4}n)$, which is local in the sense that at each step, it needs only to search the neighborhood of a set of vertices of size $O(\log^{4}n)$. We give an algorithm to find vertex 1, which w.h.p. runs in time $O(\omega\log n)$ and which is local in the strongest sense of operating only on neighborhoods of single...

  3. Stein’s method for steady-state diffusion approximations of $M/\mathit{Ph}/n+M$ systems

    Braverman, Anton; Dai, J. G.
    We consider $M/\mathit{Ph}/n+M$ queueing systems in steady state. We prove that the Wasserstein distance between the stationary distribution of the normalized system size process and that of a piecewise Ornstein–Uhlenbeck (OU) process is bounded by $C/\sqrt{\lambda}$, where the constant $C$ is independent of the arrival rate $\lambda$ and the number of servers $n$ as long as they are in the Halfin-Whitt parameter regime. For each integer $m>0$, we also establish a similar bound for the difference of the $m$th steady-state moments. For the proofs, we develop a modular framework that is based on Stein’s method. The framework has three components:...

  4. Stationary Eden model on Cayley graphs

    Antunović, Tonći; Procaccia, Eviatar B.
    We consider two stationary versions of the Eden model, on the upper half planar lattice, resulting in an infinite forest covering the half plane. Under weak assumptions on the weight distribution and by relying on ergodic theorems, we prove that almost surely all trees are finite. Using the mass transport principle, we generalize the result to Eden model in graphs of the form $G\times\mathbb{Z}_{+}$, where $G$ is a Cayley graph. This generalizes certain known results on the two-type Richardson model, in particular of Deijfen and Häggström in 2007 [Ann. Appl. Probab. 17 (2007) 1639–1656].

  5. Convex duality for stochastic singular control problems

    Bank, Peter; Kauppila, Helena
    We develop a general theory of convex duality for certain singular control problems, taking the abstract results by Kramkov and Schachermayer [Ann. Appl. Probab. 9 (1999) 904–950] for optimal expected utility from nonnegative random variables to the level of optimal expected utility from increasing, adapted controls. The main contributions are the formulation of a suitable duality framework, the identification of the problem’s dual functional as well as the full duality for the primal and dual value functions and their optimizers. The scope of our results is illustrated by an irreversible investment problem and the Hindy–Huang–Kreps utility maximization problem for incomplete...

  6. Degree sequence of random permutation graphs

    Bhattacharya, Bhaswar B.; Mukherjee, Sumit
    In this paper, we study the asymptotics of the degree sequence of permutation graphs associated with a sequence of random permutations. The limiting finite-dimensional distributions of the degree proportions are established using results from graph and permutation limit theories. In particular, we show that for a uniform random permutation, the joint distribution of the degree proportions of the vertices labeled $\lceil nr_{1}\rceil,\lceil nr_{2}\rceil,\ldots,\lceil nr_{s}\rceil$ in the associated permutation graph converges to independent random variables $D(r_{1}),D(r_{2}),\ldots,D(r_{s})$, where $D(r_{i})\sim\operatorname{Unif}(r_{i},1-r_{i})$, for $r_{i}\in[0,1]$ and $i\in\{1,2,\ldots,s\}$. Moreover, the degree proportion of the mid-vertex (the vertex labeled $n/2$) has a central limit theorem, and the minimum...

  7. Nucleation scaling in jigsaw percolation

    Gravner, Janko; Sivakoff, David
    Jigsaw percolation is a nonlocal process that iteratively merges connected clusters in a deterministic “puzzle graph” by using connectivity properties of a random “people graph” on the same set of vertices. We presume the Erdős–Rényi people graph with edge probability $p$ and investigate the probability that the puzzle is solved, that is, that the process eventually produces a single cluster. In some generality, for puzzle graphs with $N$ vertices of degrees about $D$ (in the appropriate sense), this probability is close to 1 or small depending on whether $pD\log N$ is large or small. The one dimensional ring and two...

  8. Universal limit theorems in graph coloring problems with connections to extremal combinatorics

    Bhattacharya, Bhaswar B.; Diaconis, Persi; Mukherjee, Sumit
    This paper proves limit theorems for the number of monochromatic edges in uniform random colorings of general random graphs. These can be seen as generalizations of the birthday problem (what is the chance that there are two friends with the same birthday?). It is shown that if the number of colors grows to infinity, the asymptotic distribution is either a Poisson mixture or a Normal depending solely on the limiting behavior of the ratio of the number of edges in the graph and the number of colors. This result holds for any graph sequence, deterministic or random. On the other...

  9. $\varepsilon$-Strong simulation for multidimensional stochastic differential equations via rough path analysis

    Blanchet, Jose; Chen, Xinyun; Dong, Jing
    Consider a multidimensional diffusion process $X=\{X(t):t\in [0,1]\}$. Let $\varepsilon>0$ be a deterministic, user defined, tolerance error parameter. Under standard regularity conditions on the drift and diffusion coefficients of $X$, we construct a probability space, supporting both $X$ and an explicit, piecewise constant, fully simulatable process $X_{\varepsilon}$ such that ¶ \[\sup_{0\leq t\leq1}\Vert X_{\varepsilon}(t)-X(t)\Vert_{\infty}<\varepsilon\] with probability one. Moreover, the user can adaptively choose $\varepsilon^{\prime}\in (0,\varepsilon )$ so that $X_{\varepsilon^{\prime}}$ (also piecewise constant and fully simulatable) can be constructed conditional on $X_{\varepsilon}$ to ensure an error smaller than $\varepsilon^{\prime}$ with probability one. Our construction requires a detailed study of continuity estimates of the Itô map...

  10. An epidemic in a dynamic population with importation of infectives

    Ball, Frank; Britton, Tom; Trapman, Pieter
    Consider a large uniformly mixing dynamic population, which has constant birth rate and exponentially distributed lifetimes, with mean population size $n$. A Markovian SIR (susceptible $\to$ infective $\to$ recovered) infectious disease, having importation of infectives, taking place in this population is analysed. The main situation treated is where $n\to\infty$, keeping the basic reproduction number $R_{0}$ as well as the importation rate of infectives fixed, but assuming that the quotient of the average infectious period and the average lifetime tends to 0 faster than $1/\log n$. It is shown that, as $n\to\infty$, the behaviour of the 3-dimensional process describing the evolution...

  11. Distances between nested densities and a measure of the impact of the prior in Bayesian statistics

    Ley, Christophe; Reinert, Gesine; Swan, Yvik
    In this paper, we propose tight upper and lower bounds for the Wasserstein distance between any two univariate continuous distributions with probability densities $p_{1}$ and $p_{2}$ having nested supports. These explicit bounds are expressed in terms of the derivative of the likelihood ratio $p_{1}/p_{2}$ as well as the Stein kernel $\tau_{1}$ of $p_{1}$. The method of proof relies on a new variant of Stein’s method which manipulates Stein operators. ¶ We give several applications of these bounds. Our main application is in Bayesian statistics: we derive explicit data-driven bounds on the Wasserstein distance between the posterior distribution based on a given prior...

  12. Maxima of a randomized Riemann zeta function, and branching random walks

    Arguin, Louis-Pierre; Belius, David; Harper, Adam J.
    A recent conjecture of Fyodorov–Hiary–Keating states that the maximum of the absolute value of the Riemann zeta function on a typical bounded interval of the critical line is $\exp \{\log \log T-\frac{3}{4}\log \log \log T+O(1)\}$, for an interval at (large) height $T$. In this paper, we verify the first two terms in the exponential for a model of the zeta function, which is essentially a randomized Euler product. The critical element of the proof is the identification of an approximate tree structure, present also in the actual zeta function, which allows us to relate the maximum to that of a...

  13. Nonequilibrium fluctuations of one-dimensional boundary driven weakly asymmetric exclusion processes

    Gonçalves, Patrícia; Landim, Claudio; Milanés, Aniura
    We consider one-dimensional, boundary driven, weakly asymmetric exclusion processes in contact with reservoirs at fixed density. For a general set of initial measures and by using a microscopic Cole–Hopf transformation, we derive the nonequilibrium fluctuations which are given by a generalized Ornstein–Uhlenbeck process.

  14. One-dimensional random walks with self-blocking immigration

    Birkner, Matthias; Sun, Rongfeng
    We consider a system of independent one-dimensional random walkers where new particles are added at the origin at fixed rate whenever there is no older particle present at the origin. A Poisson ansatz leads to a semi-linear lattice heat equation and predicts that starting from the empty configuration the total number of particles grows as $c\sqrt{t}\log t$. We confirm this prediction and also describe the asymptotic macroscopic profile of the particle configuration.

  15. Two-dimensional volume-frozen percolation: Exceptional scales

    van den Berg, Jacob; Nolin, Pierre
    We study a percolation model on the square lattice, where clusters “freeze” (stop growing) as soon as their volume (i.e., the number of sites they contain) gets larger than $N$, the parameter of the model. A model where clusters freeze when they reach diameter at least $N$ was studied in van den Berg, de Lima and Nolin [Random Structures Algorithms 40 (2012) 220–226] and Kiss [Probab. Theory Related Fields 163 (2015) 713–768]. Using volume as a way to measure the size of a cluster—instead of diameter—leads, for large $N$, to a quite different behavior (contrary to what happens on the...

  16. Polynomial convergence to equilibrium for a system of interacting particles

    Li, Yao; Young, Lai-Sang
    We consider a stochastic particle system in which a finite number of particles interact with one another via a common energy tank. Interaction rate for each particle is proportional to the square root of its kinetic energy, as is consistent with analogous mechanical models. Our main result is that the rate of convergence to equilibrium for such a system is ${\sim}t^{-2}$, more precisely it is faster than a constant times $t^{-2+\varepsilon}$ for any $\varepsilon>0$. A discussion of exponential vs. polynomial convergence for similar particle systems is included.

  17. Achieving nonzero information velocity in wireless networks

    Iyer, Srikanth; Vaze, Rahul
    In wireless networks, where each node transmits independently of other nodes in the network (the ALOHA protocol), the expected delay experienced by a packet until it is successfully received at any other node is known to be infinite for the signal-to-interference-plus-noise-ratio (SINR) model with node locations distributed according to a Poisson point process. Consequently, the information velocity, defined as the limit of the ratio of the distance to the destination and the time taken for a packet to successfully reach the destination over multiple hops, is zero, as the distance tends to infinity. A nearest neighbor distance based power control...

  18. Gaussian phase transitions and conic intrinsic volumes: Steining the Steiner formula

    Goldstein, Larry; Nourdin, Ivan; Peccati, Giovanni
    Intrinsic volumes of convex sets are natural geometric quantities that also play important roles in applications, such as linear inverse problems with convex constraints, and constrained statistical inference. It is a well-known fact that, given a closed convex cone $C\subset\mathbb{R}^{d}$, its conic intrinsic volumes determine a probability measure on the finite set $\{0,1,\ldots,d\}$, customarily denoted by $\mathcal{L}(V_{C})$. The aim of the present paper is to provide a Berry–Esseen bound for the normal approximation of $\mathcal{L}(V_{C})$, implying a general quantitative central limit theorem (CLT) for sequences of (correctly normalised) discrete probability measures of the type $\mathcal{L}(V_{C_{n}})$, $n\geq1$. This bound shows that,...

  19. Transition from Gaussian to non-Gaussian fluctuations for mean-field diffusions in spatial interaction

    Luçon, Eric; Stannat, Wilhelm
    We consider a system of $N$ disordered mean-field interacting diffusions within spatial constraints: each particle $\theta_{i}$ is attached to one site $x_{i}$ of a periodic lattice and the interaction between particles $\theta_{i}$ and $\theta_{j}$ decreases as $\vert x_{i}-x_{j}\vert^{-\alpha}$ for $\alpha\in[0,1)$. In a previous work [Ann. Appl. Probab. 24 (2014) 1946–1993], it was shown that the empirical measure of the particles converges in large population to the solution of a nonlinear partial differential equation of McKean–Vlasov type. The purpose of the present paper is to study the fluctuations associated to this convergence. We exhibit in particular a phase transition in the...

  20. Tracy–Widom distribution for the largest eigenvalue of real sample covariance matrices with general population

    Lee, Ji Oon; Schnelli, Kevin
    We consider sample covariance matrices of the form $\mathcal{Q}=(\Sigma^{1/2}X)(\Sigma^{1/2}X)^{*}$, where the sample $X$ is an $M\times N$ random matrix whose entries are real independent random variables with variance $1/N$ and where $\Sigma$ is an $M\times M$ positive-definite deterministic matrix. We analyze the asymptotic fluctuations of the largest rescaled eigenvalue of $\mathcal{Q}$ when both $M$ and $N$ tend to infinity with $N/M\to d\in(0,\infty)$. For a large class of populations $\Sigma$ in the sub-critical regime, we show that the distribution of the largest rescaled eigenvalue of $\mathcal{Q}$ is given by the type-1 Tracy–Widom distribution under the additional assumptions that (1) either the...

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.