# Conditioning Probability on a Language With Measure 0

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?

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.

• Nice, and thanks for the references, I will check them out. Apr 8, 2021 at 9:27