MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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 to [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?

-
Shelah has a series of papers titled Zero-one laws for graphs with edge probability decaying with distance. I haven't read any of them, but the title looks promising. – François G. Dorais Apr 21 2010 at 19:42
(I came across this by pure accident. Apologies if it turns out to be a dead end.) – François G. Dorais Apr 21 2010 at 19:44
This is true but slightly non-trivial (I mean the main question). If you haven't found this result in Shelah's papers or somewhere else already, I'll post the proof tomorrow. Now it is too late (and the comment window is too narrow...) – fedja Apr 24 2010 at 3:12
oh, I started to believe that it might be false, at least I am pretty sure that the path approach (also suggested in didier's answer) fails if p grows very slowly. So please, post the sketch of the proof! – domotorp Apr 24 2010 at 10:13

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.

-
 Nice trick, I think this is a perfect solution. – domotorp Apr 24 2010 at 14:22

Well, as it stands isn't the answer No? Just take $p(n) = 1$ if $n$ is even and $0$ if $n$ is odd. The graph will have at least two components consisting of the even and odd integers.

EDIT: retracted. Sorry. This is not (and cannot be made) decreasing. Missed that requirement.

-
p is supposed to be decreasing. – Gjergji Zaimi Apr 21 2010 at 19:00
True. My mistake. – Alon Amit Apr 21 2010 at 19:08

At least for some sequences $(p(n))$, the resulting graph is almost surely connected.

To show that the vertices $1$ and $N$ are linked by a path of open edges, build an auxiliary Markov chain $(x_n,y_n)_n$ as follows. Start from $x_0=1$ and $y_0=N$. If $x_n < y_n$, set $y_{n+1}=y_n$ and replace $x_n$ by $x_{n+1}=x_n+k$ with probability $q(k)$. Likewise, if $x_n > y_n$, set $x_{n+1}=x_n$ and replace $y_n$ by $y_{n+1}=y_n+k$ with probability $q(k)$.

Choose for $q(\cdot)$ the distribution of the least integer $k\ge1$ such that the edge $(x,x+k)$ is open in the graph, for any $x$, that is, $q(k)=p(k)(1-p(k-1))\cdots(1-p(1))$. The fact that the series $\sum_kp(k)$ diverges ensures that (indeed, is equivalent to the fact that) the measure $q$ has total mass $1$.

Now, if $x_n=y_n$ for at least one integer $n$, then the vertices $1$ and $N$ are in the same connected component. It happens that the process $(z_n)_n$ defined by $z_n=|x_n-y_n|$ is an irreducible Markov chain and that in some cases one can show that $(z_n)$ is recurrent.

For instance, if $(z_n)$ has integrable steps and if its drift at $z$ is uniformly negative for large enough values of $z$, Foster's criterion indicates that indeed $(z_n)$ is recurrent. An example of this case is when $p(n)=p$ for every $n$, with $p$ in $(0,1)$. Then $E(z_{n+1}|z_n=z)-z\to-1/p$ when $z\to\infty$ hence $(z_n)$ hits $0$ almost surely. This implies that there exists a path from $1$ to $N$ in the graph, almost surely, for every $N\ge2$.

If $E(z_{n+1}|z_n=z)$ is infinite (for instance if $p(n)=1/(n+1)$ for every $n\ge1$), more work is needed.

-
I think you follow a similar approach that I suggested, with taking the path I described, except that you do it for two starting points at the same time, this seems to be a better idea. I do not see why x_n=y_n would be equivalent to 1 and N being in the same component, but it is surely sufficient. Unfortunately I am really not an expert and I don't understand the notions that you use after. What is integrable step, recurrent, what does Foster's criterion say? Could you please give a reference where I can find these? – domotorp Apr 22 2010 at 8:14
1) You are solving the problem of whether there is a path between 1 and N that consists of two monotone subpaths; this is not exactly the same as whether there is a path between 1 and N. 2) If $\sum_{j<n} p(j)$ grows slower than $log(n)$, the steps of $z$ are not integrable. – Thorny Apr 22 2010 at 11:17
@Thorny: You are right about your 1), thanks. Answer edited. – Didier Piau Apr 22 2010 at 18:59
I was also referring to this when I wrote that I don't see the equivalence. Could anyone please give a reference to these? They were neither on wikipedia, nor on mathworld, and at other places even the statement was too complicated without knowing a bunch of other things. – domotorp Apr 22 2010 at 19:52
@domotorp: About recurrence/transience, you might try section 1.5 of the book available at "statslab.cam.ac.uk/~james/Markov/";. "(Lyapunov-)Foster criteria" is a loose name for a variety of drift conditions ensuring the recurrence or the transience of a given Markov chain; some of them are described at "math.ucsd.edu/~pfitz/downloads/courses/spring05/…;. – Didier Piau Apr 22 2010 at 20:22