Let $X$ be a Markov Chain on a state space $\{0,1\}$ with a transition matrix $$ P = \left( \begin{align} 1-p & &p \\ q & &1-q \end{align} \right) $$ with both $p,q \in (0,1)$ so in particular it is irreducible. Define $p_\delta = p +\delta$, $q = q+\delta$ and let $P_\delta$ be the corresponding transition matrix defining a Markov Chain $X_\delta$. It is well-known that no matter how small $\delta$ is, for some tail event $A$ it holds that $$ \mathsf P(A) = 0,\quad \mathsf P_\delta(A) = 1 \tag{1} $$ where $\mathsf P$ and $\mathsf P_\delta$ are corresponding probability measures over the paths. I wonder, however, whether $A$ can be always taken to be an $\omega$-regular event.

For a particular example, let $\pi$ and $\pi_\delta$ be invariant probability distributions for $X$ and $X_\delta$. Pick any vector $f$ such that $\pi f\neq \pi_\delta f$ and define $$ A_f :=\left\{\limsup_{n\to\infty}\frac1n\sum_{k=0}^n f(X_k) = \pi_\delta f\right\}, $$ then $(1)$ holds for $A_f$. Is $A_f$ $\omega$-regular?

  • $\begingroup$ What does it mean for an event to be $\omega$-regular? $\endgroup$ Apr 2, 2013 at 19:32
  • $\begingroup$ @TysonWilliams: if we think of $\{0,1\}$ as an alphabet, any event is an infinite language on this alphabet. By an $\omega$-regular event I mean the event, which is $\omega$-regulat when regarded as a language. $\endgroup$
    – SBF
    Apr 3, 2013 at 15:09

1 Answer 1


I am not sure whether $A_f$ is an $\omega$-regular event, but for any $\delta>0$ we can pick some $\omega$-regular $A_\delta$ such that $|\mathsf P(A_\delta) - \mathsf P_\delta(A_\delta)| \geq 1-\delta$. This follows from the fact that $\omega$-regular events form an algebra that generates a $\sigma$-algebra where $A_f$ does belong to.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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