Mostrando recursos 1 - 20 de 81

  1. Random cluster dynamics for the Ising model is rapidly mixing

    Guo, Heng; Jerrum, Mark
    We show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at $q=2$ on an arbitrary $n$-vertex graph is bounded by a polynomial in $n$. As a consequence, the Swendsen–Wang algorithm for the ferromagnetic Ising model at any temperature also has a polynomial mixing time bound.

  2. Phase transitions in the one-dimensional Coulomb gas ensembles

    Turova, Tatyana S.
    We consider the system of particles on a finite interval with pairwise nearest neighbours interaction and external force. This model was introduced by Malyshev [Probl. Inf. Transm. 51 (2015) 31–36] to study the flow of charged particles on a rigorous mathematical level. It is a simplified version of a 3-dimensional classical Coulomb gas model. We study Gibbs distribution at finite positive temperature extending recent results on the zero temperature case (ground states). We derive the asymptotics for the mean and for the variances of the distances between the neighbouring charges. We prove that depending on the strength of the external...

  3. A random matrix approach to neural networks

    Louart, Cosme; Liao, Zhenyu; Couillet, Romain
    This article studies the Gram random matrix model $G=\frac{1}{T}\Sigma^{{\mathsf{T}}}\Sigma$, $\Sigma=\sigma(WX)$, classically found in the analysis of random feature maps and random neural networks, where $X=[x_{1},\ldots,x_{T}]\in\mathbb{R}^{p\times T}$ is a (data) matrix of bounded norm, $W\in\mathbb{R}^{n\times p}$ is a matrix of independent zero-mean unit variance entries and $\sigma:\mathbb{R}\to\mathbb{R}$ is a Lipschitz continuous (activation) function—$\sigma(WX)$ being understood entry-wise. By means of a key concentration of measure lemma arising from nonasymptotic random matrix arguments, we prove that, as $n,p,T$ grow large at the same rate, the resolvent $Q=(G+\gamma I_{T})^{-1}$, for $\gamma>0$, has a similar behavior as that met in sample covariance matrix models, involving...

  4. Uniqueness and propagation of chaos for the Boltzmann equation with moderately soft potentials

    Xu, Liping
    We prove a strong/weak stability estimate for the 3D homogeneous Boltzmann equation with moderately soft potentials [$\gamma\in(-1,0)$] using the Wasserstein distance with quadratic cost. This in particular implies the uniqueness in the class of all weak solutions, assuming only that the initial condition has a finite entropy and a finite moment of sufficiently high order. We also consider the Nanbu $N$-stochastic particle system, which approximates the weak solution. We use a probabilistic coupling method and give, under suitable assumptions on the initial condition, a rate of convergence of the empirical measure of the particle system to the solution of the...

  5. The sample size required in importance sampling

    Chatterjee, Sourav; Diaconis, Persi
    The goal of importance sampling is to estimate the expected value of a given function with respect to a probability measure $\nu$ using a random sample of size $n$ drawn from a different probability measure $\mu$. If the two measures $\mu$ and $\nu$ are nearly singular with respect to each other, which is often the case in practice, the sample size required for accurate estimation is large. In this article, it is shown that in a fairly general setting, a sample of size approximately $\exp(D(\nu\parallel\mu))$ is necessary and sufficient for accurate estimation by importance sampling, where $D(\nu\parallel\mu)$ is the Kullback–Leibler...

  6. Sharp thresholds for contagious sets in random graphs

    Angel, Omer; Kolesnik, Brett
    For fixed $r\geq2$, we consider bootstrap percolation with threshold $r$ on the Erdős–Rényi graph $\mathcal{G}_{n,p}$. We identify a threshold for $p$ above which there is with high probability a set of size $r$ that can infect the entire graph. This improves a result of Feige, Krivelevich and Reichman, which gives bounds for this threshold, up to multiplicative constants. ¶ As an application of our results, we obtain an upper bound for the threshold for $K_{4}$-percolation on $\mathcal{G}_{n,p}$, as studied by Balogh, Bollobás and Morris. This bound is shown to be asymptotically sharp in subsequent work. ¶ These thresholds are closely related to...

  7. A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs

    Fountoulakis, Nikolaos; Kang, Mihyun; Koch, Christoph; Makai, Tamás
    A bootstrap percolation process on a graph with infection threshold $r\ge1$ is a dissemination process that evolves in time steps. The process begins with a subset of infected vertices and in each subsequent step every uninfected vertex that has at least $r$ infected neighbours becomes infected and remains so forever. ¶ Critical phenomena in bootstrap percolation processes were originally observed by Aizenman and Lebowitz in the late 1980s as finite-volume phase transitions in $\mathbb{Z}^{d}$ that are caused by the accumulation of small local islands of infected vertices. They were also observed in the case of dense (homogeneous) random graphs by Janson...

  8. Spectral gap of random hyperbolic graphs and related parameters

    Kiwi, Marcos; Mitsche, Dieter
    Random hyperbolic graphs have been suggested as a promising model of social networks. A few of their fundamental parameters have been studied. However, none of them concerns their spectra. We consider the random hyperbolic graph model, as formalized by [Automata, Languages, and Programming—39th International Colloquium—ICALP Part II. (2012) 573–585 Springer], and essentially determine the spectral gap of their normalized Laplacian. Specifically, we establish that with high probability the second smallest eigenvalue of the normalized Laplacian of the giant component of an $n$-vertex random hyperbolic graph is at least $\Omega(n^{-(2\alpha-1)}/D)$, where $\frac{1}{2}<\alpha<1$ is a model parameter and $D$ is the network...

  9. Zooming in on a Lévy process at its supremum

    Ivanovs, Jevgenijs
    Let $M$ and $\tau$ be the supremum and its time of a Lévy process $X$ on some finite time interval. It is shown that zooming in on $X$ at its supremum, that is, considering $((X_{\tau+t\varepsilon}-M)/a_{\varepsilon})_{t\in\mathbb{R}}$ as $\varepsilon\downarrow0$, results in $(\xi_{t})_{t\in\mathbb{R}}$ constructed from two independent processes having the laws of some self-similar Lévy process $\widehat{X}$ conditioned to stay positive and negative. This holds when $X$ is in the domain of attraction of $\widehat{X}$ under the zooming-in procedure as opposed to the classical zooming out [Trans. Amer. Math. Soc. 104 (1962) 62–78]. As an application of this result, we establish a limit...

  10. Reflected backward stochastic differential equations with resistance

    Qian, Zhongmin; Xu, Mingyu
    In this article, we study a class of reflected backward stochastic differential equations (introduced in El Karoui et al. [Ann. Probab. 25 (1997) 702–737], RBSDE for short) with nonlinear resistance by means of Skorohod’s equation. The advantage of this approach lies in its pathwise nature and, therefore, provides additional information about solutions of RBSDE. As an application of our approach, we will consider reflected backward problems with resistance as well. This class of RBSDEs possess significance in the super-hedging with wealth constraint.

  11. A large scale analysis of unreliable stochastic networks

    Aghajani, Reza; Robert, Philippe; Sun, Wen
    The problem of reliability of a large distributed system is analyzed via a new mathematical model. A typical framework is a system where a set of files are duplicated on several data servers. When one of these servers breaks down, all copies of files stored on it are lost. In this way, repeated failures may lead to losses of files. The efficiency of such a network is directly related to the performances of the mechanism used to duplicate files on servers. In this paper, we study the evolution of the network using a natural duplication policy giving priority to the...

  12. On the stability and the uniform propagation of chaos properties of Ensemble Kalman–Bucy filters

    Del Moral, P.; Tugaut, J.
    The ensemble Kalman filter is a sophisticated and powerful data assimilation method for filtering high dimensional problems arising in fluid mechanics and geophysical sciences. This Monte Carlo method can be interpreted as a mean-field McKean–Vlasov-type particle interpretation of the Kalman–Bucy diffusions. In contrast to more conventional particle filters and nonlinear Markov processes, these models are designed in terms of a diffusion process with a diffusion matrix that depends on particle covariance matrices. ¶ Besides some recent advances on the stability of nonlinear Langevin-type diffusions with drift interactions, the long-time behaviour of models with interacting diffusion matrices and conditional distribution interaction functions...

  13. Spatial Gibbs random graphs

    Mourrat, Jean-Christophe; Valesin, Daniel
    Many real-world networks of interest are embedded in physical space. We present a new random graph model aiming to reflect the interplay between the geometries of the graph and of the underlying space. The model favors configurations with small average graph distance between vertices, but adding an edge comes at a cost measured according to the geometry of the ambient physical space. In most cases, we identify the order of magnitude of the average graph distance as a function of the parameters of the model. As the proofs reveal, hierarchical structures naturally emerge from our simple modeling assumptions. Moreover, a...

  14. On directional derivatives of Skorokhod maps in convex polyhedral domains

    Lipshutz, David; Ramanan, Kavita
    The study of both sensitivity analysis and differentiability of the stochastic flow of a reflected process in a convex polyhedral domain is challenging due to the abrupt change in the nature of the dynamics at the boundary and is further complicated because the boundary is not smooth. These difficulties can be addressed by studying directional derivatives of an associated extended Skorokhod map, which is a deterministic mapping that takes an unconstrained path to a suitably reflected or constrained version. In this work, we develop an axiomatic framework for the analysis of directional derivatives of a large class of Lipschitz continuous...

  15. The shape of multidimensional Brunet–Derrida particle systems

    Berestycki, Nathanaël; Zhao, Lee Zhuo
    We introduce particle systems in one or more dimensions in which particles perform branching Brownian motion and the population size is kept constant equal to $N>1$, through the following selection mechanism: at all times only the $N$ fittest particles survive, while all the other particles are removed. Fitness is measured with respect to some given score function $s:\mathbb{R}^{d}\to\mathbb{R}$. For some choices of the function $s$, it is proved that the cloud of particles travels at positive speed in some possibly random direction. In the case where $s$ is linear, we show under some mild assumptions that the shape of the...

  16. Law of large numbers for the largest component in a hyperbolic model of complex networks

    Fountoulakis, Nikolaos; Müller, Tobias
    We consider the component structure of a recent model of random graphs on the hyperbolic plane that was introduced by Krioukov et al. The model exhibits a power law degree sequence, small distances and clustering, features that are associated with so-called complex networks. The model is controlled by two parameters $\alpha$ and $\nu$ where, roughly speaking, $\alpha$ controls the exponent of the power law and $\nu$ controls the average degree. Refining earlier results, we are able to show a law of large numbers for the largest component. That is, we show that the fraction of points in the largest component...

  17. Disorder and wetting transition: The pinned harmonic crystal in dimension three or larger

    Giacomin, Giambattista; Lacoin, Hubert
    We consider the lattice Gaussian free field in $d+1$ dimensions, $d=3$ or larger, on a large box (linear size $N$) with boundary conditions zero. On this field, two potentials are acting: one, that models the presence of a wall, penalizes the field when it enters the lower half space and one, the pinning potential, rewards visits to the proximity of the wall. The wall can be soft, that is, the field has a finite penalty to enter the lower half-plane, or hard, when the penalty is infinite. In general, the pinning potential is disordered and it gives on average a...

  18. Limit theorems for integrated local empirical characteristic exponents from noisy high-frequency data with application to volatility and jump activity estimation

    Jacod, Jean; Todorov, Viktor
    We derive limit theorems for functionals of local empirical characteristic functions constructed from high-frequency observations of Itô semimartingales contaminated with noise. In a first step, we average locally the data to mitigate the effect of the noise, and then in a second step, we form local empirical characteristic functions from the pre-averaged data. The final statistics are formed by summing the local empirical characteristic exponents over the observation interval. The limit behavior of the statistics is governed by the observation noise, the diffusion coefficient of the Itô semimartingale and the behavior of its jump compensator around zero. Different choices for...

  19. BSDEs with mean reflection

    Briand, Philippe; Elie, Romuald; Hu, Ying
    In this paper, we study a new type of BSDE, where the distribution of the $Y$-component of the solution is required to satisfy an additional constraint, written in terms of the expectation of a loss function. This constraint is imposed at any deterministic time $t$ and is typically weaker than the classical pointwise one associated to reflected BSDEs. Focusing on solutions $(Y,Z,K)$ with deterministic $K$, we obtain the well-posedness of such equation, in the presence of a natural Skorokhod-type condition. Such condition indeed ensures the minimality of the enhanced solution, under an additional structural condition on the driver. Our results...

  20. A Skorokhod map on measure-valued paths with applications to priority queues

    Atar, Rami; Biswas, Anup; Kaspi, Haya; Ramanan, Kavita
    The Skorokhod map on the half-line has proved to be a useful tool for studying processes with nonnegativity constraints. In this work, we introduce a measure-valued analog of this map that transforms each element $\zeta$ of a certain class of càdlàg paths that take values in the space of signed measures on $[0,\infty)$ to a càdlàg path that takes values in the space of nonnegative measures on $[0,\infty)$ in such a way that for each $x>0$, the path $t\mapsto\zeta_{t}[0,x]$ is transformed via a Skorokhod map on the half-line, and the regulating functions for different $x>0$ are coupled. We establish regularity...

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.