Week 9 (Randomized Algorithms, Streaming Algorithms)

Question 1

What is the equation for independent probability?

Answer 1

Pr(E n F) = Pr(E) . Pr(F)

Question 2

What is the equation for conditional probability?

Answer 2

Pr(E|F) = Pr(E n F) / Pr(F)

Question 3

When are two random variables X and Y independent?

Answer 3

If Pr((X=x) n (Y=y)) = Pr(X=x) . Pr(Y=y)

Question 4

What is the expectation of a discrete random variable?

Answer 4

The expectation is given by E[X]::= Σ i ∈ Range(X) i . Pr(X=i)

Question 5

What is the linearity of expecation?

Answer 5

If X1,…,Xk are discrete random variables with finite expectations, then E[Σ i=1 k Xi] = Σ i=1 k E[Xi]

Question 6

What is the proof for the linearity of expectation?

Answer 6

E[X + Y ]
= Σ i→range(X) Σ j→range(Y) (i + j) · Pr ((X = i) n (Y = j))
= Σ i→range(X) Σ j→range(Y) i · Pr((X = i) n (Y = j)) + Σ i→range(X) Σ j→range(Y) j · Pr((X = i) n (Y = j))
= Σ i→range(X) i . Pr(X=i) + Σ j→range(Y) j . Pr(Y = j)
= E[X] + E[Y]

Question 7

What is the conditional expectation?

Answer 7

Let X,Y be two discrete random variables. We define the conditional expectation E[X|Y = y]:=Σ x ∈ range(X) x . Pr(X = x | Y = y)

Question 8

What is the unconditional expectation?

Answer 8

Let X,Y be two discrete random variables, the unconditional expectation E[X]:=Σ y ∈ range(Y) Pr[Y=y] . E(X|Y = y)

Question 9

What is the proof for the unconditional expectation?

Answer 9

Σ y→range(Y) Pr[Y = y] · E(X|Y = y)
= Σ y→range(Y) Pr[Y = y] · (Σ x→range(X) x · Pr(X = x|Y = y))
= Σ x→range(X) Σ y→range(Y) x · Pr(X = x|Y = y) · Pr[Y = y]
= Σ x→range(X) Σ y→range(Y) x · Pr(X = x n Y = y)
= Σ x→range(X) x Σ y→range(Y) Pr(X = x n Y = y)
= Σ x→range(X) x · Pr[X = x]
= E[X]

Question 10

What is the (1/2)-approximation Max Cut?

(Randomised algorithm)

Answer 10

Consider a random partition for each vertex v:
- put v in X with probability 1/2
- put v in V\X with probability 1/2

Probability an edge e = a-b is in the cut is 1/2

For each edge e, let Ze be the random variable which is 1 if e is in the cut and 0 otherwise. For each edge e, we have
E[Ze] = 1 . Pr(inCut) + 0.Pr(not) = 1/2

Let Z = Σ Ze, by linear expectation we have E[Z] = E[Σ Ze] = Σ E[Ze] = |E|/2. Hence, the number of edges in the cut for a random partition is |E|/2. We therefore have at least one partition of V which has >= |E|/2 edges in the cut.

Consider any vertex v ∈ V, which can be in X or V\X
E[Z] = Pr(v ∈ X) . E[Z| v ∈ X] + Pr(v ∉ X) . E[Z| v ∉ X]
E[Z] = 1/2 . (E[Z| v ∈ X] + E[Z| v ∉ X]) = |E|/2

This implies at least one of E[Z| v ∈ X] and E[Z| v ∉ X] is >= |E|/2. We pick this choice for v, if they are the same choose either.

Consider an edge (a-b):
- If we fix both endpoints: Pr = 1 or 0
- If we fix one endpoint: Pr = 1/2
- If we fix no endpoints: Pr = 1/4 + 1/4 = 1/2

This takes O(m) time to compute both values for each vertex in V.

Total running time: O(m.n) = O(n^3)

Question 11

What is the (3/4)-approximation for Max-2-SAT?

(Randomised algorithm)

Answer 11

Consider a random assignment, set each variable to be True with a probability 1/2. Assuming we have no (x v x) or (x v x̄) clauses, the probability of a clause (x v y) is satisfied in 3/4. The expected number of clauses satisfied by a random assignment is 3/4.M

E[satisfied clauses] = Σ (Prob A) . (clauses satisfied by A)

Consider a variable x1, which is T or F:
E[C] = Pr(x1=T) . E[c|x1=T] + Pr(x1=F) . E[c|x1=F]
E[C] = 1/2. (E[c|x1=T] + E[c|x1=F]) = 3M / 4

This implies at least one of E[c|x1=T] and E[c|x1=F] is >= 3M/4. Pick this choice for x1 for each variable N to decided if its T or F.

For any clause (x v y):
- Fixed both x and y -> Pr = 1 or 0
- Fixed one x or y -> Pr = 1/2
- Fix neither x nor y -> Pr = 3/4
This can be checked in O(M) time

Total running time = O(M.N) = O(n^3)