• We call a probabilistic, expected polynomial-time algorithm a Las

Vegas algorithm for recognizing L if it computes f correctly on all

inputs x.

One also says an Atlantic City algorithm has two-sided error, a Monte

Carlo algorithm has one-sided error, and a Las Vegas algorithm has zero-

sided error.

Exercise 7.6. Show that any language recognized by a Las Vegas algorithm

is also recognized by a Monte Carlo algorithm, and that any language rec-

ognized by a Monte Carlo algorithm is also recognized by an Atlantic City

algorithm.

Exercise 7.7. Show that if L is recognized by an Atlantic City algorithm

that runs in expected polynomial time, then it is recognized by an Atlantic

City algorithm that runs in strict polynomial time, and whose error proba-

bility is at most 2’n on inputs of length n.

Exercise 7.8. Show that if L is recognized by a Monte Carlo algorithm that

runs in expected polynomial time, then it is recognized by a Monte Carlo

algorithm that runs in strict polynomial time, and whose error probability

is at most 2’n on inputs of length n.

Exercise 7.9. Show that a language is recognized by a Las Vegas algo-

rithm i¬ the language and its complement are recognized by Monte Carlo

algorithms.

Exercise 7.10. Show that if L is recognized by a Las Vegas algorithm that

runs in strict polynomial time, then L may be recognized in deterministic

polynomial time.

Exercise 7.11. Suppose that for a given language L, there exists a prob-

abilistic algorithm A that runs in expected polynomial time, and always

outputs either 0 or 1. Further suppose that for some constants ± and c,

where

• ± is a rational number with 0 ¤ ± < 1, and

• c is a positive integer,

and for all su¬ciently large n, and all inputs x of length n, we have

• if x ∈ L, then P[A(x) = 1] ¤ ±, and

/

• if x ∈ L, then P[A(x) = 1] ≥ ± + 1/nc .

(a) Show that there exists an Atlantic City algorithm for L.

(b) Show that if ± = 0, then there exists a Monte Carlo algorithm for L.

158 Probabilistic algorithms

7.3 Flipping a coin until a head appears

In this and subsequent sections of this chapter, we discuss a number of

speci¬c probabilistic algorithms.

Let us begin with the following simple algorithm (which was already pre-

sented in Example 7.1) that essentially ¬‚ips a coin until a head appears:

repeat

b ←R {0, 1}

until b = 1

Let X be a random variable that represents the number of loop iterations

made by the algorithm. It should be fairly clear that X has a geometric

distribution, where the associated probability of success is 1/2 (see Exam-

ple 6.30). However, let us derive this fact from more basic principles. De¬ne

random variables B1 , B2 , . . . , where Bi represents the value of the bit as-

signed to b in the ith loop iteration, if X ≥ i, and otherwise. Clearly,

exactly one Bi will take the value 1, in which case X takes the value i.

Evidently, for each i ≥ 1, if the algorithm actually enters the ith loop

iteration, then Bi is uniformly distributed over {0, 1}, and otherwise, Bi = .

That is:

P[Bi = 0 | X ≥ i] = 1/2, P[Bi = 1 | X ≥ i] = 1/2,

| X < i] = 1.

P[Bi =

From this, we see that

P[X ≥ 1] = 1, P[X ≥ 2] = P[B1 = 0 | X ≥ 1]P[X ≥ 1] = 1/2,

P[X ≥ 3] = P[B2 = 0 | X ≥ 2]P[X ≥ 2] = (1/2)(1/2) = 1/4,

and by induction on i, we see that

P[X ≥ i] = P[Bi’1 = 0 | X ≥ i ’ 1]P[X ≥ i ’ 1] = (1/2)(1/2i’2 ) = 1/2i’1 ,

from which it follows (see Exercise 6.54) that X has a geometric distribution

with associated success probability 1/2.

Now consider the expected value E[X]. By the discussion in Example 6.35,

we have E[X] = 2. If Y denotes the total running time of the algorithm,

then Y ¤ cX for some constant c, and hence

E[Y ] ¤ cE[X] = 2c,

and we conclude that the expected running time of the algorithm is a con-

stant, the exact value of which depends on the details of the implementation.

7.4 Generating a random number from a given interval 159

[Readers who skipped §7.1.1 may also want to skip this paragraph.]

As was argued in Example 7.1, the above algorithm halts with prob-

ability 1. To make the above argument completely rigorous, we

should formally justify that claim that the conditional distribution

of Bi , given that X ≥ i, is uniform over {0, 1}. We do not wish to

assume that the values of the Bi are located at pre-determined posi-

tions of the execution path; rather, we shall employ a more generally

applicable technique. For any i ≥ 1, we shall condition on a partic-

ular partial execution path „ that drives the algorithm to the point

where it is just about to sample the bit Bi , and show that in this

conditional probability distribution, Bi is uniformly distributed over

{0, 1}. To do this rigorously in our formal framework, let us de¬ne

the event A„ to be the event that „ is a pre¬x of the execution path.

If |„ | = , then the events A„ , A„ § (Bi = 0), and A„ § (Bi = 1) are

determined by the ¬rst +1 bits of the execution path. We can then

consider corresponding events in a probabilistic experiment wherein

we observe the behavior of the algorithm on a random ( + 1)-bit ex-

ecution path (see Exercise 7.2). In the latter experiment, it is clear

that the conditional probability distribution of Bi , given that the

¬rst bits of the actual execution path σ agree with „ , is uniform

over {0, 1}, and thus, the same holds in the original probability dis-

tribution. Since this holds for all relevant „ , it follows (by a discrete

version of Exercise 6.13) that it holds conditioned on X ≥ i.

We have analyzed the above algorithm in excruciating detail. As we

proceed, many of these details will be suppressed, as they can all be handled

by very similar (and completely routine) arguments.

7.4 Generating a random number from a given interval

Suppose we want to generate a number n uniformly at random from the

interval {0, . . . , M ’ 1}, for a given integer M ≥ 1.

If M is a power of 2, say M = 2k , then we can do this directly as follows:

generate a random k-bit string s, and convert s to the integer I(s) whose

base-2 representation is s; that is, if s = bk’1 bk’2 · · · b0 , where the bi are

bits, then

k’1

b i 2i .

I(s) :=

i=0

In the general case, we do not have a direct way to do this, since we can

only directly generate random bits. However, suppose that M is a k-bit

number, so that 2k’1 ¤ M < 2k . Then the following algorithm does the

job:

160 Probabilistic algorithms

Algorithm RN:

repeat

s ←R {0, 1}—k

n ← I(s)

until n < M

output n

Let X denote the number of loop iterations of this algorithm, Y its running

time, and N its output.

In every loop iteration, n is uniformly distributed over {0, . . . , 2k ’1}, and

the event n < M occurs with probability M/2k ; moreover, conditioning on

the latter event, n is uniformly distributed over {0, . . . , M ’ 1}. It follows

that X has a geometric distribution with an associated success probability

p := M/2k ≥ 1/2, and that N is uniformly distributed over {0, . . . , M ’ 1}.

We have E[X] = 1/p ¤ 2 (see Example 6.35) and Y ¤ ckX for some

implementation-dependent constant c, from which it follows that

E[Y ] ¤ ckE[X] ¤ 2ck.

Thus, the expected running time of Algorithm RN is O(k).

Hopefully, the above argument is clear and convincing. However, as in

the previous section, we can derive these results from more basic principles.

De¬ne random variables N1 , N2 , . . . , where Ni represents the value of n in

the ith loop iteration, if X ≥ i, and otherwise.

Evidently, for each i ≥ 1, if the algorithm actually enters the ith loop

iteration, then Ni is uniformly distributed over {0, . . . , 2k ’1}, and otherwise,

Ni = . That is:

P[Ni = j | X ≥ i] = 1/2k (j = 0, . . . , 2k ’ 1),

| X < i] = 1.

P[Ni =