Randomised Algorithms

The Probabilistic Method

The Probabilistic Method

▶ A non-constructive way of proving existence of objects with

certain properties.
▶ To prove existence, we show that the probability an object has
desired property is positive.
The Expectation Argument

▶ Uses expectation of some random variable to conclude about

existence of objects.
The Expectation Argument

▶ Uses expectation of some random variable to conclude about

existence of objects.
▶ A random variable must take a value atleast as large as its
expectation, and a value atmost as large as its expectation.
The Expectation Argument

▶ Uses expectation of some random variable to conclude about

existence of objects.
▶ A random variable must take a value atleast as large as its
expectation, and a value atmost as large as its expectation.

Lemma
Suppose we have a random variable X with E [X ] = µ. Then,
Pr (X ≥ µ) > 0 and Pr (X ≤ µ) > 0
Application: Maximum Satisfiablilty

▶ We are given a boolean formula in conjuctive normal form

(CNF).
▶ We have to find an assignment to variables such that
maximum number of clauses are satisfied.
▶ Example of SAT formula:

(x1 ∨ x 2 ) ∧ (x 1 ∨ x3 ) ∧ (x2 ∨ x3 )
Application: Maximum Satisfiablilty

Consider a formula with m clauses and atleast k literals in each

clause.
Application: Maximum Satisfiablilty

Consider a formula with m clauses and atleast k literals in each

clause.
We show that there is an assignment to the variables that satisfies
atleast m(1 − 2−k ) clauses.
Application: Maximum Satisfiablilty

Consider a formula with m clauses and atleast k literals in each

clause.
We show that there is an assignment to the variables that satisfies
atleast m(1 − 2−k ) clauses.
Assign values to all variables randomly.
Application: Maximum Satisfiablilty

Consider a formula with m clauses and atleast k literals in each

clause.
We show that there is an assignment to the variables that satisfies
atleast m(1 − 2−k ) clauses.
Assign values to all variables randomly. Then, probability that
some clause is satisfied is atleast (1 − 2−k ).
Application: Maximum Satisfiablilty

Consider a formula with m clauses and atleast k literals in each

clause.
We show that there is an assignment to the variables that satisfies
atleast m(1 − 2−k ) clauses.
Assign values to all variables randomly. Then, probability that
some clause is satisfied is atleast (1 − 2−k ). Let X denote the
number of satisfied clauses.

E [X ] ≥ m(1 − 2−k )
Application: Maximum Satisfiability

Can we find such an assignment efficiently?

Application: Maximum Satisfiability

Can we find such an assignment efficiently?

We could try to randomly assign all variables and check the
number of satisfied clauses. This gives us a Las Vegas algorithm.
Application: Maximum Satisfiability

Can we find such an assignment efficiently?

Or, we could go through the variables sequentially, and assign

either true or false to each variable to try to maximise the number
of satisfied clauses.
Application: Maximum Satisfiability

Suppose x1 , x2 , . . . xn are the variables. Let X be the number of

satisfied clauses. Let E [X |x1 , . . . xi ] be the conditional expectation
of X given that variables x1 . . . xi have been assigned values and
other variables are assigned randomly. Then we show inductively
the value to assign to xi+1 such that

E [X |x1 . . . xi+1 ] ≥ E [X |x1 . . . xi ]

Application: Maximum Satisfiability

Base Case
Application: Maximum Satisfiability

Base Case
We have,
1 1
E [X ] = E [X |x1 = 0] + E [X |x1 = 1]
2 2
Then, for atleast one value of x1 , E [X |x1 ] is as large as than E [X ].
So, we chose that value for x1

Induction
Application: Maximum Satisfiability

Base Case
We have,
1 1
E [X ] = E [X |x1 = 0] + E [X |x1 = 1]
2 2
Then, for atleast one value of x1 , E [X |x1 ] is as large as than E [X ].
So, we chose that value for x1

Induction
Let the first k variables be assigned some value. Then,
1 1
E [X |x1 . . . xk ] = E [X |x1 . . . xk , xk+1 = 0]+ E [X |x1 . . . xk , xk+1 = 1]
2 2
Again, for some value of xk+1 , E [X |x1 , . . . xk+1 ] is as large as
E [X |x1 , . . . xk ].
Application: Maximum Satisfiability

Base Case
We have,
1 1
E [X ] = E [X |x1 = 0] + E [X |x1 = 1]
2 2
Then, for atleast one value of x1 , E [X |x1 ] is as large as than E [X ].
So, we chose that value for x1

Induction
Let the first k variables be assigned some value. Then,
1 1
E [X |x1 . . . xk ] = E [X |x1 . . . xk , xk+1 = 0]+ E [X |x1 . . . xk , xk+1 = 1]
2 2
Again, for some value of xk+1 , E [X |x1 , . . . xk+1 ] is as large as
E [X |x1 , . . . xk ]. Thus, by induction, E [X |x1 , . . . xk+1 ] ≥ E [X ].
Application: Maximum Satisfiability

How do we compute the conditional expectations?

Application: Maximum Satisfiability

How do we compute the conditional expectations?

We just need to compare the expectations and choose the value
which results in a greater expectation.
Application: Maximum Satisfiability

How do we compute the conditional expectations?

We just need to compare the expectations and choose the value
which results in a greater expectation.
While processing variable xk , we ignore
Application: Maximum Satisfiability

How do we compute the conditional expectations?

We just need to compare the expectations and choose the value
which results in a greater expectation.
While processing variable xk , we ignore
▶ clauses that are already satisfied.
Application: Maximum Satisfiability

How do we compute the conditional expectations?

We just need to compare the expectations and choose the value
which results in a greater expectation.
While processing variable xk , we ignore
▶ clauses that are already satisfied.
▶ clauses that do not contain xk or its negation
Application: Maximum Satisfiability

Let C be the set of remaining clauses. For some c ∈ C , Let vc be

the numbers of variables in the clause yet to be set (excluding xk ).
Application: Maximum Satisfiability

Let C be the set of remaining clauses. For some c ∈ C , Let vc be

the numbers of variables in the clause yet to be set (excluding xk ).
Let C = C1 ∪ C2 where clauses in C1 contain xk and those in C2
contain its negation.
Application: Maximum Satisfiability

Let C be the set of remaining clauses. For some c ∈ C , Let vc be

the numbers of variables in the clause yet to be set (excluding xk ).
Let C = C1 ∪ C2 where clauses in C1 contain xk and those in C2
contain its negation.
Then, we comapre values
X X
V1 = C1 + (1 − 2−vc ), V2 = C2 + (1 − 2−vc )
c∈C2 c∈C1
Application: Maximum Satisfiability

Let C be the set of remaining clauses. For some c ∈ C , Let vc be

the numbers of variables in the clause yet to be set (excluding xk ).
Let C = C1 ∪ C2 where clauses in C1 contain xk and those in C2
contain its negation.
Then, we comapre values
X X
V1 = C1 + (1 − 2−vc ), V2 = C2 + (1 − 2−vc )
c∈C2 c∈C1

If V1 is greater, we assign xk = 1, otherwise, we assign xk = 0.

Application: Dominating Sets
Consider a r -uniform hypergraph H = (V , E ).
Application: Dominating Sets
Consider a r -uniform hypergraph H = (V , E ).
A Dominating Set is a set S ⊂ V such that for every e ∈ E ,
e ∩ S ̸= ϕ.
Application: Dominating Sets
Consider a r -uniform hypergraph H = (V , E ).
A Dominating Set is a set S ⊂ V such that for every e ∈ E ,
e ∩ S ̸= ϕ.
We show that there is a dominating set of size atmost
(m + n ln r )/r .
Application: Dominating Sets
Consider a r -uniform hypergraph H = (V , E ).
A Dominating Set is a set S ⊂ V such that for every e ∈ E ,
e ∩ S ̸= ϕ.
We show that there is a dominating set of size atmost
(m + n ln r )/r .
▶ First, select each vertex independently with probability p. Call
this set S.
Application: Dominating Sets
Consider a r -uniform hypergraph H = (V , E ).
A Dominating Set is a set S ⊂ V such that for every e ∈ E ,
e ∩ S ̸= ϕ.
We show that there is a dominating set of size atmost
(m + n ln r )/r .
▶ First, select each vertex independently with probability p. Call
this set S.
▶ Then, for each edge not covered by S, add atmost one vertex
to S. Now, S is a dominating set.
Application: Dominating Sets
Consider a r -uniform hypergraph H = (V , E ).
A Dominating Set is a set S ⊂ V such that for every e ∈ E ,
e ∩ S ̸= ϕ.
We show that there is a dominating set of size atmost
(m + n ln r )/r .
▶ First, select each vertex independently with probability p. Call
this set S.
▶ Then, for each edge not covered by S, add atmost one vertex
to S. Now, S is a dominating set.
Let X = |S| after first step, and Y is the number of vertices added
in second step. Then,

E [X + Y ] = np + m(1 − p)r
Application: Dominating Sets
Consider a r -uniform hypergraph H = (V , E ).
A Dominating Set is a set S ⊂ V such that for every e ∈ E ,
e ∩ S ̸= ϕ.
We show that there is a dominating set of size atmost
(m + n ln r )/r .
▶ First, select each vertex independently with probability p. Call
this set S.
▶ Then, for each edge not covered by S, add atmost one vertex
to S. Now, S is a dominating set.
Let X = |S| after first step, and Y is the number of vertices added
in second step. Then,

E [X + Y ] = np + m(1 − p)r
ln r
For p = r ,
E [X + Y ] ≤ (m + n ln r )/r
Lovasz Local Lemma

▶ Another useful way to prove existence of objects with some

properties.
Lovasz Local Lemma

▶ Another useful way to prove existence of objects with some

properties.
▶ Suppose we can write our event of interest, E as
\
E= Ei
i∈[n]
Lovasz Local Lemma

▶ Another useful way to prove existence of objects with some

properties.
▶ Suppose we can write our event of interest, E as
\
E= Ei
i∈[n]

▶ If E1 . . . En are independent, and Pr (Ei ) < 1, then

Y
Pr (E ) = (1 − Pr (Ei )) > 0
i∈[n]
Lovasz Local Lemma

▶ Another useful way to prove existence of objects with some

properties.
▶ Suppose we can write our event of interest, E as
\
E= Ei
i∈[n]

▶ If E1 . . . En are independent, and Pr (Ei ) < 1, then

Y
Pr (E ) = (1 − Pr (Ei )) > 0
i∈[n]

▶ If these events are not independent, Lovasz Local Lemma

helps.
Lovasz Local Lemma

Consider the dependence graph of events E1 . . . En .

Lovasz Local Lemma

Consider the dependence graph of events E1 . . . En .

Theorem
Let E1 , E2 . . . En be a set of events and assume the following hold:
1. ∀i, Pr (Ei ) ≤ p
2. the degree of dependence graph of E1 , E2 , . . . En is bounded
by d
3. 4dp ≤ 1
Then,  
\
Pr  Ei  > 0
i∈[n]
Lovasz Local Lemma

Consider the k-satisfiability problem: Given a SAT formula with m

clauses, and each clause containing exactly k literals, is there a
truth assignment that satisfies all clauses?
Lovasz Local Lemma

Consider the k-satisfiability problem: Given a SAT formula with m

clauses, and each clause containing exactly k literals, is there a
truth assignment that satisfies all clauses?
If a variable does not appear in too many clauses, there is!
Lovasz Local Lemma

Consider a random assignment to all variables. Let event Ei denote

the event that clause Ci is not satisfied. Then,

Pr (Ei ) = 2−k = p
Lovasz Local Lemma

Consider a random assignment to all variables. Let event Ei denote

the event that clause Ci is not satisfied. Then,

Pr (Ei ) = 2−k = p

We want that none of the events Ei happen.

Lovasz Local Lemma

Consider a random assignment to all variables. Let event Ei denote

the event that clause Ci is not satisfied. Then,

Pr (Ei ) = 2−k = p

We want that none of the events Ei happen.

Two events Ei and Ej are dependent iff clauses Ci and Cj share
some variable.
Lovasz Local Lemma

Consider a random assignment to all variables. Let event Ei denote

the event that clause Ci is not satisfied. Then,

Pr (Ei ) = 2−k = p

We want that none of the events Ei happen.

Two events Ei and Ej are dependent iff clauses Ci and Cj share
some variable.
If each variable is present in atmost T clauses, then d ≤ kT
Lovasz Local Lemma

Consider a random assignment to all variables. Let event Ei denote

the event that clause Ci is not satisfied. Then,

Pr (Ei ) = 2−k = p

We want that none of the events Ei happen.

Two events Ei and Ej are dependent iff clauses Ci and Cj share
some variable.
If each variable is present in atmost T clauses, then d ≤ kT
To meet the conditions of LLL,

4dp ≤ 4kT · 2−k ≤ 1

Thus, if T ≤ 2k /4k, the SAT formula has a satisfying truth

assignment.