Probabilistic Automata

Nathanaël Fijalkow

LIAFA, Paris 7 (France) and University of Warsaw (Poland)

Where the wild things are

Binary decomposition

Rabin:
Corollary (Bertoni): Undecidability of the emptiness problem.

Isolation

The threshold 1/2 is isolated if there exists $\varepsilon > 0$ such that for all words $u$, we have $\mathbb{P}(u) < 1/2 - \varepsilon$ or $\mathbb{P}(u) > 1/2 + \varepsilon$.

Theorem (Rabin): If 1/2 is isolated, then $L^{> 1/2}$ is regular.

Theorem (Bertoni): Determining if 1/2 is isolated is undecidable.

Universally non-regular automaton

Double-Rabin:
Corollary (Bertoni): Undecidability of the regularity problem.
We show that for all x in (0,1), $L^{> x}$ is non-regular.

Let $u,v$ in $\{0,1\}^*$, we have $\mathbb{P}(u \cdot \sharp \cdot v) = \mathrm{bin}(u) \cdot \mathrm{bin}(v)$.

For every $u,v$ in $\{0,1\}^*$ such that $\mathrm{bin}(u) < \mathrm{bin}(v) < x$, there exists $w$ in $\{0,1\}^*$ such that $u \cdot \sharp \cdot w \in L^{> x}$ and $v \cdot \sharp \cdot w \notin L^{> x}$; it suffices to choose $w$ such that $\mathrm{bin}(w)$ is in $\left(\frac{x}{\mathrm{bin}(v)},\frac{x}{\mathrm{bin}(u)}\right)$.

It follows that the left quotients $u^{-1} \cdot L^{> x}$ and $v^{-1} \cdot L^{> x}$ are distinct.

Universally non-regular automaton

Double-Rabin:
Corollary (Bertoni): Undecidability of the regularity problem.

Two-way Counting

Theorem (Freivalds): There exists a two-way probabilistic automaton such that:
On input $0^n 1^m$, play the following game:
A success for $0$ (resp. $1$) is when all coins turn up HEAD. Count the successes up to some constant.

Corollary (Freivalds): There is no algorithm with the following behaviour for two-way probabilistic automata:

One-way Counting

Theorem (Condon - Lipton): There is no algorithm with the following behaviour:

Numberless problems

What about not specifying the numerical values in probabilistic transition functions?

Theorem (F., Gimbert, Horn, Oualhadj): Determining whether for all probabilistic transition functions, $L^{> 1/2}$ is non-empty, is undecidable.

Convergence to 1



Corollary (Gimbert - Oualhadj): Determining whether there exists a sequence of words whose probability converges to $1$ is undecidable.
$$\left\{ \begin{array}{l} \mathbb{P}(0 \xrightarrow{b a^n} L_1) = \frac{1}{2} \cdot x^n \\ \mathbb{P}(0 \xrightarrow{b a^n} R_1) = \frac{1}{2} \cdot (1-x)^n \end{array} \right.$$ $$\begin{array}{lll} \mathbb{P}((b a^n)^N) & = & \sum_{k = 1}^{N-1} (1 - (p_n + q_n))^{k-1} \cdot p_n \\[1.5ex] & = & p_n \cdot \frac{1 - (1 - (p_n + q_n))^{N-1}}{1 - (1 - (p_n + q_n))} \\[1.5ex] & = & \frac{1}{1 + \frac{q_n}{p_n}} \cdot \left(1 - (1 - (p_n + q_n))^{N-1}\right) \\[1.5ex] \end{array}$$ We now set $N = 2^n$: $$\lim_n \mathbb{P}((b a^n)^{2^n}) = 1.$$

Convergence to 1



Corollary (Gimbert - Oualhadj): Determining whether there exists a sequence of words whose probability converges to $1$ is undecidable.

History

Determining whether there exists a sequence of words whose probability converges to $1$ is undecidable.

Markov Monoid Algorithm

Computes a stabilisation monoid, generalising the transition monoid, but for probabilistic automata.

Theorem (F., Gimbert, Oualhadj): The Markov Monoid algorithm is correct for the class of leaktight automata.

Theorem (F., Gimbert, Kelmendi, Oualhadj): The Markov Monoid algorithm is the best algorithm so far.

Characterisation

The sequence $((a^n b)^n)_{n \in \mathbb{N}}$ is polynomial, the sequence $((a^n b)^{2^n})_{n \in \mathbb{N}}$ is not.

Theorem (F.): The Markov Monoid algorithm answers YES if, and only if, there exists a polynomial sequence $(u_n)_{n \in \mathbb{N}}$ such that $\lim_n \mathbb{P}(u_n) = 1$.

Theorem (F.): Determining whether there exist two words $u,v$ such that $\lim_n \mathbb{P}((u^n v)^{2^n}) = 1$ is undecidable.

Prostochastic Theory

Profinite Prostochastic
A sequence converges if for every deterministic automaton:
  • almost all words are accepted,
  • or almost all words are rejected.
 A sequence $(u_n)_{n \in \mathbb{N}}$ converges if for every probabilistic automaton, $\lim_n \mathbb{P}(u_n)$ exists.
Two sequences are equivalent if for every deterministic automaton, they agree on almost all words. Two sequences $(u_n)_{n \in \mathbb{N}}$ and $(v_n)_{n \in \mathbb{N}}$ are equivalent if for every probabilistic automaton, $\lim_n \mathbb{P}(u_n) = \lim_n \mathbb{P}(v_n)$.
A profinite word is an equivalence class of converging sequences. A prostochastic word is an equivalence class of converging sequences.

Free Prostochastic Monoid

Theorem (F.): The free prostochastic monoid, denoted $\mathcal{PA}$, is the set of all prostochastic words. It forms a compact metric space, satisfying a universal property:
''Every morphism $\phi : A^* \to Stoch(\mathbb{R})$ extends uniquely to a continuous morphism $\widehat{\phi} : \mathcal{PA} \to Stoch(\mathbb{R})$.''

Reformulation

Theorem (F.) A probabilistic automaton has value $1$ if, and only if, it accepts a prostochastic word.

Theorem (F.) The Markov Monoid algorithm answers YES if, and only if, it accepts a polynomial prostochastic word.

Open Problems