# Probabilities of a random walk exiting a set

Let $F$ be a finite connected set in a graph (soon to be the Cayley graph of a group) and $\mathrm{Ex}_x^F$ be the function on the vertices in $F^c$ which are neighbour to vertices in $F$ defined as follow $\mathrm{Ex}_x^F(y)$ is the probability that the first time a random walker starting at $x$ exits $F$ is through $y$. To make sure this is defined, suppose the graph is transient.

$\textbf{Question}$: Assume the (transient) graph is the Cayley graph of an amenable group (for some finite generating set). Let $s$ be a neighbour of $e$. Does there exist a sequence of finite connected sets (containing $e$ and $s$) $\{F_i\}$ so that $\mathrm{Ex}_e^{F_i}(y) - \mathrm{Ex}_s^{F_i}(y) \overset{i}{\to} 0$ in $\ell^1$ norm?

The hypothesis about amenability is motivated by

• the above is clearly false in the free group and most probably false in any hyperbolic group.
• its more plausible as the Cayley graph of amenable groups (by Kesten) are those where $P^{(n)}(e,e)^{1/n} \to 1$, i.e. they tend to return "often" to where they were. Thus the random walks have bigger chance to "fuse", i.e. if a random walker starting at $s$, is at some time where the random walker starting at $e$ was, then the exit probabilities will be the same.
-
Why is it clearly false on the free group? –  Mikael de la Salle Apr 25 '13 at 8:11
I discussed your question with Vincent Beffara. We arrived at the conclusion that your question has a positive answer (for every pair (s,e)) if and only if your graph is Liouville. In particular, the lamplighter group on $\mathbb{Z}^3$ gives a negative answer to your question. Vincent should soon write more on this as an answer. –  Mikael de la Salle Apr 25 '13 at 12:59
Thanks for the comment (and Vincent's answer). Without knowing this is equivalent to trivial Poisson boundary, on the free group (which is a tree), the intuition is that the walk is "ballistic", i.e. does not really come back. Since it will with relatively small probability cross the separating edge at the beginning, there is no reason that the exit probabilities will be small. With more effort, one can actually compute these exit probabilities. –  Antoine Apr 26 '13 at 10:17

Say that a graph $G$ has the Liouville property if all bounded (discrete-)harmonic functions on it are constant.

• If it is possible to couple random walks on $G$ started from any two starting points in such a way that they almost surely coincide after some (random) time, then the graph is Liouville. The reason for that is that one can write the value of a bounded harmonic function $f$ at $x$ as the expected value of $f(X_t)$ where $X$ is a random walk on $G$ and $t$ is any stopping time; it random walks from $x$ and $y$ couple with high probability by time $t$ this gives an upper bound on $|f(x)-f(y)|$ which shows that $f$ has to be constant.

• If your graph admits non-constant bounded harmonic functions, then the TV distance between harmonic measures from $e$ and $s$ (which is another way of naming what you are interested in) cannot go to $0$ for all pairs $(e,s)$. Indeed, if $f$ is a non-constant bounded harmonic function and $f(e) \neq f(s)$, then writing $f$ as the expected exit value one gets a lower bound on the TV distance in terms of $|f(e)-f(s)|$.

• On the other hand, assume that the $\ell^1$ norm you are interested in does not go to $0$. It means that there exists a sequence $g_i$ of functions bounded by $1$ in absolute value, each defined on $F_i^c$ and such that the integrals of $g_i$ through your two exit distributions differ by at least some $\delta>0$. Taking the harmonic extension $f_i$ of $g_i$ inside $F_i$ one gets $|f_i(s) - f_i(e)| \geq \delta$. Letting $i$ go to infinity and using a diagonal argument one gets a bounded harmonic function $f$ defined on the union of the $F_i$ (which I am assuming to be the whole graph?) and such that $|f(s)-f(e)|>0$, i.e. it is non-constant.

So, the answer to your question is positive iff the graph is Liouville. Now for the link with amenability: it is not true that every amenable group is Liouville, and a counterexample is given by the lamplighter group on $Z^3$ (or on any transient amenable group for that mattter). One natural non-constant harmonic function is the following: given any $(\omega,x)$ on the LL, where $\omega$ is the lamp configuration and $x$ the location of the walker, define $f((\omega,x))$ to be the probability, for a random walk $(\omega_t,x_t)$ started there, that the lamp at the origin $\omega_t(0)$ is eventually on. Note that the state of that lamp changes only finitely many times because the underlying random walk is transient.

This function is clearly harmonic and bounded. To see that it is non-constant, just take $x$ very large: the probability that $x_t$ ever visits the origin will be very small, so with high probability the eventual state of the lamp at the origin will be the same as its state at time $0$, ie its state on $\omega$: $f((\omega,x))-\omega(0) = o_{x\to\infty}(1)$. So some places $f$ will be close to $0$ and some places it will be close to $1$.

-
@Vincent That's a nice example. What about the converse: is every Liouville group amenable? –  Sean Eberhard Apr 26 '13 at 10:09
Thankd for this nice and detailed answer! I really did not expect an "iff"... –  Antoine Apr 26 '13 at 10:11
@Sean: the answer is yes (a result of Kaimanovich, I believe, the expert will confirm/infirm). Actually, the proper formulation is that an amenable group always has a measure for which the RW has trivial Poisson boundary, but in the case of wreath products, this measure is never finitely supported (results of Erschler? again, my memory is vague). –  Antoine Apr 26 '13 at 10:22
@Vincent: In the example of harmonic function you give, are you somehow describing the space of "limiting configuration"? I've seen reference for this but cannot access the paper of Erschler where she describes them. –  Antoine Apr 26 '13 at 10:25
@Antoine: the fact that the Cayley graphs of non-amenable groups is non-Liouville is due to Furstenberg (at least according to Erschler). The converse (amenable groups carry a Liouville random walk) is due to Kaimanovich-Vershik and Rosenblatt. This is explained in ams.org/mathscinet-getitem?mr=2025301 –  Mikael de la Salle Apr 26 '13 at 11:44
show 1 more comment