2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Boris Bukh Sep 22 '15 at 13:55
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Aaron Schild Sep 22 '15 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.