贴下简单介绍随机算法的PPT提纲。

**Introduction to Randomized Algorithms**

Xu Weidong

2011/2/13

**Outline**

Definition

Las Vegas and Monte Carlo

Example: Universal Hashing

Example: Pattern Matching

Example: Randomized Primality Test

Game Theory Viewpoint

Randomized Rounding

Further Reading

**Definition**

Algorithm which is allowed access to a source of independent, unbiased, random bits.

Benefit:

Fast

Simple

**Las Vegas and Monte Carlo**

Las Vegas Algorithm

Always give correct answer, but running time is random.

Monte Carlo Algorithm

Sometime give incorrect answer, but the probability of an incorrect answer is bounded.

Typically, it has one-sided error, and probability of incorrect is less than ½.

**Universal Hashing**

A family of hash functions: for any input, a large fraction of the hash functions are near-perfect.

Algorithm

(*ax* + *b*) mod *p*

*p* is a large prime

*a*, *b* chosen randomly from 0 ~ *p* – 1, *a* ≠ 0

Fast implementation for intergers

(unsigned) (a*x) >> (w-M)

Intention: *Foil an adversary*

Natural, or artificial

**Pattern Matching**

Rabin-Karp string search algorithm

A long string can be represented by a fingerprint using a random mapping.

Two strings are likely identical if their fingerpints are identical.

Average running time

O(n + m)

Pseudocode

1 function RabinKarp(string s[1..n], string sub[1..m])

2 hsub := hash(sub[1..m]); hs := hash(s[1..m])

3 for i from 1 to n-m+1

4 if hs = hsub

5 if s[i..i+m-1] = sub

6 return i

7 hs := hash(s[i+1..i+m])

8 return not found

The algorithm can be extended for multiple pattern search.

Intention: *Fingerprinting and hashing*

**Randomized Primality Test**

Fermat’s Little Theorem

If *n* is a prime number, and *a* is any natual number less than *n*, then *a*^(*n* – 1) = 1 (mod *n*).

Conversely, in general, if *n* is not a prime, most of *a* < *n* will not satisfy the above equation.

*a* is a witness of the compositeness of *n*.

Sumarization:

We know there are lots of witnesses, if a number is composite.

But we do not know which one is a witness, and it is time consuming to search one by one.

Solution:

Randomly choose one, then check to see if it is a witness.

The algorithm is a Monte Carlo algorithm with one-side error.

Miller–Rabin Primality Test (1977)

If *n* is composite, then at least ¾ of the natual number less than *n* are witnesses of its compositeness.

Monte Carlo algorithm with one-side error of ¼.

Intention: *Exploit the abundance of witness*

Seach space is too large to be searched exhaustively. But the space contains a large number of witnesses.

**Game Theory Viewpoint**

List a table of all possible (correct) algorithms as columns, all possible inputs as rows.

Row: maximize the cost; Column: minimize the cost

Determinstic algorithn

Fix a colume

Column choose first, row choose next

Worst case of a deterministic algorithm

Las Vegas randomized algorithm

A probability distrubution over the deterministic algorithms (columes)

**Randomized Rounding**

A general scheme for appoximation algorithms.

Steps:

1. Formulate the problem to integer linear program (ILP)

2. Solve the linear programming relaxation (LP) of the ILP

3. Round the fractural solution of LP to integer solution of ILP

In step 2, the fractual solution produces a bound for ILP.

In step 3,

The main technique: randomized rounding.

Given any fractional solution x of the LP, with positive probability the randomized rounding process produces an integer solution x’ that approximates x according to some desired criterion.

**Further Reading**

Pattern Matching

Determinstic algorithm: Boyer-Moore string search algorithm

Example: Verification of matrix multiplication

Primality Test

Solovay–Strassen primality test (Use Euler witness)

AKS primality test (deterministic algorithm, 2002)

RSA (Easy to check primality, but hard to factor)

Game Theory Viewpoint

von Neumann’s Minimax Theorem

Randomized Rounding

Example: Set cover problem

Probabilistic method in combinatorics

Derandomization

Adleman’s Theorem

Probability amplification

Book: Randomized algorithms (1995)