3
$\begingroup$

Let $\Sigma = \{ 1, 2, \ldots, n\}$ be some alphabet. Assume that you have a coin with n-sides (each side corresponds to a letter in $\Sigma$), and we get each letter with equal probability. Now you can think of an infinite word $w$ over $\Sigma$ as a result of tossing the n-sided coin infinitely many times.

With this view, I can think of $\omega$-regular langauges over $\Sigma$ as events. There are interesting languages that have measure $0$. For example, consider the language $L = \bigcup\limits_{i\in \Sigma } \Sigma^* \cdot (\Sigma \setminus \{i\})^\omega$. That is, $L$ consists of all infinite words over $\Sigma$ that have finitely many $i$'s, for some $i$.

Now I am interested in computing $P(L_2|L)$ for some language $L_2 \subseteq L$. Sometimes, I can guess the answer by "symmetry" considerations in case $L$ and $L_2$ are "simple" enough, but my question is: how can I condition on a language $L$ which is of measure $0$ in the general case?

Example: assume again that $L = \bigcup\limits_{i\in \Sigma } \Sigma^* \cdot (\Sigma \setminus \{i\})^\omega$. Consider the following event (or language):

$$ L_2 = L\setminus \{ w \in \Sigma^\omega: \text{$w$ has finitely many 1's, and every $j\neq 1$ appears infinitely often in $w$}\}$$

What is $P(L_2|L)$? In other words, how can I compute the fraction of words that I did not through out from $L$.

I believe there is a way to condition on a language of measure $0$ but I'm not sure how. A similar simple situation appears in the following: one can sample a random $(x, y)$ point in a rectangle $[0, 1]\times [0, 1] \subseteq\mathbb{R}_2$ and then ask what is the probability $P(y \geq \frac{1}{2} | x = \frac{1}{2})$. Clearly, this probability is $\frac{1}{2}$ although we condition on the line $x = \frac{1}{2}$ which has measure $0$ in $[0, 1]\times [0, 1]$. The way I think about the line-rectangle example is as follows. I imagine the line $x = \frac{1}{2}$ as a rectangle of width $\epsilon \to 0$. Is there a similar approach that can be adapted to $\omega$-reuglar languages?

$\endgroup$
3
$\begingroup$

I don't know of a general approach to handle this, but in the case of $\omega$-regular languages, this has been done.

One approach, which I think is first introduced in the paper Computing Conditional Probabilities in Markovian Models Efficiently is the following:

Given the language $L$, let $D$ be a DPW for it. Now, start by constructing a Markov chain $M$ that captures your distribution on $\Sigma^\omega$ (uniform, in your case). Then take the product of $M$ and $D$.

Now, in the product MC, you have the property that the probability that the run is accepting is exactly the probability of $L$ (0, in your case, but it works for any $L$).

We now modify the product by "redistributing" the probability: whenever the MC reaches an end-component (ergodic component) in which the probability of acceptance is 0, the run restarts in the initial state. This ensures that all $0$-probability-of-acceptance runs get "another chance".

You can use this to essentially restrict yourself only to words in $L$, and now you can ask what the probability of another language is, in this MC, and this provides a reasonable definition of conditional probability.

I'm slightly sketchy on the details, but I think this should work.

I've used this technique in a paper here: https://arxiv.org/abs/1608.06567.

$\endgroup$
1
  • $\begingroup$ Nice, and thanks for the references, I will check them out. $\endgroup$ Apr 8 at 9:27

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.