<p>I am not sure whether $A_f$ is an $\omega$-regular event, but for any $\delta&gt;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. </p>

CC BY-SA 3.0
2014-07-23T07:01:40.137Z
2014-07-23T07:01:40.137Z
SBF
<p>Let $X$ be a Markov Chain on a state space $\{0,1\}$ with a transition matrix
$$
P =  \left(
\begin{align}
1-p &amp; &amp;p
\\
q &amp; &amp;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.</p>

<p>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?</p>

CC BY-SA 3.0
2013-04-02T19:32:45.953Z
What does it mean for an event to be $\omega$-regular?
Tyson Williams
CC BY-SA 3.0
2013-04-03T15:09:53.047Z
@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.
SBF
<fl.formal-languages><markov-chains><probabilistic-automata>
$\omega$-regular properties of a 2-state Markov Chain
SBF
# $\omega$-regular properties of a 2-state Markov Chain

(Asked by: username_0 on 2013-03-29)

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?

**Tags:** fl.formal-languages, markov-chains, probabilistic-automata

> **Comments:**
> **username_1**: What does it mean for an event to be $\omega$-regular?  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_0 on 2014-07-23. Score: 1 | Accepted answer

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.


---

