Randomized algorithms

Randomized algorithms

Inge Li Gørtz

• Today

• What are randomized algorithms?

• Properties of randomized algorithms

• Two examples:

• Median/Select.

• Quick-sort

Randomized algorithms

Randomized Algorithms

• So far we dealt with deterministic algorithms:

• Giving the same input to the algorithm repeatedly results in:

• The same running time.

• The same output.

• Randomized algorithm:

• Can make random choices (using a random number generator)

Randomized Algorithms

• A randomized algorithm has access to a random number generator rand(a, b), where a, b are integers, a < b.

• rand(a, b) returns a number x ∈ {a, (a + 1), . . . , (b − 1), b}.

• Each of the b − a + 1 numbers is equally likely.

• Calling rand(a, b) again results in a new, possibly different number.  

• rand(a, b) “has no memory”. The current number does not depend on the results of previous calls.

• Statistically speaking: rand(a, b) generates numbers independently according to uniform distribution.

Random number generator

• The algorithm can make random decisions using rand

Randomized algorithms

Running

while (rand(0,1) = 0) do print(“running”);

end while

print(“stopped”);

Julefrokost

while (rand(1,4) = rand(1,4)) do have another Christmas beer;

end while go home;

• A randomized algorithm might never stop.

• Example: Find the position of 7 in a three-element array containing the numbers 4, 3 and 7.

Properties of randomized algorithms

Find7(A[1…3]) goon := true;

while (goon) do i := rand(1,3);

if (A[i] = 7) then

print(Bingo: 7 found at position i);

goon := false;

end if end while

• A randomized algorithm might find the wrong solution.

• Example: Find the position of the minimum element in a three-element array.

• If A = [5,6,4] and i = 2 and j = 1 then the algorithm will wrongly return 5.

Properties of randomized algorithms

MinOfThree(A[1…3]) i := rand(1,3);

j := rand(1,3);

return(min(A[i],A[j]);

• Both examples are not so bad as they look.

• It is highly unlikely that Find7 runs a long time.

• It is more likely that MinOfThree returns a correct result than a wrong one.

Properties of randomized algorithms

• An event is something that can happen.

• An atomic event is not composed of others.

• Each atomic event x has an associated probability P[x] ∈ [0,1].

• The sum of the probabilities of all atomic events is 1.

• We consider only finite or countably infinite sets of atomic events. 


Events

X

x is atomic event

P [x] = 1

• A random variable is an entity that can assume different values.

• The values are selected “randomly”; i.e., the process is governed by a probability distribution.

• Examples:

• The number shown by a die.

• The distance of two coins dropped on the floor.

• The running time of a randomized algorithm. 


Random variables

• Let X be a random variable with values in {x1,…xn}, where xi are numbers.

• Let pi = P[X = xi] be the probability that X assumes value xi.

• The expected value (expectation) of X is defined as

• The expectation is the theoretical average.

Expected values

E [X ] =

X

i=1

x

· p

• Let X be the random variable “number shown by the die”.

• Atomic events: {1, 2, 3, 4, 5, 6}

• Probabilities: P[1] = ··· = P[6] = 1/6

• Composed event: Even = {2, 4, 6}

• Composed event: ge4 = {4, 5, 6}

• Expectation: E[X] = (1+2+3+4+5+6)/6 = 3.5


Example: a fair die

• Let X be the random variable “number shown by the die”.

• Atomic events: 1, 2, 3, 4, 5, 6

• Probabilities: 0.1, 0.1, 0.1, 0.3, 0.2, 0.2

• Expectation

E[X] = 1 · 0.1 + 2 · 0.1 + 3 · 0.1 + 4 · 0.3 + 5 · 0.2 + 6 · 0.2 = 4.0 


Example: a loaded die

• If we repeatedly perform independent trials of an experiment, each of which succeeds with probability p > 0, then the expected number of trails we need to perform until the first succes is 1/p.

• Linearity of expectation: For two random variables X and Y we have E[X+Y] = E[X] + E[Y].

Expectation

• Let A and B be events.

• If A and B are independent then

• P[A∧B] = P[A] · P[B]

• If A and B are disjoint then

• P[A∨B] = P[A] + P[B]

Rules for Probabilities

• A die is tossed twice.

• Let the random variable X1 be the result of first throw.

• Let the random variable X2 be the result of second throw.

• Events: A = (X1 = 2) and B = (X2 = 5)

• P[A] = 1/6 and P[B] = 1/6

• P[A∧B] = 1/36 = 1/6·1/6 = P[A] · P[B]

Independence example

• Event A = Even = {2, 4, 6}: P[A] = 1/2

• Event B = ge4 = {4, 5, 6}: P[B] = 1/2

• A ∧ B = {4, 6}

• P[A∧B] = 1/3 ≠ 1/4 = P[A] · P[B]

Non-independent example

• Running time: O(1).

• What is the chance that the answer of MinOfThree is correct?

• 9 possible pairs all with probability 1/9:

• (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)

• Assume wlog that A[1] is the minimum:

• 5 of the 9 pairs contain the index 1 and give the correct minimum.

• P[correct] = 5/9 > 1/2.

Analysis of MinOfThree

MinOfThree(A[1…3]) i := rand(1,3);

j := rand(1,3);

return(min(A[i],A[j]);

• Running MinOfThree once gives the correct answer with probaility 5/9 and the incorrect one with probability 4/9.

• Idea: Run MinOfThree many times and pick the smallest value returned.

• The probability that MinOfThree fails every time in k runs is:

• To be 99% sure to find the minimum, choose k such that

Analysis of MinOfThree

MinOfThree(A[1…3]) i := rand(1,3);

j := rand(1,3);

return(min(A[i],A[j]);

• Running time is variable. What is the expected running time?

• Assume wlog that A[1] = 7.

• If rand(1, 3) = 1 then the while-loop is terminated.

• P[rand(1,3) = 1] = 1/3

• If rand(1, 3) ≠ 1 then the while-loop is not terminated.

• P[rand(1,3) ≠ 1] = 2/3

• The while-loop is terminated after one iteration with probability P[rand(1,3) = 1] = 1/3.

Analysis of Find7

Find7(A[1…3]) goon := true;

while (goon) do i := rand(1,3);

if (A[i] = 7) then

print(Bingo: 7 found at position i);

goon := false;

end if end while

• The while-loop stops after exactly two iterations if

• rand(1, 3) ≠ 1 in the first iteration.

• rand(1, 3) = 1 in the second iteration.

• This happens with probability 2/3 and 1/3, resp.

• The probability for both to happen is - by independence -

Analysis of Find7

Find7(A[1…3]) goon := true;

while (goon) do i := rand(1,3);

if (A[i] = 7) then

print(Bingo: 7 found at position i);

goon := false;

end if end while

• The while-loop stops after exactly three iterations if

• rand(1, 3) ≠ 1 in the first two iterations.

• rand(1, 3) = 1 in the third iteration.

• This happens with probability 2/3, 2/3 and 1/3, resp.

• The probability for all three to happen is - by independence -

• The while-loop stops after exactly k iterations if

• rand(1, 3) ≠ 1 in the first k-1 iterations.

• rand(1, 3) = 1 in the kth iteration.

• This happens with probability 2/3, 2/3 and 1/3, resp.

• The probability for all three to happen is - by independence -

Analysis of Find7

• We have

• The expected running time of Find7 is

• Idea: Stop Las Vegas algorithm if it runs “much longer” than the expected time and restart it.

Expected running time

• We have seen two kinds of algorithms:

• Monte Carlo algorithms: stop after a fixed (polynomial) time and give the correct answer with probability greater 50%. 


• Las Vegas algorithms: have variable running time but always give the correct answer.

Types of randomized algorithms

Median/Select

• Given n numbers S = {a1, a2, …, an}.

• Median: number that is in the middle position if in sorted order.

• Select(S,k): Return the kth smallest number in S.

• Min(S) = Select(S,1), Max(S)= Select(S,n), Median = Select(S,n/2).

• Assume the numbers are distinct.

Select

Select(S, k) {

Choose a pivot s ∈ S uniformly at random.

For each element e in S if e < s put e in S’

if e > s put e in S’’

if |S’| = k-1 then return s

if |S’| ≥ k then call Select(S’, k)

if |S’| < k then call Select(S’’, k - |S’| - 1) }

• Worst case running time:

• If there is at least an fraction of elements both larger and smaller than s:

• Limit number of bad pivots.

• Intuition: A fairly large fraction of elements are “well-centered” => random pivot likely to be good.

Select

Select(S, k) {

Choose a pivot s ∈ S uniformly at random.

For each element e in S if e < s put e in S’

if e > s put e in S’’

if |S’| = k-1 then return s

if |S’| ≥ k then call Select(S’, k)

if |S’| < k then call Select(S’’, k - |S’| - 1) }

T(n) = cn + c(n 1) + c(n 2) + · · · = ⇥(n²).

"

T(n) = cn + (1 ")cn + (1 ")²cn + · · ·

= 1 + (1 ") + (1 ")² + · · · cn

 cn/".

• Phase j: Size of set at most and at least .

• Element is central if at least a quarter of the elements in the current call are smaller and at least a quarter are larger.

• At least half the elements are central.

• Pivot central => size of set shrinks with by at least a factor 3/4 => current phase ends.

• Pr[s is central] = 1/2.

• Expected number of iterations before a central pivot is found = 2 =>

expected number of iterations in phase j at most 2.

• X: random variable equal to number of steps taken by algorithm.

• Xj: expected number of steps in phase j.

• X = X1+ X2 + .…

• Number of steps in one iteration in phase j is at most .

• E[Xj] = .

• Expected running time:

Select

n(3/4)^{j n(3/4)j+1}

E[X] = X

j

E[X_j]  X

j

2cn

✓3 4

◆j

= 2cnX

j

✓3 4

◆j

 8cn.

2cn(3/4)^j

cn(3/4)^j

Quicksort

• Given n numbers S = {a1, a2, …, an} return the sorted list.

• Assume the numbers are distinct.

Quicksort

Quicksort(A,p,r) {

if |S| ≤ 1 return S

else

Choose a pivot s ∈ S uniformly at random.

For each element e in S if e < s put e in S’

if e > s put e in S’’

L = Quicksort(S’) R = Quicksort(S’’)

Return the sorted list L◦s◦R.

}

• Worst case Quicksort requires Ω(n²) comparisons: if pivot is the smallest element in the list in each recursive call.

• If pivot aways is the median then T(n) = O(n log n).

• for i < j: random variable

• X total number of comparisons:

• Expected number of comparisons:

Quicksort: Analysis

X_ij =

(1 if a_i and a_j compared by algorithm 0 otherwise

X =

nX1

i=1

Xn

j=i+1

X_ij

E[X] = E[

nX1

i=1

Xn

j=i+1

X_ij] =

nX1

i=1

Xn

j=i+1

E[X_ij]

• Expected number of comparisons:

• Since Xij only takes values 0 and 1:

• ai and aj compared iff ai or aj is the first pivot chosen from Zij = {ai,…,aj}.

• Pivot chosen independently uniformly at random => all elements from Zij equally likely to be chosen as first pivot from this set.

• We have

• Thus

Quicksort: Analysis

E[X] = E[

nX1

i=1

Xn

j=i+1

X_ij] =

nX1

i=1

Xn

j=i+1

E[X_ij] E[X_ij] = Pr[X_ij = 1]

Pr[Xij = 1] = 2/(j i + 1)

E[X] =

nX1

i=1

Xn

j=i+1

E[X_ij] =

nX1

i=1

Xn

j=i+1

Pr[X_ij] =

nX1

i=1

Xn

j=i+1

2 j i + 1

<

nX1

i=1

Xn

k=1

2

k =

nX1

i=1

O(logn) = O(nlogn)

=

nX1

i=1

n i+1X

k=2

2 k

• Prize for best three teams.

• Can count as a mandatory assignment.

Programming Competition