Chapter 6

Randomization II

This recitation covers a number of examples of analyzing randomized algorithms, with a focus on high-
probability bounds for their span.

1 High Probability Bounds

We say that an algorithm terminates in O(f (n)) with high probability if, for any value of k > 0, the
algorithm terminates in O(k · f (n)) time with probability at least 1 − n1k .

2 Another Dice Game

Having won the previous dice game of Lucky 7s, Fatima has decided to play another game with a board
and a die. She starts with a number n on the board. On each round, Anna rolls the die to generate a
random integer d between 1 and 6. She then multiplies the number on the board by d4 (the number will
not always be an integer). The game ends when the number on the board is less than or equal to 1.

Task. Show that Fatima’s game ends in O(lg n) rounds with high probability.

Solution (Solution). We need to show that for any constant k, the probability of the game having ended
within O(k · lg n) rounds is at least 1 − n1k .
Consider that after r rounds, the number on the board is n multiplied by the values of r dice rolls,
each divided by 4. Let X be a random variable equal to the number on the board after r rolls, and Xi be
a random variable representing the number from the ith roll. Then the number on the board after r rolls
is:

Πri=1 Xi
X =n·
4r
Since all die rolls are independent of each other and n, we can say that:

Πri=1 E[Xi ]
E[X] = n ·
4r

As computed in lecture, the expected value of a single dice roll is 72 . Hence, each E[Xi ] = 7
2 and:

21
22 CHAPTER 6. RANDOMIZATION II

( 72 )r 7
E[X] = n · r
= n · ( )r
4 8
We can use Markov’s inequality to relate the probability of the number on the board being greater
than one with the expected number:

E[X]
P (X > 1) ≤
1
We want to find out when it is the case that the probability is low, which means that the probability
that the game ended (P (x ≤ 1)) is high. According to our definition of high probability, this means that
P (x > 1) should be n1k for every k. Hence:

7 1
n · ( )r = k
8 n
7 1
( )r = k+1
8 n
1
r = log 78
nk+1
r = log 78 n−(k+1)
r = −(k + 1) · log 78 n
lg n
r = −(k + 1) ·
lg 78

Which means that, after O(lg n) rounds, the has ended with high probability.

3 The Secret Algorithm

Task. Professor Christos has a secret algorithm which has O(lg n) span with high probability, and O(n)
span in the worst case. Prove that Prof. Christos’ algorithm has O(lg n) span in expectation.

Solution. Let “good” be the event that S(n) ∈ O(lg n), and “bad” be the event that S(n) ̸∈ O(lg n).
The definition of high probability states that for any k, the probability that we have O(k · lg n) span is
greater than or equal to 1 − n1k . Setting k = 3 yields that the “good” probability is at least 1 − n13 , while
the “bad” probability is at most 3 since O(3 · lg n) is the same as O(lg n).
Using the law of total expectation, we have:

E[S(n)] = E[S(n)|good]P (good) + E[S(n)|bad]P (bad)

= E[S(n)|good](1 − P (bad)) + E[S(n)|bad]P (bad)
Note that we know the following:
3. THE SECRET ALGORITHM 23

• E[S(n)|good] is upper bounded by O(lg n);

• E[S(n)|bad] is upper bounded by O(n); and
• p(bad) is upper bounded by n3 .
1

Therefore:

E[S(n)] ≤ O(lg n) · (1 − P (bad)) + O(n) · P (bad)

= O(lg n) + (O(n) − O(lg n)) · P (bad)
≤ O(lg n) + O(n) · P (bad)
1
≤ O(lg n) + O(n) · 3
n
1
= O(lg n) + O( 2 )
n
∈ O(lg n)

Task. Prof. Eduardo is trying to guess what Prof. Christos’ secret algorithm is. He comes up with the
following algorithm:

fun rec (n : int) =

if n <= 1 then 1
else case flip()
of true => rec(n/2) + 1
| false => rec(n-1) + 1
The flip function simulates a coin flip and returns true and false with equal probability. Could this
be Prof. Christos’ secret algorithm?

Solution. We want to show two things:

1. Prof. Eduardo’s algorithm has span O(n) in the worst case; and
2. Prof. Eduardo’s algorithm has span O(lg n) with high probability.
The first one is easy to see: the value of n decreases by at least 1 at every iteration. Therefore in the
worst case it will take n − 1 function calls to get from n to 1.
The second one can be shown as follows: we are interested in the probability of the function ter-
minating after at most k · lg n iterations where k is some positive integer. We can lower bound this
probability by assuming that if we get false, the value of n stays the same. Now this is just like the
skittles game.
Let X be a random variable indicating the value of the input to rec after r levels of recursion. We
need to lower bound P (X ≤ 1) in terms of r, since this is the probability that the algorithm would have
terminated at this point. We have:

3
E[X] = n · ( )r
4
24 CHAPTER 6. RANDOMIZATION II

Using Markov’s inequality, we get that P (x > 1) ≤ E[X]1 .

We would like to show that this is equal to n1k . Hence:

3 1
n · ( )r = k
4 n
Solving this yields r = (k + 1) log 43 n ∈ O(k · lg n). This finally gives us that

1
P (X ≤ 1) = 1 − P (X > 1) ≥ 1 −
nk
which is the high probability bound we desire.
Therefore this could be Prof. Christos’ secret algorithm!

4 Parallel Randomization
We have a function f , which takes an input of size n. f is a randomized function, which has a 12 chance
of halving the size of the input on each round and a chance of leaving it the same size. f terminates
when the input size is ≤ 1, as always. From what we have done so far, we know that a single call to f
will terminate in O(lg n) rounds with high probability.
Prof. Ryan is writing a brute-force algorithm, and he is using f on each of the different possible
solutions. His problem has n210 possible solutions, and he calls f , at the same time, on each of these n210
inputs of size n in parallel.
Prof. Ryan’s computer allows for one round of all running calls to f to take place each second – that
is, after one second, all calls to f will have run one round, after two seconds, they will each have run
two rounds, and so on.

Task. Prove that the number of seconds it takes for all the parallel calls to terminate is still in O(lg n)
with high probability.

Solution. To show that the overall brute-force algorithm terminates in O(lg n) seconds with high proba-
bility, we must be able to show that it terminates in (k · logn) seconds with at least probability 1 − n1k for
any adversarially-chosen constant k.
Because each subtask terminates in O(lg n) seconds with high probability, we know that each subtask
terminates in O(k ′ · lg n) seconds with probablity at least 1 − n1k′ , for any constant k ′ . Let’s call a subtask
“good” it if terminates within that bound, and call it “bad” if it violates that bound with probability
< n1k′ .
Because Prof. Ryan’s brute-force algorithm takes as long as the longest subtask, let’s call the overall
algorithm “bad” if any of the n210 subtasks is bad, i.e., the brute-force algorithm being bad is the union
of the subtasks being bad. By the union bound, the probability that the overall brute-force algorithm is
bad is at most:

210 1 1
Σni=1 = n210 · k′
nk ′ n
4. PARALLEL RANDOMIZATION 25

This bound is true regardless of whether or not the subtasks are independent.
Choose k ′ = k + 210, where k is our target constant in the high-probability bound for the overall
algorithm. Substituting this value into the above equation, we have that the probability that the brute-
force algorithm is bad is at most n210 · nk+210 1
= n1k as desired. But that means the overall brute-force
algorithm finishes in less than O((k + 210) · lg n) seconds with probability at least 1 − n1k . Because
(k + 210) · lg n ∈ O(k · lg n), this satisfies the requirements needed to be a high probability bound.