# Random walks on infinite directed regular graphs

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$$.

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$$.