Probabilities of a random walk exiting a set

Question

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.

Answer 1

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