First passage percolation for general graphs

Question

There have been many questions about the behavior of first-passage percolation on specific graphs. In particular, it seems like cliques, grids, random graphs, and ladders are well-studied. But I can't find much on general graphs. Rather than computing the distance explictly, I just want to show that the distance concentrates.

Note that the variance of a sum of independent Bernoulli random variables is always less than its expectation, so we get good concentration bounds even if the mean is small. More generally, consider a graph G and let the weights be independent (not necessarily i.d.) Bernoullis. For any two vertices s and t, does the shortest path distance between s and t have variance less than its mean as long as the distance is greater than 1? I am especially interested in the case where the Bernoullis are heavily biased towards 0.

Answer 1

No I think you can get basically any distribution you want. Suppose you have a distribution $(p_n)$ on the integers and assume it has unbounded support.

Define $q_n=p_n/\sum_{i\ge n}p_i$. Now take a graph with vertices $\{1,2,\ldots,\infty\}$. Join $i$ to $i+1$ by an edge labelled by a Bernoulli random variable with weight 1; and connect $i$ to $\infty$ with a Bernoulli($q_i$) weight.

You can check $1-q_n=\sum_{i\ge n+1}p_i / \sum_{i\ge n}p_i$. Now the probability that the shortest path joining $1$ to $\infty$ is of length $k$ is $(1-q_1)(1-q_2)\ldots (1-q_{k-1})q_k$. From the above formula (and telescoping), $(1-q_1)\ldots (1-q_{k-1})=\sum_{i\ge k}p_i$, so that $(1-q_1)\ldots (1-q_{k-1})q_k=p_k$.

If you don't like Bernoulli's with parameter 1, you can try Bernoulli's with parameter $1-\epsilon^n$. Nothing much changes.