As for the distribution of X, it follows from a simple induction argument

that P[X ≥ i] = q i’1 , where q := 1 ’ p; indeed, P[X ≥ 1] = 1, and for i ≥ 2,

we have

P[X ≥ i] = P[Ni’1 ≥ M | X ≥ i ’ 1]P[X ≥ i ’ 1] = q · q i’2 = q i’1 .

It follows that X has a geometric distribution with associated success prob-

ability p (see Exercise 6.54).

As for the distribution of N , by (a discrete version of) Exercise 6.13, it

su¬ces to show that for all i ≥ 1, the conditional distribution of N given that

7.4 Generating a random number from a given interval 161

X = i is uniform on {0, . . . , M ’ 1}. Observe that for any j = 0, . . . , M ’ 1,

we have

P[N = j § X = i] P[Ni = j § X ≥ i]

P[N = j | X = i] = =

P[Ni < M § X ≥ i]

P[X = i]

1/2k

P[Ni = j | X ≥ i]P[X ≥ i]

= =

M/2k

P[Ni < M | X ≥ i]P[X ≥ i]

= 1/M.

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

To make the above argument completely rigorous, we should ¬rst

show that the algorithm halts with probability 1, and then show

that the conditional distribution of Ni , given that X ≥ i, is indeed

uniform on {0, . . . , 2k ’ 1}, as claimed above. That the algorithm

halts with probability 1 follows from the fact that in every loop iter-

ation, there is at least one choice of s that will cause the algorithm

to halt. To analyze the conditional distribution on Ni , one considers

various conditional distributions, conditioning on particular partial

execution paths „ that bring the computation just to the beginning

of the ith loop iteration; for any particular such „ , the ith loop iter-

ation will terminate in at most := |„ | + ck steps, for some constant

c. Therefore, the conditional distribution of Ni , given the partial ex-

ecution path „ , can be analyzed by considering the execution of the

algorithm on a random -bit execution path (see Exercise 7.2). It is

then clear that the conditional distribution of Ni given the partial

execution path „ is uniform over {0, . . . , 2k ’ 1}, and since this holds

for all relevant „ , it follows (by a discrete version of Exercise 6.13)

that the conditional distribution of Ni , given that the ith loop is

entered, is uniform over {0, . . . , 2k ’ 1}.

Of course, by adding an appropriate value to the output of Algorithm

RN, we can generate random numbers uniformly in an interval {A, . . . , B},

for given A and B. In what follows, we shall denote the execution of this

algorithm as

n ←R {A, . . . , B}.

We also mention the following alternative approach to generating a ran-

dom number from an interval. Given a positive k-bit integer M , and a

parameter t > 0, we do the following:

Algorithm RN :

s ←R {0, 1}—(k+t)

n ← I(s) mod M

output n

Compared with Algorithm RN, Algorithm RN has the advantage that

162 Probabilistic algorithms

there are no loops ” it halts in a bounded number of steps; however, it

has the disadvantage that its output is not uniformly distributed over the

interval {0, . . . , M ’ 1}. Nevertheless, the statistical distance between its

output distribution and the uniform distribution on {0, . . . , M ’ 1} is at

most 2’t (see Example 6.27 in §6.8). Thus, by choosing t suitably large, we

can make the output distribution “as good as uniform” for most practical

purposes.

Exercise 7.12. Prove that no probabilistic algorithm that always halts in

a bounded number of steps can have an output distribution that is uniform

on {0, . . . , M ’ 1}, unless M is a power of 2.

Exercise 7.13. Let A1 and A2 be probabilistic algorithms such that, for

any input x, the random variables A1 (x) and A2 (x) take on one of a ¬nite

number of values, and let δx be the statistical distance between A1 (x) and

A2 (x). Let B be any probabilistic algorithm that always outputs 0 or 1. For

for i = 1, 2, let Ci be the algorithm that given an input x, ¬rst runs Ai on

that input, obtaining a value y, then it runs B on input y, obtaining a value

z, which it then outputs. Show that |P[C1 (x) = 1] ’ P[C2 (x) = 1]| ¤ δx .

7.5 Generating a random prime

Suppose we are given an integer M ≥ 2, and want to generate a random

prime between 2 and M . One way to proceed is simply to generate random

numbers until we get a prime. This idea will work, assuming the existence

of an e¬cient algorithm IsPrime that determines whether or not a given

integer n > 1 is prime.

Now, the most naive method of testing if n is prime is to see if any of the

numbers between 2 and n ’ 1 divide n. Of course, one can be slightly more

clever, and only perform this divisibility check for prime numbers between 2

√

and n (see Exercise 1.1). Nevertheless, such an approach does not give rise

to a polynomial-time algorithm. Indeed, the design and analysis of e¬cient

primality tests has been an active research area for many years. There is, in

fact, a deterministic, polynomial-time algorithm for testing primality, which

we shall discuss later, in Chapter 22. For the moment, we shall just assume

we have such an algorithm, and use it as a “black box.”

Our algorithm to generate a random prime between 2 and M runs as

follows:

7.5 Generating a random prime 163

Algorithm RP:

repeat

n ←R {2, . . . , M }

until IsPrime(n)

output n

We now wish to analyze the running time and output distribution of

Algorithm RP on input M . Let k := len(M ).

First, consider a single iteration of the main loop of Algorithm RP, viewed

as a stand-alone probabilistic experiment. For any ¬xed prime p between

2 and M , the probability that the variable n takes the value p is precisely

1/(M ’ 1). Thus, every prime is equally likely, and the probability that n

is a prime is precisely π(M )/(M ’ 1).

Let us also consider the expected running time µ of a single loop iteration.

To this end, de¬ne Wn to be the running time of algorithm IsPrime on input

n. Also, de¬ne

M

1

WM := Wn .

M ’1

n=2

That is, WM is the average value of Wn , for a random choice of n ∈

{2, . . . , M }. Thus, µ is equal to WM , plus the expected running time of

Algorithm RN, which is O(k), plus any other small overhead, which is also

O(k). So we have µ ¤ WM + O(k), and assuming that WM = „¦(k), which

is perfectly reasonable, we have µ = O(WM ).

Next, let us consider the behavior of Algorithm RP as a whole. From the

above discussion, it follows that when this algorithm terminates, its output

will be uniformly distributed over the set of all primes between 2 and M . If

T denotes the number of loop iterations performed by the algorithm, then

E[T ] = (M ’ 1)/π(M ), which by Chebyshev™s theorem (Theorem 5.1) is

˜(k).

So we have bounded the expected number of loop iterations. We now

want to bound the expected overall running time. For i ≥ 1, let Xi denote

the amount of time (possibly zero) spent during the ith loop iteration of the

algorithm, so that X := i≥1 Xi is the total running time of Algorithm RP.

Note that

E[Xi ] = E[Xi | T ≥ i]P[T ≥ i] + E[Xi | T < i]P[T < i]

= E[Xi | T ≥ i]P[T ≥ i]

= µP[T ≥ i],

164 Probabilistic algorithms

because Xi = 0 when T < i and E[Xi | T ≥ i] is by de¬nition equal to µ.

Then we have

P[T ≥ i] = µE[T ] = O(kWM ).

E[X] = E[Xi ] = µ

i≥1 i≥1