Part I
Basic concepts and examples of randomized algorithms
CZ.1.07/2.2.00/28.0041
Centrum interaktivn´ıch a multimedi´aln´ıch studijn´ıch opor pro inovaci v´yuky a efektivn´ı uˇcen´ı
FUTURE in INFORMATIC ERA
FUTURE in INFORMATICS ERA 2015
Prof. Jozef Gruska, DrSc
Wendesday, 14.00-15.40, C410
WEB PAGE of the LECTURE
http://www.fi.muni.cz/usr/gruska/random15
EXAM: You need to answer three questions out of five given.
EXERCISES/TUTORIALS
EXERCISES/TUTORIALS: Thursday 18.00-19.30, D205
TEACHER: Dr. Shenggen Zheng (in English), Dr. Jana Fabrikova (in Czech/English)
NOTE: Exercises/tutorials are not obligatory
CONTENTS - preliminary
1 Basic concepts and examples of randomized algorithms
2 Types and basic design methods for randomized algorithms
3 Basics of probability theory
4 Games and design of randomized algorithms
5 Basic techniques I: moments and deviations
6 Basic techniques II: tail probabilities inequalities
7 Probabilistic method I:
8 Markov chains - random walks
9 Algebraic techniques - fingerprinting
10 Fooling the adversary - examples
11 Randomized cryptographic protocols
12 Randomized proofs
13 Probabilistic method II:
14 Quantum algorithms
LITERATURE
R. Motwami, P. Raghavan: Randomized algorithms, Cambridge University Press,
1995
J. Gruska: Foundations of computing, 1997
J. Hromkoviˇc: Design and analysis of randomized algorithms, Springer, 2005
N. Alon, J. H. Spencer: The probabilistic method, Willey-Interscience, 2008
Chapter 1. INTRODUCTION
The main aim of the first chapter and lecture is:
1 to present several interesting examples of simple randomized algorithms;
2 to demonstrate advantages of randomized algorithms and methods of their analysis.
The second aim of this chapter is to introduce main complexity classes for randomized
algorithms.
Third aim is to show relations between randomized and deterministic complexity classes.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 8/62
WHY to use RANDOMIZED ALGORITHMS?
Randomized algorithms are such algorithms that make random choices (coin-tossing)
during their executions. As a consequence, their outcomes do not depend only on their
(external) inputs.
Advantages: There are several important reasons why randomized algorithms are of
increasing importance:
1 Randomized algorithms are often faster either from the worst-case asymptotic point
of view or/and from the numerical implementations point of view;
2 Randomized algorithms are often (much) simpler than deterministic ones for the
same problem;
3 Randomized algorithms are often easier to analyse and/or reason about especially
when applied in counter-intuitive settings;
4 Randomized algorithms have often more easily interpretable outputs, which is of
interests in applications where analyst’s time rather than just computation time is of
interest;
5 Randomized algorithms have been recently surprisingly successful when dealing with
huge-data matrix computation problems.
6 Randomized numerical algorithms can often be organized better to exploit modern
computer architectures.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 9/62
WHY CAN RANDOMIZED ALGORITHMS BE MORE EFFICIENT?
Two simplified explanations:
(1) A systematic search for a solution must often go through a time-consuming
computation paths corresponding to some (few) very unlikely pathological cases. A
randomized search for a solution can often avoid, with a sufficiently large
probability, such time-consuming paths.
(2) For some algorithmic problems P, for each deterministic algorithm for P there are
also bad inputs that force the algorithm to do very long computations. However, for P
there is a set of deterministic algorithms such that for any input most of these algorithms
are fast and a random choice of one of the algorithms from such a set very likely provides
fast an output.
Moreover, quantum algorithms are, in principle, randomized.
Randomized complexity classes offer also a plausible way to extend the very important
feasibility concept.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 10/62
VIEWS of RANDOMIZED ALGORITHMS:
A randomized algorithm A is an algorithm that at each new run receives, in addition to
its input i, a new stream/string r of random bits which are then used to specify
outcomes of the subsequent random choices (or coin tossing) during the execution of the
algorithm.
Streams r of random bits are assumed to be independent of the input i for the algorithm
A.
input
random bits
randomized
algorithm
i −
r −
output i,r
Important comment: Repeated runs of a randomized algorithm with fixed input data
will not, in general, produce the same results. Outcomes, A(i, r), depend not only on i,
but also on r.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 11/62
MODELS of RANDOMIZED ALGORITHMS I.
A randomized algorithm can be seen also in other ways:
As an algorithm that may, from time to time, toss a coin, or read a (next) random
bit from its special input stream of random bits, and then to proceed depending on
the outcome of the coin tossing (or chosen random bit).
As a nondeterministic-like algorithm which has a probability assigned to each
possible transition.
As a probability distribution on a set of deterministic algorithms - {Ai , pi }n
i=1.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 12/62
RANDOMIZED ALGORITHMS as PROBABILISTIC
DISTRIBUTIONS on DETERMINISTIC ALGORITHMS
randomized algorithm
1/2
1/2
1/2 1/2
as a probabilistic distribution on three deterministic algorithms
A
(B, 1/4) (C, 1/4) (D, 1/2)
B, C, D
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 13/62
MODELS of RANDOMIZED ALGORITHMS II
TH
H
H H H H
H T
TTT
T
T
0.25
0.5
0.25
0.3 0.5
0.2
0.3 0.7 0.40.6
C
C C C C
C
CC1
2
3 4 5 6
C7
8
9
Pr(C )i
C are runs of dif. determ. alg.i
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 14/62
STORY of RANDOMNESS
STORY of RANDOMNESS
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 15/62
DOES RANDOMNESS EXIST? - I
One of the fundamental questions (of science) has been, and actually still is, whether
randomness really exists or whether term randomness is used only to deal with events
the laws of which we do not fully understand. Two early views are:
The randomness is the unknown and Nature is determined in its fundamentals.
Democritos (470-404 BC)
By Democritos, the order conquered the world and this order is governed by
unambiguous laws. By Leucippus, the teacher of Democritos.
Nothing occurs at random, but everything for a reason and necessity.
By Democritus and Leucippus, the word random is used when we have an incomplete
knowledge of some phenomena. On the other side:
The randomness is objective, it is the proper nature of some events.
Epikurus (341-270 BC)
By Epikurus, there exists a true randomness that is independent of our knowledge.
Einstein also accepted the notion of randomness only in the relation to incomplete
knowledge.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 16/62
VIEWS on RANDOMNESS in 19th CENTURY
Main arguments, before 20th century, why randomness does not exist:
God-argument: There is no place for randomness in a world created by God.
Science-argument: Success of natural sciences and mechanical engineering in 19th
century led to a belief that everything could be discovered and explained
by deterministic causalities of a cause and the resulting effect.
Emotional-argument: Randomness used to be identified with uncertainty or
unpredictability or even chaos.
There are only two possibilities, either a big chaos conquers the world, or order and law.
Marcus Aurelius
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 17/62
EINSTEIN versus BOHR
God does not roll dice.
Albert Einstein, 1935, a strong opponent of randomness.
The true God does not allow anybody to prescribe what he has to do.
Famous reply by Niels Bohr - one of the fathers of quantum mechanics.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 18/62
DOES GOD PLAY DICE? - NEW VIEWS
God does play even non-local dice.
An observation, due to N. Gisin, on the basis that measurement of entangled states
produces shared randomness.
God is not malicious and made Nature to produce, so useful, (shared)
randomness.
This is what the outcomes of the theoretical informatics imply.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 19/62
RANDOMNESS in NATURE
Two big scientific discoveries of 20th century changed the view on usefulness of
randomness.
1 It has turned out that random mutations of DNA have
to be considered as a crucial instrument of evolution.
2 Quantum measurement yields, in principle, random
outcomes.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 20/62
R´ENYI’s VIEW
Randomness and order do not contradict each other;
more or less both may be true at once.
The randomness controls the world
and due to this there are order and law in the world,
what can be expressed in measures of random events
that follow the laws of probability theory.
Alfr´ed R´enyi
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 21/62
RANDOMNESS
Randomness as a mathematical topic has been studied since 17th century.
Attempts to formalize chance by mathematical laws is somehow paradoxical
because, a priory, chance (randomness) is the subject of no law.
There is no proof that perfect randomness exists in the real world.
More exactly, there is no proof that quantum mechanical phenomena of the
microworld can be exploited to provide a perfect source of randomness for the
macroworld.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 22/62
KOLMOGOROV COMPLEXITY
Kolmogorov complexity KC (x) of a binary string x with respect to a universal
computer C is the length of the shortest program for C that produces x.
The above definition is basically independent of the choice of C. Namely, it holds
that for any other universal computer C there is a constant aC,C such that for any
string x, KC (x) ≤ KC (x) + aC,C .
A string x is considered as random if KC (x) ≈ |x|, that is if x is incompressible.
Kolmogorov complexity is not computable.
It is undecidable whether a given string is random.
Until Kolmogorov complexity was introduced we had no meaningful way to talk
about a given object being random.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 23/62
EXAMPLE 1. MONOPOLIST GAME
Game Given are n active players each having w one dollar coins. They play, in rounds,
the following game until all but one players become bankrupt:
1 In each round every active player puts $1 on a table and roulette wheel is spin-ed to
determine the winner who then take all money on the table.
2 A player who looses all his money declares bankruptcy and becomes inactive.
Will the game end? If not, why? If yes, when?
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 24/62
EXAMPLE 1. MONOPOLIST GAME - again
Game Given are n active players each having w one dollar coins. They play, in rounds,
the following game until all but one players become bankrupt:
1 In each round every active player puts $1 on a table and roulette wheel is spin-ed to
determine the winner who then take all money on the table.
2 A player who looses all his money declares bankruptcy and becomes inactive.
Will the game end? It can be shown that it ends almost always in approximately (nw)2
steps.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 25/62
EXAMPLE 2 - ELECTION of a LEADER
In some cases randomization is the only way to solve the problem.
Example Let n identical processors, connected into a ring, have to choose one of them to
be a “leader”, under the assumption that each of the processors knows n.
e
e
ee
e
e
e
e e
e
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 26/62
EXAMPLE 2 - ELECTION of a LEADER - I.
Algorithm (Election of a leader - a symmetry breaking protocol)
1 Each processor sets its local variable V to n and starts to be active.
2 Each active processor chooses, randomly and independently, an integer between 1
and V and put it into V .
3 Those processors that choose 1 (if any), send one-bit message around the ring –
clockwise - with the speed of one processor per time unit.
4 After n − 1 steps each processor knows the number l of processors that chosen 1. If
l = 1, the election ends and the leader introduces himself; if l = 0, election continues
by repeating Step 2. If l > 1, the only processors remaining active will be those that
have chosen 1 in Step 2. They set V ← l and election continues with Step 2.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 27/62
CLASSICAL versus QUANTUM RANDOMIZATION
Exact solvability of the leader election problem for regular graphs with identical
node-processors is a celebrated unsolvable problem of classical distributed computing.
It can be shown that this problem cannot be solved exactly and in bounded time on
classical computers even in the case processors know number of nodes (n) and
topology of the network.
However, there is quantum algorithm that runs in O(n3
) time, its communication
complexity is O(n4
), and it can solve this problem exactly for any network topology,
provided parties are connected by quantum communication links.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 28/62
THE DINING CRYPTOGRAPHERS PROBLEM
Three cryptographers have dinner at a round table of a 5-star restaurant.
Their waiter tells them that an arrangement has been made that bill will be paid
anonymously - either by one of them, or by NSA.
They respect each others right to make an anonymous payment, but they wonder if
NSA has payed the dinner.
How should they proceed to learn whether one of them paid the bill without learning
which on e - for other two?
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 29/62
DINNING CRYPTOGRAPHERS - SOLUTION
Protocol
Each cryptographer flips a perfect coin between him and the cryptographer on his
right, so that only two of them can see the outcome.
Each cryptographer who did not pay dinner states aloud whether the two coins he see the
one he flipped and the one his right-hand neighbour flipped - fell on the same side
or not.
The cryptographer who paid the dinner states aloud the opposite what he sees.
Correctness:
Odd number of differences uttered at the table implies that that a cryptographer paid
the dinner.
Even number of differences uttered at the table implies that NSA paid the dinner.
In a case a cryptographer paid the dinner the other two cryptographers would have no
idea he did that.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 30/62
TABLE
*****
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 31/62
TECHNICAL SOLUTION
Let three coin tossing made by cryptographers be represented by bits
b1, b2, b3
In case none of them payed dinner, then what they say loudly are values
b1 ⊕ b2, b2 ⊕ b3, b3 ⊕ b1
and their parity is
(b1 ⊕ b2) ⊕ (b2 ⊕ b3) ⊕ (b3 ⊕ b1) = 0
In case one of them payed dinner, say Cryptographer 2, they say loudly:
b1 ⊕ b2, b2 ⊕ b3, b3 ⊕ b1
and
(b1 ⊕ b2) ⊕ (b2 ⊕ b3) ⊕ (b3 ⊕ b1) = 1
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 32/62
EXAMPLE: RANDOM COUNTING
Problem: Determine the number, say n, of elements of a bag X, provided you can do,
repeatedly, only the following operation: to pick up, randomly, an element of the bag X,
to look at it, and to return it back to the bag.
Algorithm:
k ← 0;
do choose randomly an element from X, mark it and return it back; set k ← k + 1
until the just chosen element has already been chosen;
n ← 2k2
π
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 33/62
EXAMPLE: ZERO POLYNOMIAL TESTING
Problem: Decide whether a given polynomial p(x1, . . . , xn), (given implicitly) with
integer coefficients, and with each product of variables being of the degree at most k, is
identically 0. Algorithm:
Compute p(x1, . . . , xn) N times, for sufficiently large N; each time with randomly chosen
integer values for x1, . . . , xn from the interval [0, 2kn].
If, at the above process at least once a value different from 0 is obtained, then p is not
identically 0.
If all N values obtained are 0, then we can consider p to be identically 0. The probability
of error is at most 2−N
.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 34/62
DESIGN of the SMALLEST ENCLOSING DISK
Task Given is a set S of n points in the plane. Find the smallest disk (circle) D(S)
containing S.
Note D(S) is determined by any three points on its edge.
Naive solution For any three points design a disk/circle passing through them complexity
of such an algorithm is O(n3
)
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 35/62
Random O(n) algorithm - Welzl
For the start let us consider all points as having the weight 1
Algorithm
1 Choose randomly (taking into considerations weights of points) a set of about 20
points S and determine, somehow, D(S ).
2 In case there are points of S that are out of D(S ) double their weights and go to
Step 1. Otherwise you are done
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 36/62
RANDOMIZED QUICKSORT
Problem: To sort a set S of n elements we can use the following algorithm.
1 Choose a median y of S.
2 Compare all elements of S with y and divide S into the set S1 of elements smaller
than y and into the set S2 of the remaining elements.
3 Sort recursively sets S1 and S2.
Analysis of the number of comparisons: T(n)
T(n) ≤ 2T(n
2
) + (c + 1)n
in case we can find y in cn steps for some constant c
Solution of the above inequality:
T(n) ≤ c n lg n
Asymptotically, the same solution is obtained if we require only that none of the sets S1,
S2 has more than 3
4
n elements. Since there are at least n
2
elements y with the last
property there is a good chance that if y is always chosen randomly, then we get a good
performance.
This way we obtain random QUICKSORT or RQUICKSORT.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 37/62
ANALYSIS of RQUICKSORT (RQS)
Let the set S to be sorted be given and let
si – be the i-th smallest element of S;
sij – be a random variable having value 1 if si and sj are being compared (during an
execution of the RQS).
Expected number of comparisons of RQS
E
n
i=1
n
j=1
sij =
n
i=1
n
j=1
E[sij ]
If pij is the probability that si and sj are being compared during an execution of the
algorithm, then E[sij ] = pij .
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 38/62
In order to estimate pij it is enough to realize that if si and sj are compared during
an execution of the RQS, then one of these two elements has to be in the subtree
headed by the other element in the comparison tree being created at that
execution. Moreover, in such a case all elements between si and sj are still to be inserted
into the tree being created. Therefore, at the moment other element (not the one in the
root of the subtree), is chosen, it is chosen randomly from at least |j − i| + 1 elements.
Hence pij ≤ 1
|i−j|+1
. Therefore we have (for Hn = n
i=1
1
i
):
n
i=1
n
j=1
pij ≤
n
i=1
n
j=i
2
j − i + 1
≤
n
i=1
n−i+1
k=1
2
k
≤
2
n
i=1
n−i+1
k=1
1
k
≤ 2nHn = Θ(n log n)
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 39/62
FALSIFIABILITY of BOOLEAN FORMULAS
The following algorithm finds, given a satisfiable Boolean formula F in 3-CNF, with very
high probability, a satisfying assignment for F.
Algorithm:
Choose randomly a truth assignment T for F;
while there is a truth assignment T that differs from T in
exactly one variable and satisfies more clauses of F than T
do choose such of these T that satisfy the most clauses and set T ← T od;
return T
A natural question: How good is this simple algorithm?
Theorem If 0 < < 1
2
, then there is a constant c such that for all but a fraction of at
most n2n
e− n2
2 of satisfiable 3-CNF Boolean formulas with n variables, the probability
that the above algorithm succeeds in discovering a truth assignment in each independent
trial from a random start is at least 1 − e− 2
n
.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 40/62
EXAMPLE: CUTS in MULTIGRAPHS - PROBLEM
Given is an undirected and loop-free multigraph G.The task is to find one of the smallest
sets C of edges (called a cut) of G such that the removal of edges from C disconnects
the multigraph G.
Basic operation is an edge contraction If e is an edge of a loop-free multigraph G, then
the multigraph G/e is obtained from G by contracting the edge e = {x, y}, that is, we
identify the vertices x and y and remove all resulting loops.
Example:
q
q
q
q
qc
  
dd
p
p
p
p
a
p p pa p p
p
p
p
p
a
p p pa p p
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 41/62
CUTS in MULTIGRAPHS - ALGORITHM
Basic idea of the algorithm given below: An edge contraction of a multigraph does not
reduce the size of the minimal cut.
Contract algorithm:
while there are more than 2 vertices in the multigraph
do edge-contraction of a randomly chosen edge od
Output the size of the minimal cut of the resulting 2 vertices multigraph.
Example:
q
q
q
q
qc
  
dd
p
p
p
p
a
p p pa p p
p
p
p
p
a
p p pa p p
In the above example, where two options are explored in the second step, we got once
the optimal result, and once a non-optimal result.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 42/62
HOW GOOD is the ABOVE ALGORITHM?
How probable is that our algorithm produces an incorrect result?
Let G be a multigraph with n vertices and k be the size of its minimal cut;
C - be a particular minimal cut of size k.
Observation: G has to have at least kn
2
edges. (Why?)
We derive a lower bound on the probability that no edge of C is ever contracted during
an execution of the algorithm.
Let Ei be the event of non-choosing an edge of C at the i-th step of the algorithm. The
probability that the edge randomly chosen in the first step is in C is at most k
nk
2
= 2
n
and
therefore Pr(E1) ≥ 1 − 2
n
.
If E1 occurs, then at the second contraction step there are at least k(n−1)
2
edges. Hence
Pr(E2|E1) ≥ 1 − 2
n−1
Similarly, in the i-th step
Pr Ei |
i−1
j=1
Ej ≥ 1 −
2
n − i + 1
=
n − i − 1
n − i + 1
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 43/62
PROOF CONTINUATION
Therefore, the probability that no edge of C is ever contracted during an execution of the
algorithm, that is that algorithm gives correct output, can be lower bounded by
Pr
n−2
i=1
Ei ≥
n−2
i=1
1 −
2
n − i + 1
=
n−2
i=1
n − i − 1
n − i + 1
=
2
n(n − 1)
= Ω(
1
n2
)
Hence, the probability of an incorrect result is ≤ 1 − 2
n(n−1)
.
Moreover, if the above algorithm is repeated n2
2
times, making each time random
decisions, then the probability that a minimal cut is not found is at most
1 −
2
n2 − n
n2
2
< 1 −
2
n2
n2
2
= 1 −
1
n2
2
n2
2
<
1
e
Running time of the best deterministic minimum cut algorithm is O(nm + n2
lg n), where
m is number of edges and n is number of vertices.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 44/62
REMINDERS
The following facts are well-known from mathematical
analysis:
(1 + x
n)n
≤ ex
;
limn→∞(1 + x
n)n
= ex
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 45/62
PRIMES RECOGNITION
The fastest known sequential deterministic algorithm to decide whether a given integer n
is prime has complexity O (lg n)14
A simple randomized Rabin-Miller’s Monte Carlo algorithm for prime recognition is based
on the following result from the number theory.
Lemma Let n ∈ N, n = 2s
d + 1, d is odd. Denote, for 1 ≤ x < n, by C(x) the condition:
xd
≡ 1 (mod n) and x2r
d
≡ −1 (mod n) for all 1 < r < s Key fact: If C(x) holds for
some 1 ≤ x < n, then n is not prime (and x is a witness for compositness of n). If n is
not prime, then C(x) holds for at least half of x between 1 and n.
In other words most of the numbers between 1 and n are witnesses for composability of
n.
Rabin-Miller algorithm
Choose randomly integers x1, . . . , xm such that 1 ≤ xj < n;
For each xj determine whether C(xj ) holds;
if C(xj ) holds for some xj ;
then n is not prime
else n is prime, with probability of error 2−m
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 46/62
RANDOMIZED COMPLEXITY CLASSES
A special way how to model random steps formally, and to study power of randomization,
it is enough to consider probabilistic algorithms as nondeterministic Turing machines
(NTM), that have in each configuration exactly two choices to make and for each input
all computations have the same length. In order to define different complexity classes for
randomized computations, one then just needs to consider different acceptance modes.
RP: A language L is in RP (Random Polynomial time) if there is a polynomial NTM
such that:
if x ∈ L, then at least half of all computations of M on x terminate in an accepting
state;
if x ∈ L, then all computations of M terminate in rejecting states. (So called Monte
Carlo acceptance or one-sided Monte Carlo acceptance).
PP: A language L is in PP (Probabilistic Polynomial time) if there is a polynomial NTM
such that: x ∈ L iff more than half of computations of M on x terminate in accepting
states. (So called acceptance by majority.)
ZPP: A language L is in ZPP (Zero error Probabilistic Polynomial time) (it is also called
Las Vegas acceptance if.) L ∈ ZPP = RP ∧ coRP.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 47/62
BPP and OTHER VIEW of COMPLEXITY CLASSES
BPP: A language is in BPP (Bounded error away from 1
2
Probabilistic Polynomial time),
if there is a polynomial NTM M such that:
If x ∈ L, then at least 3
4
computations of M on x terminate in accepting states.
If x ∈ L, then at least 3
4
of computations of M on x terminate in rejecting states.
Less formally, classes RP, PP and BPP can be defined as classes of problems for which
there is a randomized algorithm A with the following property:
RP:
x ∈ L ⇒ PR(A(x) accepts) ≥ 1
2
;
x ∈ L ⇒ PR(A(x) accepts) = 0
PP:
x ∈ L ⇒ PR(A(x) accepts) > 1
2
;
x ∈ L ⇒ PR(A(x) accepts) ≤ 1
2
.
BPP:
x ∈ L ⇒ PR(A(x) accepts) ≥ 3
4
;
x ∈ L ⇒ PR(A(x) accepts) < 1
4
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 48/62
PP class - some observations
An example of a PP problem: Given a Boolean formula φ with n variables, do at
least half of the 2n
possible assignments of variables make the formula to evaluate to
TRUE?
Just like deciding whether there exists satisfying assignment is NP-complete, so this
majority-vote variant can be shown to be PP-complete; that is, any other
PP-complete problem is efficiently reducible to it.
Problems: a PP-algorithm is free to accept with probability 1/2 + 2−n
if the answer
is yes and probability 1/2 − 2n
if the answer is no. However how can a mortal
distinguish these two cases if, for example, n = 5000?
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 49/62
INCLUSIONS between MAIN COMPLEXITY CLASSES
Theorem
P ⊆ ZPP ⊆ RP ⊆ NP ⊆ PP ⊆ PSPACE
Proof: Since relations P ⊆ ZPP ⊆ RP are obvious, we show first
RP ⊆ NP
If L ∈ RP then there is a NTM M accepting L with Monte Carlo acceptance. Hence,
L ∈ NP. Now we show:
NP ⊆ PP
Let L ∈ NP and M be a polynomial NTM for L. Design a NTM M that for f an input
w nondeterministically chooses and performs one of two steps:
1 (1) M accepts (2) M simulates M on the input w.
M can be transformed into an equivalent NTM M that always have two choices and all
its computations on w have the same length. M therefore accepts L by majority what
implies: L ∈ PP. Indeed: If w ∈ L, then exactly half of computations accept – those
corresponding to step 1.
If w ∈ L, then there is at least one computation of M that accepts w ⇒ more than half
of computations of M accept. In addition, it holds PP ⊆ PSPACE.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 50/62
COMPLEXITY CLASS BPP
Acceptance by clear majority seems to be the most important concept of the
randomized computing.
The number 3
4
used in the definition of the class BPP can be replaced by any
number larger than 1
2
. In other words, for any ε < 1
2
we can say that an
BPP-algorithm accepts (rejects) any word from (not from) the underlying language
with the probability at least 1 − ε
BPP–algorithms allow to diminish, by a repeated application, the probability of error
as much as needed.
It seems that P BPP NP and therefore the class BPP seems to be a
reasonable extension of the class P and as a class of feasible problems.
Theorem All languages in BPP have polynomial size Boolean circuits.
Definition A language L ⊆ {0, 1} has polynomial size Boolean circuits if there is a family
of Boolean circuits G = {Ci }∞
i=1 and a polynomial p such that size of Cn is bounded by
p(n), Cn has n inputs and x ∈ L iff the output of C|x| is 1 if its i-th input is xi .
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 51/62
AMPLIFICATION of PROBABILITIES
Let a PTM M have a probability of error at most ε < 1
2
. Take k copies of M and run
them for the same input and then make the majority decision. Such a majority voting will
be wrong with probability
perr ≤
S⊆{1,...,k},|S|≤k/2
(1 − ε)|S|
εk−|S|
(1)
= ((1 − ε)ε)k/2
S⊆{1,...,k},|S|≤k/2
ε
1 − ε
k/2−|S|
(2)
< ( ε(1 − ε))k
2k
= λk
, (3)
where λ = 2 ε(1 − ε) < 1, because the above sum is ≤ 2k
, since ε
1−ε
≤ 1.
In case k is big enough, the effective error probability will be as small as we wish. This
process is called amplification of probability.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 52/62
BPP and P/poly
The result from the last theorem can be stated in a nice form using the concept of
non-uniform complexity class P/poly.
For a Boolean function
f : {0, 1}∗
→ {0, 1}
and an integer n let fn be the Boolean function defined on {0, 1}n
by
fn(x1, . . . , xn) = f (x1 . . . xn)
and let c(fn) be the size of the minimal circuit for fn.
Definition A Boolean function f belongs to the class P/poly if there is a polynomial p
such that
c(fn) ≤ p(n).
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 53/62
MAIN THEOREM: BPP ⊆ P/poly
Proof. Let f (x) be a BPP-predicate(language) and M be a probabilistic TM that
determines/decides f with probability at least 1 − ε. Using repetitive runs we can
construct i a polynomial probabilistic TM M that decides f with the error probability
less than ε = 1/2n
for inputs of length n.
M uses at each run a random string r (one random bit for each step). For each input x
of length n, the fraction of strings r that lead to an incorrect answer is therefore less than
1/2n
.
The overall fraction of “bad” pairs (x, r) among all such pairs is therefore less than 1/2n
.
(If one represents the set of all pairs (x, r) as a unit square, the “bad” subset has an area
< 1/2n
.)
Therefore it has to exist an r = r∗ such that the fraction of bad pairs (x, r) is less than
1/2n
among all pairs with r = r∗. However, there are only 2n
such pairs. Hence, the only
way how the fraction of bad pairs (x, r∗) can be smaller than 1/2n
is that there are no
bad pairs at all!!
Consequently, we have to conclude that that there is a string r∗ that produces correct
answers for all x of length n,
The machine M can therefore be transformed into a polynomial-size circuit with inputs
(x, r). Then we fix the value r = r∗ and this way we obtain a polynomial size circuit with
an input x that decides/computes f (x) for all x of length n.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 54/62
HIERARCHY of COMPLEXITY CLASSES
ZPP
coRPRP
BPPNP coNP
PP
PSPACE
EXP
P
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 55/62
CLASS MA
The class BPP can be seen as a randomized version of the class P. In a similar way the
class MA (Marlin-Arthur), defined bellow, can be seen as a randomized version of the
class NP.
MA is the class of decision problems solvable by a Merlin-Arthur protocol, which goes as
follows: Merlin, who has unbounded computational resources, sends Arthur a
polynomial-size to-be-proof that the answer to the problem is ”yes”. Arthur must verify
the proof in BPP, so that if the answer to the decision problem is
”yes”, then there exists a proof which Arthur accepts with probability at least 2
3
.
”no”, then Arthur accepts any ”to-be-proof” with probability at most 1
3
.
An alternative definition requires that if the answer is ”yes”, then there exists a proof
that Arthur accepts with certainty.
It can be shown that if P = BPP, then MA=NP.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 56/62
HOW IMPORTANT is RANDOMNESS for DESIGN of
ALGORITHMS
The answer depends much on how we define when an algorithm is ”efficient”.
If constant factors are of importance, then randomization is clearly of large
importance.
If we consider O(n), O(n2
) and also O(n3
) algorithms as still efficient, but already
O(n4
) algorithms as not, then randomness is still of importance for some problems.
If ”polynomial-time computability” is used for efficiency criterion, we do not know
answer yet but we maybe able to claim that randomness is not essential.
There is a strong evidence that P = BPP.
Such assumption is based on results showing that computational hardness of some
problems can be used to generate pseudorandom sequences that look random to all
polynomial time algorithms.
Using such techniques Widgerson and Impagliazo showed that P=BPP if there is a
problem computable in an exponential time that requires circuits of exponential size.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 57/62
BERTRAND’s PROBLEM
The following problem has at least three very different (and correct) solutions,with
different outcomes. This indicates how tricky are concepts of probability and
randomness.
Problem See the next figure. Fix a circle of radius 1. Draw in the circle equilateral
triangle and denote l its length. Choose randomly a chord d (and denote m its length) of
the circle. What is the probability that m ≥ l?
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 58/62
SOLUTION # 1
See the the figure below: Consider shaded internally tangented circle in the inscribed
equilateral triangle (it has radius 1/2).
If the centre of the chord D lies inside the shaded disc, then m > l; otherwise m ≤ l.
Therefore the probability that m > l is
area of shaded disc
area of unit disc
=
π/4
π
=
1
4
Indeed, second figure above shows that the shaded disc has radius 1/2.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 59/62
SOLUTION # 2
See the next figure. Without loss of generality we can assume that randomly chosen
chord is horizontal.
If the height, from the base of the circle, of the chord d is less ≤ 1/2, then m ≤ l;
otherwise m > l.
Therefore, the probability that m > l is 1/2.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 60/62
Solution # 3 - I.
See the next figure. Without loss of generality we can assume that one vertex of our
randomly chosen chord occurs at the lower left vertex A of the inscribed triangle.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 61/62
Solution # 3 - II.
Consider now the angle θ that the chord subtends with the tangent line to the circle at
the point A.
One can show that if 0 ≤ θ ≤ 60 or 120 ≤ θ ≤ 180 degrees, than m ≤ l; otherwise m > l.
Therefore, the probability that randomly chosen chord has length exceeding l is 60
180
= 1
3
.
prof. Jozef Gruska IV054 1. Basic concepts and examples of randomized algorithms 62/62