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](https://mathoverflow.net/questions/91188/return-probabilities-for-random-walks-on-infinite-schreier-graphs). 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$.



Random walks on infinite directed regular graphs
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$.


