Random walk on a tree

Question

Consider a Cayley tree with coordination number 3 (http://en.wikipedia.org/wiki/Bethe_lattice). Consider two sites, $x$ and $y$, having a distance $k$ one from another. What is the probability that random walk starting from $x$ will ever visit $y$? Jumps are distributed uniformly at random among the neighbours.

Answer 1

If $p(k)$ is the probability of ever reaching $y$ when starting a distance $k$ away then you have $$p(k) = \tfrac13p(k-1)+\tfrac23p(k+1)$$ with $p(0)=1$.

The solution is the rather simple $$p(k) = 2^{-k}.$$

Answer 2

When you have given the Cayley tree, you can write down the following $N \times N$ Matrix with $N$ the number of graph nodes:

$P_{ij}:=$ Probability for jumping from node $i$ to node $j$. When the node has $n$ neighbors, for every neighbor the probability is $\frac{1}{n}$. From graph theory it is known that the Expression $(P^a)_{ij}$ for a power $a$ is the probability going from i to j within exactly $a$ steps.

To compute the probability for visiting $y$ when starting from node $x$, you have to sum up all possible steps in which the node $y$ can be reached, i.e.

$p = \sum_{a=1}^\infty (P^a)_{xy} = (\frac{1}{1-P})_{xy} - 1$

where in the last equality the geometric series formula is used.