Return to Answer

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.

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.

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.

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.

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.

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.