# $\omega$-regular properties of a 2-state Markov Chain

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?

• What does it mean for an event to be $\omega$-regular? Apr 2, 2013 at 19:32
• @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.
– Ilya
Apr 3, 2013 at 15:09

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.