I revisited some elementary finite state Markov chain theory these days using the Aldous and Fill book, and found some treasures even in chapter 2. I was not interested in them before because they seem not directly related to mixing time problems. Now that I am free from the shackle of graduate school, the time is ripe to figure things out systematically on my own. One of those identities shows a way to compute in terms of rational functions of for various 's; here stands for the first hitting time of the state , and is the expected first hitting time of if one starts the chain at . So I sought generalization to things like . Note since we are working in discrete time, these inequalities are clean as equality cannot hold. To investigate such question conforms to my view of how math should be done in a way: a systematic pursuit of the obvious possibility to ease laymen's way of grasping the subject; indeed most published works explore things hardly conceived by the untrained crowd, albeit being very original and nontrivial.
So the question remains whether the three term inequality probability can be expressed as a rational function of things like . After trying a bunch of things similar to how the simpler two term case was done, I decided that it was inevitable to introduce things of the form into the equation. This is clearly the same as , i.e., the mean hitting time of the two point set . It is unclear to me yet whether the latter can be expressed in terms of ‘s only. First we apply the Markov property to get . The second factor is already handled by Aldous and Fill and turns out to rely on the following identities:
where is a random state equal in law to , and is a stopping time. The convention is that the number of visits before something includes time 0 but excludes .
(obvious). Here means the first time such that .
follows from previous identity.
The first identity can of course be found in most textbooks on Markov chains, as it constructs the stationary distribution; the proof exploits an infinite sum and is a bit miraculous. The last two follow by choosing appropriate stopping time . The accompanying diagrams illustrate the construction of appropriate stopping times to fit in the pattern of the first identity. Two not so immediate corollaries are
Indeed take the first of these: let the number of visits to before . Then
from which the first corollary is obvious.
Now consider the extended probability introduced in the beginning: . We first compute . By analogy with above, this is
The numerator expands to
The denominator similarly becomes
Of course the and the like can be further expanded in terms of ‘s, but we omit. The main obstacle is apparently .