In my first post I promised to give a polynomial-time procedure to compute the probability that an infinite word (chosen uniformly at random) is accepted by a given unambiguous Büchi automaton.
For example, let's take this Büchi automaton again:

Let's call the probability $x_1, x_2, x_3$, depending on the start state: \[ \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} := \begin{pmatrix} \text{Pr(state $1$ accepts a random word)}\\ \text{Pr(state $2$ accepts a random word)}\\ \text{Pr(state $3$ accepts a random word)} \end{pmatrix} \] I showed in the first post that $x_1, x_2, x_3$ are nonzero in this example. In order to

$x_{1,b} = 0$ because state $1$ has…

Let's call the probability $x_1, x_2, x_3$, depending on the start state: \[ \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} := \begin{pmatrix} \text{Pr(state $1$ accepts a random word)}\\ \text{Pr(state $2$ accepts a random word)}\\ \text{Pr(state $3$ accepts a random word)} \end{pmatrix} \] I showed in the first post that $x_1, x_2, x_3$ are nonzero in this example. In order to

*compute*the $x_i$ we set up a linear system of equations and solve it. We have \[ x_1 \ = \ \frac12 \cdot x_{1,a} + \frac12 \cdot x_{1,b}\,, \] where $x_{1,a}$ and $x_{1,b}$ denote the (conditional) probabilities that state $1$ accepts a random word, under the condition that the word starts with $a$ and $b$, respectively.$x_{1,b} = 0$ because state $1$ has…