Conditioning Probability on a Language With Measure 0

Question

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?

Answer 1

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.