Jump to content

User:Erel Segal/Probability and Computing 2006

From Wikipedia, the free encyclopedia

An index to:

Mitzenmacher, Michael; Upfal, Eli (2006). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. ISBN 9780521835404.

1. Events and Probability

[edit]
  1. Application: random algorithm for Polynomial identity testing
  2. Axioms of probability
  3. Application: random algorithm for verifying matrix multiplication.
  4. Application: random algorithm for finding a minimum cut.

2. Discrete Random Variables and Expectation

[edit]
  1. Random variables and expectation
  2. The Bernouli random variable and Binomial random variable.
  3. Conditional expectation
  4. The Geometric distribution
  5. Application: the expected run-time of quicksort

3. Moments and Deviations

[edit]
  1. Markov's inequality
  2. Variance and moments of a random variable.
    • Example: variance of a binomial random variable
  3. Chebyshev's inequality
  4. Application: random algorithm for computing median

4. Chernoff bounds

[edit]
  1. Moment-generating functions
  2. Deriving and applying Chernoff bounds
  3. Better bounds for some special cases
  4. Application: set balancing
  5. Application: Routing protocol for packet-routing in sparse networks.

5. Balls, bins and random graphs

[edit]
  1. Example: the birthday paradox
  2. Balls into bins
  3. The Poisson distribution
    • Limit of the binomial distribution
  4. The Poisson approximation
  5. Application: Hash table
  6. Random graphs
  1. The basic counting argument
  2. The expectation argument
  3. Derandomisation using conditional expectations
  4. Sample and Modify
  5. The Second moment method
  6. The conditional expectation inequality
  7. The Lovász local lemma
  8. Explicit constructions using the Local Lemma
  9. Lovász local lemma: the general case

7. Markov chains and Random walks

[edit]
  1. Markov chains: definitions and representation
  2. Classification of states
  3. Stationary distributions
    • Example: a simple queue
  4. Random walks on undirected graphs
  5. Parrondo's paradox

8. Continuous distributions and the Poisson process

[edit]
  1. Continuous Random Variables
  2. The Continuous uniform distribution
    • Additional properties of the uniform distribution
  3. The Exponential distribution
    • Additional properties of the exponential distribution
    • Example: Balls into bins with feedback
  4. The Poisson point process
    • Interarrival distribution
    • Combining and splitting Poisson processes
    • Conditional arrival time distribution
  5. Continuous time Markov processes
  6. Example: Markovian Queues

9. Entropy, randomness and information

[edit]
  1. The entropy function
  2. Entropy and binomial coefficients
  3. Entropy: a measure of randomness
  4. coding: Shannon's theorem

10. The Monte Carlo Method

[edit]
  1. The Monte Carlo method; FPRAS (Fully Polynomial Randomized Approximation Scheme).
  2. Application: the DNF counting problem - counting the number of satisfying assignments to a DNF formula
    • The Naive approach - might be exponential-time.
    • A FPRAS for DNF counting - always polynomial-time.
  3. From approxiamte sampling to approximate counting
  4. The Markov chain Monte Carlo method

11. Coupling of Markov chains

[edit]
  1. Variation distance and Mixing time
  2. Coupling
  3. Application: Variation distance is nonincreasing
  4. Geometric convergence
  5. Application: Approximately sampling proper colorings
  6. Path coupling

12. Martingales

[edit]
  1. Martingales and Doob martingale
  2. Stopping time
  3. Wald's equation
  4. Tail inequalities for martingales
  5. Applications of the Azuma-Hoeffding inequality

13. Pairwise independence and Universal hash function

[edit]
  1. Pairwise independence
    • Example: a construction of Pairwise Independent Bits
    • Application: Derandomizing of Algorithm for Large Cuts
    • Example: constructing pairwise independent values modulu a prime
  2. Chebyshev's inequality for Pairwise independent variables
    • Application: sampling using fewer random bits
  3. Families of Universal hash functions
    • Example: a 2-universal family of hash functions
    • Example: a strongly 2-universal family of hash functions
    • Application: perfect hashing
  4. Application: finding heavy hitters in data streams

14. Balanced allocations

[edit]
  1. The power of two choices
    • The upper bound
  2. Two choices: the lower bound
  3. Applications of the power of two choices
    • Hashing
    • Dynamic resource allocation
[edit]