Skip to main content

Probabilistic Models of Computation

This post has 0 ideas. At least, no ideas that are younger than 50 years or so. I'm talking about the two most fundamental models of probabilistic computation and the two most fundamental results about them, according to my subjective judgement.

Every computer scientist knows finite automata:
State $1$ is the start state, and state $3$ is the only accepting state. Some words are accepted (i.e., have an accepting run), for instance the word $aa$. Other words are rejected (i.e., have no accepting run), for instance the word $ba$. Most questions about finite automata are decidable. For instance, the emptiness problem, which asks whether the automaton accepts at least one word. This problem is decidable in polynomial time: view the automaton as a graph, and search the graph for a path from the initial state to an accepting state. One can also decide whether two given automata are equivalent, i.e., do they accept the same words? This problem is computationally hard though: PSPACE-complete (never mind if you don't know what that means).

Let's slap on probabilities:
This is a probabilistic automaton. Previously each state and each letter "activated" transitions, one of which was nondeterministically taken. A probabilistic automaton, in addition, determines a probability distribution over the activated transitions. There is one such probability distribution for each state and each letter. For instance, if in state $1$ the letter $b$ is input then the probabilistic automaton moves to state $3$ with probability $\frac13$, and remains in state $1$ with probability $\frac23$. Probabilistic automata are reactive: someone inputs letters, and the probabilistic automaton reacts to the input by taking transitions probabilistically. As a consequence, each input word is accepted with some probability. For instance, consider the input word $bb$. The probabilistic automaton takes the path $1 \xrightarrow{b} 1 \xrightarrow{b} 3$ with probability $\frac23 \cdot \frac13 = \frac29$. Similarly, it takes the path $1 \xrightarrow{b} 3 \xrightarrow{b} 3$ with probability $\frac13 \cdot \frac34 = \frac14$. These two paths are accepting, because state $3$ is accepting. The other two $bb$-labelled paths, $1 \xrightarrow{b} 1 \xrightarrow{b} 1$ and $1 \xrightarrow{b} 3 \xrightarrow{b} 2$, are rejecting, because states $1$ and $2$ are rejecting. It follows that the probabilistic automaton accepts $bb$ with probability $\frac29 + \frac14 = \frac{17}{36}$. Whereas a nonprobabilistic automaton either accepts or rejects the input word, a probabilistic automaton accepts the input with some probability.
Given a probabilistic automaton, the emptiness problem asks if there exists a word that is accepted with probability $\ge \frac12$.
The following theorem appears in the 1971 textbook Introduction to Probabilistic Automata by Azaria Paz:
The emptiness problem is undecidable.
The emptiness problem remains undecidable when the nonstrict inequality $\ge$ is replaced by strict inequality $>$, and also when the threshold $\frac12$ is replaced by another number strictly between $0$ and $1$. With threshold $0$ or $1$, the emptiness problem becomes decidable: apply what I wrote above about nonprobabilistic automata.

While probabilistic automata are reactive, labelled Markov chains are generative:
Now for each state, the probabilities of all outgoing transitions sum up to $1$. There are no input words and no accepting states. Instead, in any state, the labelled Markov chain autonomously picks an outgoing transition and emits the letter that the transition is labelled with. For instance, in state $1$, it emits $a$ with probability $\frac14$, and $b$ with probability $\frac12 + \frac14$. This generalizes to longer words in the natural way. For instance, starting in state $1$, the word $bb$ is emitted with probability $\frac12 \cdot \frac12 + \frac12 \cdot \frac14 + \frac14 \cdot \frac13 + \frac14 \cdot \frac16$. In this way, for each number $n$, the labelled Markov chain defines a probability distribution over words of length $n$.
Given two labelled Markov chains, the equivalence problem asks if for each word $w$ the chains emit $w$ with the same probability.
The following theorem goes back to a 1961 paper by Marcel-Paul Sch├╝tzenberger and was subsequently rediscovered many times:
The equivalence problem is decidable in polynomial time.
The algorithm is based on linear algebra. Loosely speaking, it iteratively discovers equivalent states and, more generally, equivalent linear combinations of states. In this way one can also check two probabilistic automata for equivalence, where equivalence means that for each word $w$ the automata accept $w$ with the same probability. More generally, the equivalence-checking algorithm works for weighted automata, which are similar to labelled Markov chains and probabilistic automata except that the numbers do not have to be probabilities. Equivalence checking is used to check randomized protocols for anonymity and obliviousness, properties that are hard to formalize otherwise.

As a rule of thumb, equality questions about probabilistic models are decidable, and inequality questions are undecidable. More about that in later posts, such as this one.


Popular posts from this blog

Oxford Admissions

An initial draft of this post was about how to make rankings more meaningful, a piece of mathsy computer science, as you expect it from this blog. My motivation is personal: I'm involved in selecting CS undergraduate students. Some people might be curious how Oxford admissions work: it's certainly a favourite subject for UK politicians and news media. Therefore I decided to postpone my original plan and to write this post about Oxford admissions. I hope I'm not playing with too much fire and the blog will not suddenly become famous for the wrong reasons!

The tenor in newspapers and political campaigns is that the Oxbridge admissions process is “opaque” and unfair. Here I am going to offer transparency and some comments on fairness. The views expressed here are my own, and may not necessarily coincide with the university's views.

Oxford's goal is to admit the strongest applicants. One can disagree with this basic premise, but we try to admit those applicants who w…

Equivalence Checking

There is a compact data structure for words: automata. Finite automata can “store” many words, even infinitely many—in the sense that the language of a finite automaton can be infinite. This powerful feature makes automata ubiquitous in computer science. Lecture notes by Javier Esparza emphasize this view of automata as data structures.

The most fundamental algorithmic problems on automata are:
operations, such as computing set union or complement of the languages of automata; tests, such as checking their languages for equality. In this post I focus on the latter: equivalence checking. In general, equivalence checking for automata is PSPACE-complete, which is excusable considering how compact and flexible data structures they are. One can check two deterministic finite automata for equivalence in polynomial time, by searching their product.

Less known is the fact that one can efficiently check much wider classes of automata for equivalence, including unambiguous automata, probab…

Unambiguous Automata: From PSPACE to P

Computer science is about leveraging mathematical structure, for instance, in order to accelerate algorithms. More often than we'd like we can't accelerate much: For instance, checking two NFAs for language inclusion or equivalence is PSPACE-complete. Even the problem whether an NFA accepts all words is PSPACE-complete. For DFAs, those problems are easy. This means that for NFAs we can't do much better than determinizing (using the subset construction and incurring an exponential blowup) and solving the resulting DFA problem.

In this post I'll discuss an automata problem that seems to call for determinization and is, in fact, PSPACE-complete for NFAs. But there is an efficient algorithm for unambiguous automata.

Here is an example of an unambiguous automaton:
The notion of accepting states is not used in this post. By unambiguousness I just mean that the automaton has no diamonds, that is, for any states $q, r$, any word $w$ labels at most one path from $q$ to $r$. (…