Connectedness of random distance graph on integers - MathOverflow

Connectedness of random distance graph on integers

2010-04-21T16:13:53Z

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?

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

Answer by Alon Amit for Connectedness of random distance graph on integers

2010-04-21T18:55:15Z

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.

Answer by Didier Piau for Connectedness of random distance graph on integers

2010-04-21T21:07:51Z

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.

Answer by fedja for Connectedness of random distance graph on integers

2010-04-24T13:25:43Z

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.