I would like a result along the following lines to be true, but haven't been able to locate it in the literature; pointers would be welcome.

Let $X_{t}$ be a finite-state, irreducible, aperiodic Markov chain. Let $f$ be a bounded functional, which is mean-zero with respect to the stationary distribution of $X$. Let $$ S_{t} = \frac{1}{\sqrt{n}} \sum_{s \leq t} f(X_{s}), \quad t \leq n $$ be the partial sum process. Then there exists $\epsilon > 0$, $N_0 > 0$, and a Brownian motion $B_t$ such that, for all $n > N_{0}$, $$ g(n) := \sup_{t \leq n} |B_{t} - S_{t}| \leq n^{1/2 - \epsilon}. $$ (Interpreted either as "$t$ is an integer less than $n$" or as "interpolate $S_{t}$ linearly between integers".)

In the case of partial sums of i.i.d. random variables, if I remember correctly, the Skorohod embedding gives $g(n) \sim n^{1/4}\log(n)$, and the KMT approximation gives $g(n) \sim \log(n)$. In the Markovian setting, I'm hoping for $g(n)$ to depend on the mixing time of the Markov chain.

It's possible that the correct generality for this is "ergodic sequence" rather than "Markov chain".

  • 1
    $\begingroup$ The correct level of generality is certainly not ergodic sequences. If you take sums of a mean zero function, then you have the analog of the strong law of large numbers: $S_n=o(n)$ and absolutely nothing more in general (it's not hard to construct counterexamples using Rokhlin's lemma). If you want more than this in the ergodic world, you have to make assumptions about mixing properties of the underlying transformation, and smoothness of the function. $\endgroup$ Jul 6, 2014 at 7:32
  • $\begingroup$ Agreed. Perhaps you can suggest where I would find results that do make assumptions about mixing properties? If I understand correctly, the finite-state irreducible aperiodic Markov chain I'm dealing with has all the mixing properties one could ever want. $\endgroup$ Jul 6, 2014 at 17:18
  • 2
    $\begingroup$ My guess is that it would be slightly perverse to try and go through ergodic theory. What people there are doing is trying to recover enough independence to be able to mimic proofs in MCs. A sample ergodic paper: Melbourne, Ian; Nicol, Matthew A vector-valued almost sure invariance principle for hyperbolic dynamical systems. Ann. Probab. 37 (2009), no. 2, 478–505. I believe there is something of an industry of this though. My guess is that this will be far less precise than what is known in more specific probabilistic settings. $\endgroup$ Jul 6, 2014 at 18:33

1 Answer 1


It turns out that to find a whole slew of results of this shape I needed to know that

(a) this sort of statement is called "strong invariance principle" more often than "strong approximation";

(b) the result as requested above is the subject of the book by Walter Philipp and William Stout, Almost sure invariance principles for partial sums of weakly dependent random variables, Memoirs of the AMS vol. 2 no. 161, July 1975.


Your Answer

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

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