MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $X_i$ be a (finite-state, irreducible, aperiodic) Markov chain, not necessarily stationary. (That is, it doesn't start from the invariant distribution; I'm happy to have it be time-homogeneous if that helps.) Let $Y_i = f(X_i)$. Let $S_i = \sum_{s=1}^i Y_i$ be the partial sum sequence. Is it true that $$ \mathbb E_s [\max_{i \leq n} S_i^2] \leq C \mathbb E_s[S_n^2]? $$ Here $\mathbb E_s$ is the expectation given $X_0 = s$. The constant $C$ may potentially depend on the size of the state space, the mixing time of the chain, etc. (It's also possible that the correct functional dependence is actually more like $\leq C_1 \mathbb E_s S_n^2 + C_2$.)

Basically, I'll take any sensible bound on the maximum of the partial sum sequence for a (functional of a) non-stationary Markov chain; I'm not after the optimal bound.

A sub-question: there are lots of maximal inequalities for dependent sequences satisfying certain mixing conditions. (E.g.: Peligrad, Utev, and Wu, Proceedings of the AMS 2005; Rio, Journal of Theoretical Probability 2009; Merlevede and Peligrad, Annals of Probability 2013; the list is not meant to be in any way exhaustive.) Is there an easy way to convert a maximal inequality for a stationary mixing sequence to a maximal inequality for a (functional of a) non-stationary finite-state Markov chain?

share|cite|improve this question
As written it seems fairly hopeless: Here's a stupid example. If your MC has $a\to b\to c$ (i.e. that the only successor of $a$ is $b$; and the only successor of $b$ is $c$), then if $f(a)=1$ and $f(b)=-1$, but $f$ is 0 elsewhere and $s$ has no chance of being at $a$ or $b$ after $n$ steps (but may be there before), then you're out of luck. – Anthony Quas Jun 17 '14 at 21:38
You could have what I'm talking about in an irred. and aper. MC (there may be several paths from $c$ back to $a$ of different lengths); just no path from $s$ to $a$ or $b$ of length exactly $n$ (of course $n$ has to be small for this to be possible) – Anthony Quas Jun 18 '14 at 16:08
It seems to me that it should at least be possible to show that I lose at most a constant? I believe coupling the MC to its stationary version should give me a constant of the form $Ct_{mix}$, where $C \sim max(f) - min(f)$ and $t_{mix}$ is the mixing time. – Elena Yudovina Jun 18 '14 at 16:14

Your Answer


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

Browse other questions tagged or ask your own question.