Skip to main content

Connectedness of random distance graph on integers

This is not my field, a friend needs the answer for the following question. Suppose we have a decreasing probability function, $p: N \rightarrow [0,1]$ such that $sum_n p(n) = \infty$. Take the graph where we connect two integers at distance d with probability $p(d)$. Will this graph be connected with probability one?

I see that if the sum is convergent, then we almost surely have an isolated vertex (unless $p(1)=1$), so this would be "sharp". One possible approach would be to take the path that starts from the origin and if it is at n after some steps, then next goes to the smallest number that is bigger than $n$ and is connected to $n$ and to show that this path has a positive density with probability one. Is this second statement true?

I am sure that these are easy questions for anyone who knows about this.

domotorp
  • 19k
  • 3
  • 57
  • 127