1.6. Exercises 47
the union of T1 and T2 and adding one more connection: we say that
o and ˜ o are adjacent.
• Convince yourself that T is a connected tree, i.e., between
any two points of T there is a unique path in the tree that
does not go through any point more than once.
• Let Sn denote simple random walk on the tree, i.e., the
process that at each step chooses one of the three nearest
neighbors at random, each with probability 1/3, with the
choice being independent of all the previous moves. Show
that Sn is transient, i.e., with probability one Sn visits the
origin only finitely often. (Hint: Exercise 1.18 could be
• Show that with probability one the random walk does one
of the two following things: either the random walk visits
T1 only finitely often or it visits T2 only finitely often. Let
f(x) be the probability that the walk visits T1 finitely often.
Show that f is a nonconstant bounded harmonic function.
(A function f on T is harmonic if for every x ∈ T , f(x)
equals the average value of f on the nearest neighbors of x.)
• Consider the space of bounded harmonic functions on T .
Show that this is an infinite dimensional vector space.
Exercise 1.27. Show that if A ⊂ A1 are two subsets of
λA ≤ λA1 . Show that if A1 is connected and A = A1, then λA λA1 .
Give an example with A1 disconnected and A a strict subset of A1
for which λA = λA1 .
Exercise 1.28. Consider β(j, N),j = 1,...,N − 1 where β(j, N) is
the unique positive number satisfying