n ←R {0, . . . , j ’ 1}

until n = 0 or n = 1

Show that this algorithm halts with probability 1, and that its expected

running time exists (and is equal to some implementation-dependent con-

stant).

7.6 Generating a random non-increasing sequence

The following algorithm, Algorithm RS, will be used in the next section as

a fundamental subroutine in a beautiful algorithm (Algorithm RFN) that

168 Probabilistic algorithms

generates random numbers in factored form. Algorithm RS takes as input

an integer M ≥ 2, and runs as follows:

Algorithm RS:

n0 ← M

i←0

repeat

i←i+1

ni ←R {1, . . . , ni’1 }

until ni = 1

t←i

Output (n1 , . . . , nt )

We analyze ¬rst the output distribution, and then the running time.

7.6.1 Analysis of the output distribution

Let N1 , N2 , . . . be random variables denoting the choices of n1 , n2 , . . . (for

completeness, de¬ne Ni := 1 if loop i is never entered).

A particular output of the algorithm is a non-increasing chain (n1 , . . . , nt ),

where n1 ≥ n2 ≥ · · · ≥ nt’1 > nt = 1. For any such chain, we have

P[N1 = n1 § · · · § Nt = nt ] = P[N1 = n1 ]P[N2 = n2 | N1 = n1 ] · · ·

P[Nt = nt | N1 = n1 § · · · § Nt’1 = nt’1 ]

11 1

· · ··· ·

= . (7.3)

M n1 nt’1

This completely describes the output distribution, in the sense that we

have determined the probability with which each non-increasing chain ap-

pears as an output. However, there is another way to characterize the output

distribution that is signi¬cantly more useful. For j = 2, . . . , M , de¬ne the

random variable Ej to be the number of occurrences of j among the Ni .

The Ej determine the Ni , and vice versa. Indeed, EM = eM , . . . , E2 = e2

i¬ the output of the algorithm is the non-increasing chain

(M, . . . , M , M ’ 1, . . . , M ’ 1, . . . , 2, . . . , 2, 1).

eM times eM ’1 times e2 times

From (7.3), we can therefore directly compute

M

1 1

§ . . . § E2 = e2 ] =

P[EM = eM . (7.4)

j ej

M

j=2

7.6 Generating a random non-increasing sequence 169

Notice that we can write 1/M as a telescoping product:

M

M ’1 M ’2

1 21

· · ··· · · = (1 ’ 1/j),

=

M ’1

M M 32

j=2

so we can re-write (7.4) as

M

j ’ej (1 ’ 1/j).

P[EM = eM § · · · § E2 = e2 ] = (7.5)

j=2

Notice that for j = 2, . . . , M ,

j ’ej (1 ’ 1/j) = 1,

ej ≥0

and so by (a discrete version of) Theorem 6.1, the variables Ej are mutually

independent, and for all j = 2, . . . , M and integers ej ≥ 0, we have

P[Ej = ej ] = j ’ej (1 ’ 1/j). (7.6)

In summary, we have shown that the variables Ej are mutually indepen-

dent, where for j = 2, . . . , M , the variable Ej +1 has a geometric distribution

with an associated success probability of 1 ’ 1/j.

Another, perhaps more intuitive, analysis of the joint distribution of the

Ej runs as follows. Conditioning on the event EM = eM , . . . , Ej+1 = ej+1 ,

one sees that the value of Ej is the number of times the value j appears in

the sequence Ni , Ni+1 , . . . , where i = eM + · · · + ej+1 + 1; moreover, in this

conditional probability distribution, it is not too hard to convince oneself

that Ni is uniformly distributed over {1, . . . , j}. Hence the probability that

Ej = ej in this conditional probability distribution is the probability of

getting a run of exactly ej copies of the value j in an experiment in which

we successively choose numbers between 1 and j at random, and this latter

probability is clearly j ’ej (1 ’ 1/j).

7.6.2 Analysis of the running time

Let T be the random variable that takes the value t when the output is

(n1 , . . . , nt ). Clearly, it is the value of T that essentially determines the

running time of the algorithm.

With the random variables Ej de¬ned as above, we see that T = 1 +

M

j=2 Ej . Moreover, for each j, Ej + 1 has a geometric distribution with

170 Probabilistic algorithms

associated success probability 1 ’ 1/j, and hence

1 1

’1=

E[Ej ] = .

1 ’ 1/j j’1

Thus,

M ’1

M M

1 dy

+ O(1) ∼ log M.

E[T ] = 1 + E[Ej ] = 1 + =

j y

1

j=2 j=1

Intuitively, this is roughly as we would expect, since with probability 1/2,

each successive ni is at most one half as large as its predecessor, and so after

O(len(M )) steps, we expect to reach 1.

To complete the running time analysis, let us consider the total number

of times X that the main loop of Algorithm RN in §7.4 is executed. For

i = 1, 2, . . . , let Xi denote the number of times that loop is executed in the

ith loop of Algorithm RS, de¬ning this to be zero if the ith loop is never

reached. So X = ∞ Xi . Arguing just as in §7.5, we have

i=1

E[Xi ] ¤ 2 P[T ≥ i] = 2E[T ] ∼ 2 log M.

E[X] =

i≥1 i≥1

To ¬nish, if Y denotes the running time of Algorithm RS on input M ,

then we have Y ¤ c len(M )(X + 1) for some constant c, and hence E[Y ] =

O(len(M )2 ).

Exercise 7.20. Show that when Algorithm RS runs on input M , the ex-

pected number of (not necessarily distinct) primes in the output sequence

is ∼ log log M .

Exercise 7.21. For j = 2, . . . , M , let Fj := 1 if j appears in the output

of Algorithm RS on input M , and let Fj := 0 otherwise. Determine the

joint distribution of the Fj . Using this, show that the expected number of

distinct primes appearing in the output sequence is ∼ log log M .

7.7 Generating a random factored number

We now present an e¬cient algorithm that generates a random factored