Weak disorder asymptotics in the stochastic mean-field model of distance II

S. Bhamidi, R.W. Hofstad, van der, G. Hooghiemstra

Research output: Book/ReportReportAcademic


In this paper, we study the complete graph $K_n$ with $n$ vertices, where we attach an i.i.d.~weight to each of the $n(n-1)/2$ edges. We focus on the weight $W_n$ and the number of edges $H_n$ of the minimal weight path between vertex $1$ and vertex $n$. It is shown in \cite{BH09} that when the weights on the edges are independent and identically distributed (i.i.d.) with distribution equal to $E^s$, where $s>0$ is some parameter and $E$ has an exponential distribution with mean 1, then $H_n$ is asymptotically normal with asymptotic mean $s\log n$ and asymptotic variance $s^2\log n$. In this paper, we analyze the situation when the weights have distribution $E^{-s},\, s>0$, where the behavior of $H_n$ is markedly different as $H_n$ is a tight sequence of random variables. More precisely, we use Stein's method for Poisson approximation to show that, for almost all $s>0$, the hopcount $H_n$ converges in probability to the nearest integer of $s+1$ greater than or equal to 2, and identify the limiting distribution of the recentered and rescaled minimal weight. For a countable set of special $s$ values denoted by ${\cal S}=\{s_j\}_{j\geq 2}$, the hopcount $H_n$ takes on the values $j$ and $j+1$ each with \emph{positive} probability.
Original languageEnglish
Number of pages19
Publication statusPublished - 2010

Publication series

NamearXiv.org [math.PR]


Dive into the research topics of 'Weak disorder asymptotics in the stochastic mean-field model of distance II'. Together they form a unique fingerprint.

Cite this