Foster’s Lemma provides a natural condition to prove the positive recurrence of a Markov chain.
- Let be a discrete-time Markov chain on countable, irreducible state-space .
Theorem [Foster’s Lemma] If is a function with and such that for some and some , is finite, and
then is positive recurrent.
Consider a process that jumps to then, at each unit of time, moves down until it moves below and then subsequently jumps up to again. For every one unit of time below , this process spends units of time above . So the proportion of time the process is below is about . In other words, the process is positive recurrent in states less than or equal to . This is Foster’s Lemma in a nutshell; however, the conditions of Forster’s Lemma says that on average this is the worst that can happen to . Need to turn this intuition about our average process to a rigorous proof about our stochastic process.
- We will often refer to the function used in Foster’s Lemma as a Lyapunov function.
Proof. For any discrete time Markov chain exists and, moreover, the limit is positive iff is positive recurrent.
Rearranging this expression and taking limits, we get that
Thus since is finite, for some ,
In other words, is positive recurrent and thus our irreducible Markov chain is positive recurrent.
There are numerous generalizations of Foster’s Lemma, but all roughly follow this structure.
We consider one such generalization, the Multiplicative Foster’s Lemma. Here we allow the Markov chain to have a downward drift over a period of time proportional to the size of its initial state. This version of Foster’s Lemma will be useful when we take a deterministic process as the limit of our stochastic process.
- Let be a continuous-time Markov chain on countable, irreducible state-space .
- We let define a norm on . 1
Theorem [Multiplicative Foster’s Lemma] If and if for some , some and some , is finite, and
where is the next jump time of the Markov chain then is positive recurrent.
- When we take a fluid limit, we rescaled space and time proportionally to get a deterministic limit. Observe this result remains invariant when we rescaled space and time proportionally.
Proof. We consider our Markov chain at specific stopping times: and for ,
where is the time to the next jump of our Markov chain after time . Similar to Foster’s Lemma Rearranging, dividing by and taking limits, we gain the expression
Thus, is positive recurrent as it is positive recurrent in the finite set of state .
- We do not really need a norms here. Just some notion of distance, but to be safe we assume it is a norm.↩