Probabilistic Algorithms

A probabilistic algorithm uses the outcome of a random process to influence execution, which can be helpful for certain kinds of predictions

Why would this ever be useful? Sometimes calculating the best choice takes too much time, and estimating it always introduces bias

For example, determining information about individuals in a large population can be done quicker if we use random sampling

Definition: A probabilistic Turing machine $M$ is a type of nondeterministic Turing machine in which each nondeterministic step is called a coin-flip step and has two legal next moves

We assign a probability to each branch $b$ of $M$‘s computation on input $w$ as $\text{Pr}[b]=2^{-k}$ where $k$ is the number of coin-flip steps that occur on branch $b$

Then, $\text{Pr}[M\text{ accepts }w]={\sum }_{b\text{ is accepting}}^{}\text{Pr}[b]$

Definition: $M$ decides language A with probability $ϵ$ if $w\in A⟹\text{Pr}[M\text{ accepts }w]\ge 1-ϵ$ and $w\notin A⟹\text{Pr}[M\text{ rejects }w]\ge 1-ϵ$

We also consider error probability bounds as a function of $n$, like $ϵ=2^{-n}$ which is exponentially small error

We measure time and space complexity as with any nondeterministic Turing machine, taking the worst case computation branch on each input

Definition: $\mathbf{BPP}$ is the class of languages decidable by probabilistic polynomial time Turing machines with an error probability of $C$

This class is equivalent for any $C<\frac{1}{2}$ by virtue of the amplification lemma

Lemma: Let $ϵ$ be a fixed constant with $0<ϵ<\frac{1}{2}$, then for any polynomial $p(n)$, a probabilistic Turing machine $M_1$ with error $ϵ$ has an equivalent machine $M_2$ with error $2^{-p(n)}$

The gist of this result is we can simply repeat the same computation $p(n)$ times and take the majority result, which reduces the error and ultimately still runs in polynomial time

Primality

While a polynomial time algorithm for testing primality exists, the most practical algorithms are probabilistic

The most obvious way to test primality is by testing for factors, but this is not known to be possible in probabilistic polynomial time

Definition: For any $p$ greater than 1, we say that two numbers are equivalent modulo p if they differ by a multiple of $p$, in which case we write $x\equiv y(\mathrm{mod}p)$

Every number is equivalent modulo $p$ to some member of the set ${\mathcal{Z}}_p=\{0,\dots ,p-1\}$, and for convenient we also write ${\mathcal{Z}}_p^{+}=\{1,\dots ,p-1\}$

The main idea of this algorithm uses Fermat’s little theorem

Theorem: If $p$ is prime and $a\in {\mathcal{Z}}_p^{+}$, then $a^{p-1}\equiv 1(\mathrm{mod}p)$

We use this to derive a Fermat test, where we say $p$ passes the Fermat test at $a$ if $a^{p-1}\equiv 1(\mathrm{mod}p)$

Definition: A number is pseudoprime if it passes Fermat tests for all smaller a’s relatively prime to it

The pseudoprime numbers are identical to the prime numbers with the exception of the infrequent Carmichael numbers

$PSEUDOPRIME=$ “On input $p$:

1. Select $a_1,\dots ,a_k$ randomly in ${\mathcal{Z}}_p^{+}$
2. Compute $a_i^{p-1}\text{ mod }p$ for each $i$
3. Accept if all computed values are 1”

Because a number that is not pseudoprime it must fail at least half of the tests (not shown here), the probability of a false positive is at most $2^{-k}$

Modular exponentiation is computable in polynomial time, so this is a probabilistic polynomial time algorithm

To convert this to a full primality algorithm, we use the principle that the number 1 has exactly two square roots, 1 and -1, modulo any prime $p$, but will always have four or more for many composite numbers, including all Carmichael numbers

Because of this, if $p$ passes the Fermat test at $a$, $a^{p-1}\text{ mod }p=1$, and we can calculate the square root of $1$ by dividing the degree of the exponent by 2 until we get a different number (starting with $a^{(p-1)/2}\text{ mod }p$)

$PRIME=$ “On input $p$:

1. If $p$ is even, accept if $p=2$ and reject otherwise
2. Select $a_1,\dots ,a_k$ randomly in ${\mathcal{Z}}_p^{+}$
3. For each $i$ from 1 to $k$:
4. Compute $a_i^{p-1}\text{ mod }p$ and reject if different from 1
5. Let $p-1=s\cdot 2^l$ where $s$ is odd and compute $a_i^{s\cdot 2^0},\dots ,a_i^{s\cdot 2^l}$
6. If some element of this sequence is not 1, find the last element that is not 1 and reject if that element is not $-1$
7. If the test has not rejected at this point, accept”

Let’s demonstrate that this works as intended, and the maximum error probability is $2^{-k}$

We say $a_i$ is a (compositeness) witness if either test 1 or 2 rejects (stage 4 and 6 respectively)

First, we see that if $p$ is an odd prime number, then $\text{Pr}[PRIME\text{ accepts }p]=1$

$a_i$ cannot be a test 1 witness because of Fermat’s little theorem
$a_i$ cannot be a test 2 witness because this would imply some $b^2-1\equiv 0(\mathrm{mod}p)$, which leads to $(b-1)(b+1)=cp$, meaning $p$ cannot be prime

To prove the error bound, we use the Chinese remainder theorem, which says that if $p$ and $q$ are relatively prime, then each number $r\in {\mathcal{Z}}_{pq}$ corresponds to a unique pair $(a,b)$ such that $r\equiv a(\mathrm{mod}p)$ and $r\equiv b(\mathrm{mod}q)$

We show that $\text{Pr}[a\text{ is a witness}]\ge \frac{1}{2}$ for a random $a\in {\mathcal{Z}}_p^{+}$ by finding a unique witness for each nonwitness

In every nonwitness, the test 2 sequence consists of either all 1s or all 1s along with a -1 at some position

Among all nonwitnesses with a -1 in some test 2 position, we find the witness $h$ in which -1 appears in the largest position $j$, such that $h^{s\cdot 2^j}\equiv -1(\mathrm{mod}p)$

Because $p$ is composite, either $p$ is the power of a prime or we can write $p$ as the product of $q$ and $r$ relatively prime

The Chinese remainder theorem tells us that some number $t$ exists such that,
$t\equiv h(\mathrm{mod}q)$
$t\equiv 1(\mathrm{mod}r)$

Therefore,
$t^{s\cdot 2^j}\equiv -1(\mathrm{mod}q)$
$t^{s\cdot 2^j}\equiv 1(\mathrm{mod}r)$

Since $x\equiv a(\mathrm{mod}p)⟺x\equiv a(\mathrm{mod}q)\text{ and }x\equiv a(\mathrm{mod}r)$, we see that $t^{s\cdot 2^j}\not\equiv \pm 1(\mathrm{mod}p)$ and $t^{s\cdot 2^{j+1}}\equiv 1(\mathrm{mod}p)$, so $t$ is a witness

Now, note that for each nonwitness $d$, $d^{s\cdot 2^j}\equiv \pm 1(\mathrm{mod}p)$ and $d^{s\cdot 2^{j+1}}\equiv 1(\mathrm{mod}p)$, due to the way we chose $j$

Then, $(dt{)}^{s\cdot 2^j}\not\equiv \pm 1(\mathrm{mod}p)$ and $(dt{)}^{s\cdot 2^{j+1}}\equiv 1(\mathrm{mod}p)$, so $dt\text{ mod }p$ is a witness

If $d_1$ and $d_2$ are distinct nonwitnesses, then $d_{1}t\text{ mod }p\ne d_{2}t\text{ mod }p$, since if $t{d}_1\text{ mod }p=t{d}_2\text{ mod }p$ then $d_1=t^{s\cdot 2^{j+1}}{d}_1\text{ mod }p=t^{s\cdot 2^{j+1}}{d}_2\text{ mod }p=d_2$

Thus we’ve proven our analysis in the case where $p$ is not a prime number

Otherwise $p=q^e$ with $q$ prime and $e>1$, in which case we let $t=1+q^{e-1}$

$t^p=(1+q^{e-1}{)}^p=1+p\cdot q^{e-1}+\text{multiples of higher powers of }{q}^{e-1}$ which is by definition equivalent to $1\text{ mod }p$

Hence $t$ is a test 1 witness, because if $t^{p-1}\equiv 1(\mathrm{mod}p)$, then $t^p\equiv t/{\equiv }_1(\mathrm{mod}p)$

Then we obtain our other witnesses as above, and our bound is proven

Theorem: $PRIMES\in \text{BPP}$

This specific algorithm has a one-sided error, in the sense that rejections are absolute

This is a common feature, so there is a special complexity class

Definition: $\mathbf{RP}$ is the class of language decidable by probabilistic polynomial time Turing machines where inputs in the language are accepted with a probability of at least $\frac{1}{2}$, and inputs not in the language are rejected with a probability of $1$

Our primality algorithm shows that $COMPOSITES\in \text{RP}$

Again, we can use a probability amplification technique on these algorithms

Read-Once Branching Programs

We examine branching programs as an interesting example of a problem that can apparently only be solved in polynomial time with probabilism

Definition: A branching program is a directed acyclic graph where all query nodes are labeled by variables with two outgoing edges labeled 0 and 1, except for two output nodes

A branching program determines a Boolean function on the values of the query nodes

Branching programs are related to the class $\text{L}$ in a way that is analogous to the relationship between Boolean circuits and the class $\text{P}$

The problem of testing equivalence for branching programs is $\text{coNP}$-complete

Here we consider a read-once branching program, which can query each variable at most one time on any execution path

Theorem: $E{Q}_{\text{ROBP}}$ is in $\text{BPP}$

Our algorithm works by assigning random values to the variables

Instead of Boolean values, we modify our scheme to handle non-Boolean assignments to the variables and allow the values to propagate through the graph, summing the edges flowing into a single node, such that the result is a polynomial $p(x_1,\dots ,x_m)$

Let $\mathcal{F}$ be a finite field with at least $3m$ elements (the coefficient is arbitrary), where $m$ is the number of variables of the read-once branching programs we’re investigating

$D=$ “On input $⟨B_1,B_2⟩$:

1. Select $a_1,\dots ,a_m$ at random from $\mathcal{F}$
2. Accept if $p_1(a_1,\dots ,a_m)=p_2(a_1,\dots ,a_m)$”

We show this decides $E{Q}_{\text{ROBP}}$ with an error probability of at most $\frac{1}{3}$

Because $B$ is read-once, we may write $p$ as a sum of product terms $y_1{y}_2\dots y_m$ where each $y_i$ is $x_i,(1-x_i),$ or 1, and where each product term corresponds to a path in $B$ from the start node to the output node labeled 1

We can then rewrite $p$ into an equivalent polynomial $q$ such that no product terms contain $y_i=1$, by repeatedly splitting terms into the sum of a term with $y_i=x_i$ and $y_i=1-x_i$

The result is that $q$ contains a product term for each assignment on which $B$ evaluates to 1

If $B_1$ and $B_2$ are equivalent then the polynomials $q_1$ and $q_2$ must be the same, and therefore $p_1$ and $p_2$ are equal on every assignment

To show the probability that $D$ rejects nonequivalent branching programs, we need some results on polynomials

First, a degree-$d$ polynomial $p$ on a single variable $x$ either has at most $d$ roots or is everywhere equal to 0 (we can prove this simply by induction)

Lemma: Now let $\mathcal{F}$ be a finite field with $f$ elements and let $p$ be a nonzero polynomial on $x_1,\dots ,x_m$, with degrees at most $d$; if $a_1,\dots ,a_m$ are selected randomly in $\mathcal{F}$, then $\text{Pr}[p(a_1,\dots ,a_m)=0]\le md/f$

We prove this inductively

For $m=1$, $p$ has at most $d$ roots so the probability that $a_1$ is one of them is at most $d/f$

Assume true for $m-1$
Let $x_1$ be one of $p$‘s variables, and let $p_i$ be the polynomial comprising the terms of $p$ containing the terms of $p$ containing $x_1^i$ but where $x_1^i$ has been factored out

Then, $p=p_0+x_1{p}_1+x_1^2{p}_2+\cdots +x_1^d{p}_d$

If $p(a_1,\dots ,a_m)=0$ then either all $p_i$ evaluate to 0 or some doesn’t and $a_1$ is a root of the single variable polynomial obtained by evaluating $p$ on $a_2,\dots ,a_m$

The probability that all $p_i$ evaluate to 0 is at most the probability that some $p_j$ evaluates to 0, which by our induction hypothesis is at most $(m-1)d/f$

If some $p_i$ doesn’t evaluate to 0, then this reduces to a nonzero polynomial in the single variable $x_1$, which our base case shows has probability at most $d/f$

Thus the probability that $a_1,\dots ,a_m$ is a root of the polynomial is at most $md/f$ proving our lemma

This means the probability that our random assignment is a root of $B_2-B_1$ is at most $\frac{1}{3}$, meaning $D$ rejects with a probability of at least $\frac{2}{3}$

Pseudorandom Generators

It’s important to note that true randomness is generally difficult or impossible to obtain

Practical implementations use pseudorandom generators, which are deterministic algorithms whose output appears random

Pseudorandom generators can never be truly random, but may satisfy various statistical tests

Proving an algorithm works equally well with pseudorandom generators is difficult, and may not always hold

Pseudorandom generators have been devised that can produce results indistinguishable from truly random results by any test that operates in polynomial time, assuming that one-way functions exist