4 deleted 106 characters in body

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.

EDIT: If $p(n)=1/(n+1)$ for every $n$, a martingale argument show that $(z_n)$ hits $0$ almost surely.

3 deleted 70 characters in body

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 componentif and only if $x_n=y_n$ for at least one integer $n$. . It happens that the process $(z_n)_n$ defined by $z_n=|x_n-y_n|$ is an irreducible Markov chain , hence the question is to know whether and that in some cases one can show that $(z_n)$ is recurrentor not.

If

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 the mean size of a step of $(z_n)$ at $z$ is asymptotically $-1/p$ E(z_{n+1}|z_n=z)-z\to-1/p$when$z\to\infty$hence$(z_n)$hits$0$almost surely, which means . This implies that there exists a path from$1$to$N$in the graph, almost surely, for every$N\ge2$. If the steps of$(z_n)$are not integrable E(z_{n+1}|z_n=z)$ is infinite (for instance if $p(n)=1/(n+1)$ for every $n\ge1$, hence $q(n)=1/(n(n+1))$), n\ge1$), more work is needed. EDIT: If$p(n)=1/(n+1)$for every$n$, a martingale argument show that$(z_n)$hits$0$almost surely. 2 added 106 characters in body 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, the vertices$1$and$N$are in the same connected component if and only if$x_n=y_n$for at least one integer$n$. It happens that the process$(z_n)_n$defined by$z_n=|x_n-y_n|$is an irreducible Markov chain, hence the question is to know whether$(z_n)$is recurrent or not. 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 the mean size of a step of$(z_n)$at$z$is asymptotically$-1/p$when$z\to\infty$hence$(z_n)$hits$0$almost surely, which means that there exists a path from$1$to$N$in the graph, almost surely, for every$N\ge2$. If the steps of$(z_n)$are not integrable (for instance if$p(n)=1/(n+1)$for every$n\ge1$, hence$q(n)=1/(n(n+1))$), more work is needed. EDIT: If$p(n)=1/(n+1)$for every$n$, a martingale argument show that$(z_n)$hits$0\$ almost surely.

1