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.



Connectedness of random distance graph on integers
All right. Here goes, as promised. We shall work with a big circle containing a huge number $N$ of points and a sequence of probabilities $p\_1,\dots,p\_L$ such that $\sum\_j p\_j=P$ is large (so we never connect points at the distance greater than $L$ but connect points at the distance $d\le L$ with probability $p\_d$). If $N\gg L$ and $p\_j<1$ for all $j$, the probability of a connected path going around the entire circle is extremely small, so the problem is essentially equivalent to the one on the line. I chose the circle just to make averaging tricks technically simple (otherwise one would have to justify some exchanges of limits, etc.). Fix $\delta>0$.


Our aim will be to show that with probability at least $1-2\delta$, we have $\sum\_{j\in E\_0} p\_{|j|}\ge P$ where $E\_0$ is the connected component of $0$ and integers are understood modulo $N$, provided that $P>P(\delta)$. This, clearly, implies the problem (just consider the connected component of $0$ in the subgraph with even vertices only; whatever it is, the edges going from odd vertices to even vertices are independent of it, so we get $0$ joined to $1$ with probability $1$ in the limiting line case with infinite sum of probabilities).


We shall call a point $x$ good if $\sum\_{y\in E\_x}p\_{|y-x|}\ge P$. We will call a connected component $E$ with $m$ points good if at least $(1-\delta)m$ its points are good. 


Fix $m$. Let's estimate the average number of points lying in the bad components. To this end, we need to sum over all bad $m$-point subsets $E$ the probabilities of the events that the subgraph with the set of vertices $E$ is connected and there are no edges going from $E$ elsewhere and then multiply this sum by $m$. For each fixed $E$ these two events are independent and, since $E$ is bad, there are at least $\delta m$ vertices in $E$ for which the probability to not be connected with a vertex outside $E$ is at most $e^{-P}$ (the total sum of probabilities of edges emanating from a vertex is $2P$ and only the sum $P$ can be killed by $E$). Thus, the second event has the probability at most $e^{-\delta P m}$ for every bad $E$ and it remains to estimate the sum of probabilities to be connected.


We shall expand this sum to all $m$-point subsets $E$. Now, the probability that subgraph with $m$ vertices is connected does not exceed the sum over all trees with the set of vertices $E$ of the probabilities of such trees to be present in the graph. Thus, we can sum the probabilities of all $m$-vertex trees instead. 


We need an efficient way to parametrize all $m$-trees. To this end, recall that each tree admits a route that goes over each edge exactly twice. Moreover, when constructing a tree, in this route one needs to specify only new edges, the returns are defined uniquely as the last edge traversed only once by the moment. Thus, each $m$ tree can be encoded as a starting vertex and a sequence of $m-1$ integer numbers (steps to the new vertex) interlaced with $m-1$ return commands. For instance, (7;3,2,return,-4,return,return) encodes the tree with vertices 7,10,12,6 and the edges 7--10, 10--12, 10--6. Well I feel a bit stupid explaining this all to a combinatorist like you...


Now when we sum over all such encodings, we effectively get $N$ (possibilities for the starting vertex) times the sum the products of probabilities over all sequences of $m-1$ integers multiplied by the number of possible encoding schemes telling us the positions of the return commands. (actually a bit less because not all sequences of integers result in a tree). Since there are fewer than $4^{m-1}$ encoding schemes, we get $4^{m-1}(2P)^{m-1}$ as a result. Thus the expected number of bad $m$-components is at most $N\cdot 4^{m-1}(2P)^{m-1}e^{-\delta Pm}$. Even if we multiply by $m$ (which is not really necessary because each tree is counted at least $m$ times according to the choice of the root) and add up over all $m\ge 1$, we still get less than $\delta N$ if $P$ is large. 


Now we see that the expected number of bad points is at most $2\delta N$ (on average at most $\delta N$ points lie in the bad components and the good components cannot contain more than $\delta N$ points by their definition). Due to rotational symmetry, we conclude that the probability of each particular point to be bad is at most $2\delta$.


The end.


