Mathematics – Probability
Scientific paper
2010-09-21
Mathematics
Probability
19 pages
Scientific paper
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.
Bhamidi Shankar
der Hofstad Remco van
Hooghiemstra Gerard
No associations
LandOfFree
Weak disorder in the stochastic mean-field model of distance II does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Weak disorder in the stochastic mean-field model of distance II, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Weak disorder in the stochastic mean-field model of distance II will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-697307