Randomization

Bart Massey

Basic Idea

Use randomization as a technique for accelerating algorithms * As opposed to expected-case analysis * Usually doesn't improve worst-case performance * Can make expected-case good and worst-case vanishingly unlikely

Generating Random Numbers

• Definitions of random:

  • Unpredictable
  • Physically random
  • Uncorrelated

• Construction of PRNGs

  • Linear
  • Crypto-secure

Using Random Numbers in Algorithms

• Finding approximate median

  • Using this to find actual median

• Local search

• Randomizing inputs

The Perfect Shuffle

• Construct from "obvious" random selection algorithm
  • Replace array shifts with fill-ins
  • Replace output array with blanks in input array
  • Proof of correctness is thus easy

Random Weighted Selection

• Application: Bayesian Particle Filtering

• Technique: Start with "obvious" scan through weights

  • Accelerate by DP + binary search
  • Accelerate by merging
  • Fixing the merge order
  • Improving constant factors