Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Edits: Changed function to eigenfunction. I should have stated the problem with more explicit conditions. Anyways I realized the original formulation is not true, even when one starts at a single state: take the function on the $\mathbb{Z}$ with $f(1) =1$, $f(-1) = -1$, $f(0)= 0$, and $f(x) = \text{sgn}(x) \epsilon$ where $\epsilon$ is very small, and the simple random walk on $\mathbb{Z}$, then it will have the highest variance at $t=1$. One can easily adapt this example to the simple random walk on the $n$-cycle.

Given a function $f: \Omega \to \mathbb{R}$, where $\Omega$ is the state space of an ergodic finite state Markov chain, and let the chain start at a single state $x \in \Omega$. Assume $f$ is an eigenfunction of the chain. Is it true that $\mathbb{E}_t (f- \mathbb{E}_t f)^2$ is nondecreasing in $t$? Here $\mathbb{E}_t f$ denotes $\mathbb{E} P_t f$ where $P_t$ is the Markov transition kernel from time $0$ to time $t$. Note it's important to start with the point mass distribution at a single state, since otherwise one could choose an initial distribution that has an $f$-variance larger than the stationary (as pointed out by one of the commenters below).

Wilson's method gives a way to bound the variance of eigenfunctions in $t$ in a way that's reminiscent of the Martingale difference method, but since the variance at time $\infty$ is usually easy to calculate, if we know the above monotonicity result, we could bound the variance at finite time easily.

share|improve this question
Not sure I understand the question. What do you take for the initial distribution? If the chain is stationary, the quantity doesn't depend on $t$. On the other hand, if you allow a general initial distribution, just start in some distribution where the variance of the test function is higher than it is under the stationary distribution. Even if you insist on a deterministic initial state, pretty much any 2-state chain will give a counterexample - take a function whose variance is not maximised by the stationary distribution, and consider approaching stationarity from one extreme or the other. –  James Martin Mar 12 '11 at 8:39
Take any finite chain with an absorbing state and where all other states are transient. Then the variance converges to $0$. –  camomille Mar 12 '11 at 13:07
@James: I agree that even if starting at deterministic initial state, counterexample exists if $f$ is not required to be an eigenfunction. But I don't quite understand your last 2-state example. The starting variance is always 0 right? –  John Jiang Mar 12 '11 at 16:45
add comment

1 Answer

I can give you the answer for a certain class of Markov Chains, i.e. for reversible, irreducible and aperiodic Markov Chains on a finite state space.

Then the question is related to the spectral gap of the transition matrix $P:\Omega\times\Omega\to [0,1]$ of your chain. The transition matrix entry $P(x,y)$ is the probability of going from state $x$ to $y$. Thus one has $\sum_{y\in \Omega} P(x,y)=1$ If your chain is irreducible ($\forall x,y\in \Omega \exists n\in \mathbb{N}: P^n(x,y)>0$) and aperiodic (means that $\forall x\in \Omega$ the period defined by the greatest common divisor of the set $T(x)=\{n\in \mathbb{N}: P^n(x,x)>0\}$ is $1$) then one has the following Theorem:

If $\Omega$ is finite and the chain defined by the transition matrix $P$ is irreducible and aperiodic than there exists a unique stationary distribution $\pi$ such that $\pi P =\pi$.

A chain satisfying a detailed balance relation $\pi(x) P(x,y) =\pi(y) P(y,x)$ is reversible.

Under these conditions the eigenvalues of $P$ are bounded in modulus by $1$ and the largest is $1$, the corresponding left eigenvector is $\pi$. Then the spectral gap is defined by $\gamma=1-\max_{\lambda\ne 1} |\lambda| $. Note that $0<\gamma<1$. Then it yields the following estimate for the variance of a test function $f:\Omega\to\mathbb{R}$ with respect to the stationary measure $\pi$

${\mathrm{Var}}_\pi(P^n f) \leq (1-\gamma)^{2t} {\mathrm{Var}}_\pi(f)$

share|improve this answer
@Andre: remember the variance is defined by $\text{var} f = \mathbb{E}_t(f^2) - \mathbb{E}_t(f)^2$ so you also had to subtract off the mean, and the mean is taken not with respect to the stationary measure, but rather the running measure at time $t$. If the mean is the stationary measure mean, then what you wrote is correct. But I really need the variance at time t without apriori knowledge of the stationary distribution. –  John Jiang Mar 12 '11 at 16:39
This is not related to the question. Moreover, the assumption of reversibility is useless. The exponential convergence will hold for any finite state irreductible aperiodic Markov Chain. In addition, the aperiodicity is useless to get the existence and unicity of a stationary distribution... –  camomille Mar 12 '11 at 16:44
Ahem. The new question is actually very different from the initial one. –  camomille Mar 12 '11 at 16:47
sorry about that. I will start a new post. –  John Jiang Mar 12 '11 at 18:02
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.