Random Walk on a complete binary tree

[Ben Edwards]

So just to start the adjacency matrix looks something like

[ 0 1/2 1/2 0 ...
[ 1/3 0 0 1/3 1/3 0 ...
[ 1/3 0 0 0 0 1/3 1/3 0 ...

Then when we get down to the leaves we have something like

[ ... 0 1 0 ...]

As the only place to go is back up.

As per usual the lazy random walk just halves everything and puts 1/2
on the diagonal.

I've worked out some small examples for the characteristic polynomial
of the SRW, eg

Tree of size 3
x^3 -x = 0 is the characteristic

For a tree of size 7 its
x^7 - 5/3x^5 + 2/3x^3 = 0

I can't quite come up with the terms for the characteristic
polynomial, as we did for the other examples in class. IE what are the
permutations that actually give us non-zero terms.

[thanaphon Tangchoopong]

Andrew and I plan to talk about the problem before class in the morning (around 9.30 am) on the CS department 3rd floor. 

Everyone is welcome to join. Related reading is CH7 on the book. 

Joe 

[Thomas Hayes]

Hi,

Some answers to Ben's questions, below.

On Sun, Sep 26, 2010 at 4:53 PM, Ben Edwards <bjed...@gmail.com> wrote:

The permutations corresponding to nonzero terms are the ones where each
cycle in the permutation corresponds to a closed walk on the graph.
In the case where the graph is a tree, the only cycles which can correspond to
closed walks are 2-cycles and 1-cycles. The 1-cycles correspond to diagonal
entries of (xI - P), and hence each contributes a factor of x. The 2-cycles
correspond to traversing an edge in both directions, and hence contribute a
factor of (a) 1/3 * 1/3 for an internal edge. (b) 1/3 * 1 for an edge
to a leaf, or
(c) 1/3 * 1/2 for an edge to a root.
Since the cycles in a permutation partition the n vertices, we are looking for
matchings in the graph.

Let's analyze the tree of size 3:
x^3 corresponds to the identity permutation (matching of size 0).
x * 1/2 * 1 corresponds to each of the 2 edges (matchings of size 1).
(The corresponding permutations fix one leaf, and swap the other leaf
with the root.)
Summing up with signs gives: x^3 + 2 * (-1) * x * 1/2 * 1 = x^3 - x,
as Ben wrote.

For the tree of size 7:
x^7 corr to the matching of size 0.
6 matchings of size 1:
4 * (-1) * x^5 * 1/3 * 1 (edges to leaves)
2 * (-1) * x^5 * 1/2 * 1/3 (edges to root)
8 matchings of size 2:
4 * (-1)^2 * x^3 * 1/2 * 1/3 * 1/3 * 1 (1 edge to root, 1 edge to leaf)
4 * (-1)^2 * x^3 * (1/3 * 1)^2 (2 edges to leaf).
no matchings of size >= 3.
Total: x^7 - (5/3) x^5 + (2/3) x^3, again, as Ben wrote.

The eigenvalues here are 0 (multiplicity 3), +/-1, and +/-sqrt{2/3}.
If you look at the eigenvectors, you'll see that the ones for +/-1
and at least one of the ones for 0 project down to the eigenvectors
for -1, 0, 1 for the random walk on the path of length 2.
The eigenvectors for +/-sqrt(2/3) both project down to the all-zero
vector on the path. Note that sqrt(2/3) is the second-largest
eigenvalue, which is controlling the mixing time for LRW on the tree.

When you go up to bigger trees, this pattern continues, so the
eigenvalue gap for the tree gets really small compared to that for
the path. So much for projections!

Tom