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 as the generic notation for them; the more discrete-sounding notation will be used as a placeholder for parameters defining the state space or initial distribution, etc., of the chain.
Also we will use a generic notation to denote the transition kernel of such Markov chains, i.e., is a function which satisfies:
for all and for all states
|Definition (Discrete harmonic functions):|
A function is said to be harmonic for at a state if one has
the function is said to be harmonic for if it is harmonic for at all states
A function which is harmonic for some transition kernel (at a point is sometimes called a discrete harmonic function for (at point
where the word ”discrete” reminds us that we are in the discrete setting as the underlying state space is countable.
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 real part of holomorphic functions)|
A function is a harmonic function if and only if there is a holomorphic function such that for all
A celebrated result in complex analysis, namely the Liouville’s theorem can then be stated as follows:
|Theorem 3 (Liouville’s theorem)|
(i) Suppose is an entire function. Then can be bounded (i.e., if and only if is a constant function.
(ii) The only bounded harmonic functions are the constant functions.
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 is a simple symmetric random walk on and suppose be a harmonic function for this Markov chain. Then the following are true:
(i) (Weak discrete harmonic principle, Blackwell) If is bounded then is constant.
(ii) (Strong discrete harmonic principle) If is bounded on one side (i.e., if there is some real number such that or then is constant.
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:
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 are iid copies of a random variable taking values in then any event in the exchangeable (or finite-permutation invariant) algebra has probability either one or zero.
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.