# First passage percolation for general graphs

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.

• The expectation of the shortest path distance is infinite (since with non-zero probability s is isolated). It is probably unintentional, but the intended question is not clear. – Boris Bukh Sep 22 '15 at 13:55

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.
• Isn't the length of the shortest path always at most 1 in this case, since you can just follow the 1 to $\infty$ edge with weight at most 1? $q_i$ is the probability that the length of the edge is 0, not that it is $\infty$. – Aaron Schild Sep 22 '15 at 6:59