CSCE 411 Lecture 22

Lecture Slides

« previous | Wednesday, October 17, 2012 | next »

Randomized Algorithms

Algorithm maxes random choices during its execution.

• Steps taken might differ between executions, even if input remains the same.
• can be simple and easy to implement
• can be very efficient implementations

Running time is now a random variable that must be determined with probability theory

Motivation

Company has several datacenters, and company wants to verify that copies of the databases are still consistent. Transmission of data is not feasible, so how can we test whether the content is the same?

Suppose we have implemented an extremely fast algorithm to multiply very large matrices ($n=100,000$). How do we check that the algorithm is correct.

In the RSA key exchange, we need to form the product of two very large primes (each having 1000 digits or more). How can we efficiently check whether a number is prime?

Basic Probability Theory

Sample spaces

possible outcomes of an experiment

represented by symbol $\mathrm{\Omega }$

e.g. for coin flip $\mathrm{\Omega }=\{\text{heads},\text{tails}\}$

σ-Algebra

represented by symbol $F$

A collection of subsets of a sample space $\mathrm{\Omega }$ such that

• the empty set is contained in $F$
• if $E\in F$, then its complement $E^C=\mathrm{\Omega }E\in F$
• A countable union of sets in $F$ is contained in $F$

Example:

• $\mathrm{\Omega }=\{1,2,3,4,5,6\}$
• $D=\{1,2\}$
• $E=\{3,4,5,6\}$
• the smallest $F$ containing $D$ and $E$ is $\{\mathrm{\varnothing },D,E,\mathrm{\Omega }\}$.
• The empty set is called the "impossible" event

Probability Measure

Let $F$ be a σ-algebra over a sample space $\mathrm{\Omega }$. A probability measure on $F$ is a function $Pr:F\to [0,1]$ such that:

• The centain event satisfies $Pr(\mathrm{\Omega })=1$
• $Pr\left(\bigcup _{i=1}^{\mathrm{\infty }}{E}_i\right)=\sum _{i=1}^{\mathrm{\infty }}Pr(E_i)$

Properties

• Let $D\subseteq E$ be events. Then $Pr[D]\le Pr[E]$
• Let $F$ and $G$ be any events, then $Pr[F\cup G]=Pr[F]+Pr[G]-Pr[F\cap G]$.

Uniform Probability Distribution

Probability of any singleton event $E=\{s\}$ happening is $Pr[E]=\frac{1}{|\mathrm{\Omega }|}$

Continuous Probability Distribution

Continuous uniform distribution over interval $[a,b]$ associates to each subinterval $[c,d]$ of $[a,b]$

σ-algebra breaks down since one cannot choose $F={𝒫}(\mathrm{\Omega })$. Use Borel measure instead:

$Pr[[c,d]]=\frac{d-c}{b-a}$

Union Bound

Let $I\subset \mathbb{\mathbb{N}}$. Let $E_i$ with $i\in I$ be a set of events. These events do not need to be disjoint:

$Pr\left[\bigcup _{i\in I}{E}_i\right]\le \sum _{i\in I}Pr[E_i]$

This bound is useful because it is easy to compute

Conditional Probabilities

Let $D$ and $E$ be events such that $Pr[E]>0$. The conditional probability $Pr[D|E]$ is defined as

$\begin{array}{rlrl}Pr[D|E]& =\frac{Pr[D\cap E]}{Pr[E]}& Pr[D\cap E]& =Pr[D|E]Pr[E]\end{array}$

Interpret as the probability that $D$ occurs, assuming that event $E$ occurs.

Independent Events

Two events are called independent iff

$P[D\cap E]=P[D]P[E]$

If $D$ and $E$ are independent, then $Pr[D|E]=Pr[D]$

Verifying Polynomial Identities

Suppose we want to check whether two polynomials in $x$ with integer coefficients are the same.

For example, is $(x+1)(x-2)(x+3)(x-4)(x+5)(x-6)$ the same as $x^6-7x^3+25$?

Doing this the old-fashioned expansion way is slow ($\mathrm{\Theta }(d^2)$)

Randomized Algorithm

def verify_polynomial_identity f, g
  d = [f.degree, g.degree].max
  r = (1..100*d).to_a.sample
  f(r) == g(r)
end

It's Fast ($O(d)$)! (but it can be wrong)

We can reduce the probability that the algorithm will be wrong by repeating it several times. (how many? next time...)