## 随机算法简介 — 提纲

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

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)

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])

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.

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