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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Anthony Quas Jun 17 '14 at 21:38
  • 1
    $\begingroup$ 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) $\endgroup$ – Anthony Quas Jun 18 '14 at 16:08
  • $\begingroup$ 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. $\endgroup$ – Elena Yudovina Jun 18 '14 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.