# Bounding the probability of landing at any point for a random walk on a tree

Fix $m\geq 2$ and a vertex $v_0$ in an infinite connected $2m$-regular tree, (in other words, the Cayley graph for the free group on $m$ generators) and consider the random walk on the tree starting at $v_0$ which moves from a vertex to any neighbor with equal probability. Let $\mu_n$ be the probability distribution of the random walk at the $n^{th}$ step. It seems like it should be true that for any $v$ in the tree, $\mu_n(v)\ll r^{n}$ for some $r<1$, but I am having trouble showing it.

At first I thought to reduce the problem to a random walk on $\{0,1,2,\dots\}$ by just considering the distance of the random walk from the vertex $v_0$, get a bound on the probability that $0$ is hit and the probability that $1$ is hit at the $n^{th}$ step in this random walk, and then to argue that $\mu_n(v_0)\geq\mu_n(v)$ for all $v$ in the tree when $n$ is even and that a similar bound holds for the neighbors of $v_0$ when $n$ is odd. I could not even manage to analyze this random walk on $\{0,1,2,\dots\}$, however, because I got a messy two variable recurrence relation for the probabilities that I did not know how to deal with. It also seems like this strategy is too complicated for the problem at hand.

Is there a simple way to show that there's an $r<1$ such that for any $v$ in this tree, $\mu_n(v)\ll r^{n}$? Must I go through the random walk on $\{0,1,2,\dots\}$ as I was describing, or is there a slicker way? If there is no slicker way, what is a good way to bound the probabilities that $0$ or $1$ are hit on the $n^{th}$ step in the random walk on $\{0,1,2,\dots\}$ with transition probabilities $p_{0\to 1}=1$ and $p_{i\to i+1}=1-\frac{1}{2m}$, $p_{i\to i-1}=\frac{1}{2m}$ for $i\geq 1$?

## 1 Answer

You can extend the walk to the negative numbers; then the probabilities are simple (e.g. for $n$ and $d$ of the same parity):

\begin{align} p_n(d)&=\binom n{\frac{n+d}2}p^{(n+d)/2}(1-p)^{(n-d)/2}\\ &\lt\binom n{\frac n2}(p(1-p))^{n/2}\left(\frac p{1-p}\right)^{d/2}\\ &\le2^n(p(1-p))^{n/2}\left(\frac p{1-p}\right)^{d/2}\\ &=\left(2\sqrt{p(1-p)}\right)^n\left(\frac p{1-p}\right)^{d/2}\\ \end{align}

with $2\sqrt{p(1-p)}\lt1$ for $m\ge2$. There are two effects from the spurious negative numbers – the probability on the negative numbers themselves, which you should be able to bound suitably, and the shift due to the availability of the negative numbers in the past, which works towards smaller $d$ and thus should also be manageable.

• Thank you! I was able to get the bound I wanted easily doing what you described – dfsfljn Mar 24 '16 at 1:42