1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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
    Commented Jun 17, 2014 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
    Commented Jun 18, 2014 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
    Commented Jun 18, 2014 at 16:14
  • 1
    $\begingroup$ This is true if you assume that $f$ has mean zero with respect to the invariant measure, but the second constant will depend on $f$ itself. Let $Gf= \sum_{n \ge 0} P^nf$, and then apply Doob's inequality to the martingale $Gf(X_n) - \sum_1^nf(X_j)$. Then you will get the bound $$\Bbb E[ \sup_{n\le N} S_n^2 ] \leq 18\|Gf\|_{\infty}^2 + 16\Bbb E[S_N^2]\le 18\gamma^{-2}\|f\|_{\infty}^2 + 16\Bbb E[S_N^2],$$ where $\gamma$ is the spectral gap of the chain. $\endgroup$
    – shalop
    Commented Jun 16, 2020 at 21:17

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .