In a previous blogpost I discussed a way of using results about random walks to solve the functional equation
and we saw that the only solutions to (1) are the constant functions. My friend Drago posted an alternate solution to this problem on his weblog over here where he used the famous Krein-Milman theorem to solve not just the functional equation in (1) for bounded functions but a wide range of similar functional equations for for positive-valued functions
as well; even for this simple case, finding a probabilistic solution is not an easy task, though there exists one.
Note: A part of the contents discussed on this blogpost was presented by me, as a class presentation in one of the classes of a course on martingale theory which I am studying this semester.
We begin with some definitions.
Notation and terminology 1: Throughout this blogpost, unless mentioned otherwise, by Markov chains we would mean a discrete-time, time homogeneous Markov chain on a countable state space Despite the time points being discretely spaced, we would use Also we will use a generic notation for all |
Definition (Discrete harmonic functions): A function the function A function where the word ”discrete” reminds us that we are in the discrete setting as the underlying state space |
This is closely related to the notion of harmonic functions which are continuously twice differentiable functions that satisfy
where is the Laplace operator.
These continuous harmonic functions appear in complex analysis, often in disguise (thanks to the following result from complex analysis).
Proposition 2 (Harmonic functions A function |
A celebrated result in complex analysis, namely the Liouville’s theorem can then be stated as follows:
Theorem 3 (Liouville’s theorem) |
Discrete harmonic functions are not totally alien to the other notion of harmonicity defined by (4). In fact if one replaces by its discrete or finitary version (often known as the discrete Laplacian-averaging operator or finite Laplacian) then (4) turns out to become equivalent to (3).
Getting motivated by Liouville’s theorem one may feel tempted to investigate whether bounded discrete harmonic functions for a transition kernel are always constant or not. The answer is no, in general.
Exercise 4 (thanks to Yuval Peres): Suppose
is a
regular tree on a countably infinite set of vertices and let
be a vertex distinguished as the root of the tree. Suppose
is a neighbour of the root
let
be the family of vertices spawned by
that is to say that,
Suppose
is the simple symmetric random walk on
Defne for all vertices
of this tree
Show that
is a non-constant, bounded (in fact
valued) harmonic function.
However, in the special case of SSRW on integer lattice it is true that bounded harmonic functions must be constant. It is also true that one-side bounded harmonic functions for the SSRW on
are also constant.
In a more precise tone we have the following:
Theorem 5 (Harmonic principle for SSRW on Suppose |
Here I discuss two proofs of the weak harmonic principle (one using coupling of Markov chains and the other using the Hewitt-Savage 0-1 law). There is a third proof of the claim using the Krein-Milman theorem, but that would not be elaborated in this blogpost.
Note: when I initially planned to write this blogpost, I thought I would discuss the Krein-Milman based proof here itself; however owing to the significant difference of flavour between these two proofs, I eventually ended up deciding to put it on a different blogpost.
References: I learnt the coupling-based proof of the weak discrete harmonic principle from professor Yuval Peres; see here for more details.
Proof of Weak version of the discrete harmonic principle for SSRW on (Using coupling):
Consider any two arbitrary points Let two persons
start performing a random walk on
from points
respectively, as per the following rules: at each step draw an element
uniformly at random; if at this time point the
th coordinate of the position of
is same as the
th coordinate of the position of
then with probability
we leave both the random walkers’ position unchanged and with the remaining probability
we move both the walkers together in the direction
otherwise if the
th coordinates of the positions of the two random walkers at this point are different then pick one of the two walkers at random and let the chosen walker move in the direction
choosing one the two possible transitions in the
th direction, uniformly at random.
Notice that, if and
are the random walks traced by
when they move as per the above rules, then
and
are lazy simple symmetric random walks on
and if for some $t \ge 0$ and
the
th coordinates of
and
are equal then these two sequences agree on their
th coordinates at all time points
Now notice that for any the sequence of difference between the
th coordinate of
and the
th coordinate of
is a lazy simple symmetric random walk on
with
as an absorbing state whence it follows that
as
To prove the claim it suffices to notice that:
as
Thus for all
whence
since
were arbitrarily chosen elements of
it follows that
for all
Now we discuss a proof of this result using Hewitt-Savage 0-1 law (for permutation invariant combinations of iid random variables).
Proof of Weak version of the discrete harmonic principle for SSRW on (Using Hewitt-Savage 0-1 law)
Named after Edwin Hewitt and Leonard Savage, the Hewitt-Savage 0-1 law can be stated as follows:
Lemma 6 (Hewitt-Savage 0-1 law, iid version) If |
Exercise 7: Suppose
are iid copies of a
valued random variable
with zero mean. Suppose
be a bounded function such that
exists and is equal to
for all
Show that
![]()
Let be a sequence of iid random variables having law uniform over
where as usual
is the
vector with the
th coordinate one and all other coordinates zero.
Thanks to Exercise 7 it follows that for all
So it suffices to show that the limit does not depend on
But this is true, because for any a SSRW on
originating at
and a SSRW on
originating at
intersect with a strictly positive probability, hence
with a strictly positive probability; but since we also established that these limits must be deterministic and equal to
respectively, it follows that
and we are done.
Interestingly enough, proving the strong discrete harmonic principle for SSRW on is significantly simple when
and thanks to Polya’s theorem this is precisely the case when the SSRW on
is recurrent; recurrence of the SSRW on the one and two dimensional integer lattice makes it significantly easier to establish the claim in this special situation.
Proof of Strong version of the discrete harmonic principle for SSRW on when
:
Suppose that It is known that the SSRW on
in this case would be recurrent, and hence it would visit every state
infinitely often with probability one, in this case.
Let be the SSRW on
(
is a member of the set
) and suppose
is a lower bounded harmonic function for this Markov chain; we may assume (by scaling and shifting, as necessary) that
Now clearly the sequence is a non-negative martingale with respect to its own natural filtration; we know that non-negative martingales converge almost surely, it follows that
converges almost surely as
but since
is recurrent (thanks to Polya’s theorem), for any
the sequence
has infinitely many terms equal to
with probability one, but then one must have
for all
and this proves the claim.