Random walks on infinite directed regular graphs

Question

Let us consider a directed graph $\Gamma=(V,E,s,t)$ ($V$ set of vertices, $E$ set of edges, $s,t: E \rightarrow V$ are the "source" and "target" maps).

Assume that $\Gamma$ is bi-regular, that is there are two integers $d_1 \geq 1$ and $d_2 \geq 1$ such that $|s^{-1}(v)|=d_1$ and $|t^{-1}(v)|=d_2$ for every $v \in D$. Assume that $\Gamma$ weakly connected (there is an undirected path relying any two vertices). And finally assume that $\Gamma$ has no forward-closed finite subset (i.e. if $S$ is a finite subset of $V$, there is an edge in $E$ with source in $S$ and target not in $S$). In particular $\Gamma$ is infinite.

Consider the standard discrete-time forward random walk on $\Gamma$, starting at $x \in V$: at time $0$ you are at $x$ with probability $1$; for any $n \geq 0$, at time $n+1$, conditional to being at $y$ at time $n$, your odds of being at any of the $d_1$ forward-neighbors of $y$ (i.e. $t(e)$ for $e \in E$, $s(e)=y$) is $1/d_1$.

Let $p^n_{x,y}$ be the probability of being at $y$ at time $n$.

Is it true that for every $y$, $p_n(x,y) \rightarrow 0$ as $n \rightarrow \infty$?

---

Here are some remarks. This question is related to Fedja's beautiful answer to this question. Fedja proves the result when $\Gamma$ is an undirected regular graph (seen as an undirected graph by replacing each undirected edge by two directed edges going both way). Unfortunately, I have not been able to extend his argument to my directed case.

The hypothesis that $\Gamma$ has no forward-closed finite subset is certainly necessary: If $S$ was such a subset, and $x \in S$, then you would be sure to stay in the finite set $S$ forever, so $\sum_{y \in S} {p^n_{x,y}} = 1$ and one of these $p^n_{x,y}$ at least can not tend to $0$.

The hypothesis that $|s^{-1}(v)|=d_1$ (or at least $s^{-1}(v)$ finite) for all $v$ is necessary to define the random walk, but that $|t^{-1}(v)|=d_2$ (or at least is finite) for all $v$ is also necessary for the theorem to be true. Without it, consider the graph with $V=\mathbb Z$, and for every $a \in \mathbb Z$, there is one directed edge from $a$ to $a+1$ and one directed edge from $a$ to $0$ (called the "speedy return" edge). Thus $|s^{-1}(a)|=2$ for every $a \in \mathbb Z$, but $|t^{-1}(0)|=\infty$. The probability $p^n_{0,0}$ is $\geq 1/2$ since every path that ends up with the "speedy return edge" goes from $0$ to $0$.

Answer 1

Here is a counterexample:

Let $G_1$ be the digraph with vertex set $\mathbb N$, two loops at $0$, an edge from $0$ to $1$, and for every $i \geq 1$ an edge from $i$ to $(i+1)$ and two parallel edges from $i$ to $(i-1)$. Let $G_2$ be any countable digraph in which every vertex has $2$ outgoing edges and $4$ incoming edges, and let $f \colon V(G_2) \to V(G_1)$ be such that $|f^{-1}(0)| = 0$ and $|f^{-1}(i)| = 1$ for every $i \geq 1$.

Let $G$ be the digraph obtained from $G_1 \uplus G_2$ by adding all edges from $v$ to $f(v)$. Then $G$ is bi-regular with $d_1 = 3$ and $d_2 = 4$. Moreover, $G$ is weakly connected and has no finite forward closed sets since every vertex has a forward edge connecting it to the forward ray in $G_1$.

The simple random walk on $G$ almost surely enters $G_1$ after finitely many steps (and remains in $G_1$ thereafter since there are no edges from $G_1$ to $G_2$). But the simple random walk on $G_1$ is just a biased random walk on $\mathbb N$ with bias towards $0$. This random walk is irreducible, aperiodic (because of the loops at $0$), and positive recurrent. Thus $\lim_{n \to \infty} p_n(x, i) = \mu(i)$ independently of the starting point $x$, where $\mu \neq 0$ is the invariant probability measure on $\mathbb N$.