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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.