Efnisyfirlit

• Cover
• Half title
• Title
• Copyright
• Dedication
• Table of Contents
• Preface to the Second Edition
• Preface to the First Edition
• 1 Events and Probability
• 1.1 Application: Verifying Polynomial Identities
• 1.2 Axioms of Probability
• 1.3 Application: Verifying Matrix Multiplication
• 1.4 Application: Naïve Bayesian Classifier
• 1.5 Application: A Randomized Min-Cut Algorithm
• 1.6 Exercises
• 2 Discrete Random Variables and Expectation
• 2.1 Random Variables and Expectation
• 2.1.1 Linearity of Expectations
• 2.1.2 Jensen’s Inequality
• 2.2 The Bernoulli and Binomial Random Variables
• 2.3 Conditional Expectation
• 2.4 The Geometric Distribution
• 2.4.1 Example: Coupon Collector’s Problem
• 2.5 Application: The Expected Run-Time of Quicksort
• 2.6 Exercises
• 3 Moments and Deviations
• 3.1 Markov’s Inequality
• 3.2 Variance and Moments of a Random Variable
• 3.2.1 Example: Variance of a Binomial Random Variable
• 3.3 Chebyshev’s Inequality
• 3.3.1 Example: Coupon Collector’s Problem
• 3.4 Median and Mean
• 3.5 Application: A Randomized Algorithm for Computing the Median
• 3.5.1 The Algorithm
• 3.5.2 Analysis of the Algorithm
• 3.6 Exercises
• 4 Chernoff and Hoeffding Bounds
• 4.1 Moment Generating Functions
• 4.2 Deriving and Applying Chernoff Bounds
• 4.2.1 Chernoff Bounds for the Sum of Poisson Trials
• 4.2.2 Example: Coin Flips
• 4.2.3 Application: Estimating a Parameter
• 4.3 Better Bounds for Some Special Cases
• 4.4 Application: Set Balancing
• 4.5 The Hoeffding Bound
• 4.6* Application: Packet Routing in Sparse Networks
• 4.6.1 Permutation Routing on the Hypercube
• 4.6.2 Permutation Routing on the Butterfly
• 4.7 Exercises
• 5 Balls, Bins, and Random Graphs
• 5.1 Example: The Birthday Paradox
• 5.2 Balls into Bins
• 5.2.1 The Balls-and-Bins Model
• 5.2.2 Application: Bucket Sort
• 5.3 The Poisson Distribution
• 5.3.1 Limit of the Binomial Distribution
• 5.4 The Poisson Approximation
• 5.4.1* Example: Coupon Collector’s Problem, Revisited
• 5.5 Application: Hashing
• 5.5.1 Chain Hashing
• 5.5.2 Hashing: Bit Strings
• 5.5.3 Bloom Filters
• 5.5.4 Breaking Symmetry
• 5.6 Random Graphs
• 5.6.1 Random Graph Models
• 5.6.2 Application: Hamiltonian Cycles in Random Graphs
• 5.7 Exercises
• 5.8 An Exploratory Assignment
• 6 The Probabilistic Method
• 6.1 The Basic Counting Argument
• 6.2 The Expectation Argument
• 6.2.1 Application: Finding a Large Cut
• 6.2.2 Application: Maximum Satisfiability
• 6.3 Derandomization Using Conditional Expectations
• 6.4 Sample and Modify
• 6.4.1 Application: Independent Sets
• 6.4.2 Application: Graphs with Large Girth
• 6.5 The Second Moment Method
• 6.5.1 Application: Threshold Behavior in Random Graphs
• 6.6 The Conditional Expectation Inequality
• 6.7 The Lovász Local Lemma
• 6.7.1 Application: Edge-Disjoint Paths
• 6.7.2 Application: Satisfiability
• 6.8* Explicit Constructions Using the Local Lemma
• 6.8.1 Application: A Satisfiability Algorithm
• 6.9 Lovász Local Lemma: The General Case
• 6.10* The Algorithmic Lovász Local Lemma
• 6.11 Exercises
• 7 Markov Chains and Random Walks
• 7.1 Markov Chains: Definitions and Representations
• 7.1.1 Application: A Randomized Algorithm for 2-Satisfiability
• 7.1.2 Application: A Randomized Algorithm for 3-Satisfiability
• 7.2 Classification of States
• 7.2.1 Example: The Gambler’s Ruin
• 7.3 Stationary Distributions
• 7.3.1 Example: A Simple Queue
• 7.4 Random Walks on Undirected Graphs
• 7.4.1 Application: An s–t Connectivity Algorithm
• 7.5 Parrondo’s Paradox
• 7.6 Exercises
• 8 Continuous Distributions and the Poisson Process
• 8.1 Continuous Random Variables
• 8.1.1 Probability Distributions in R
• 8.1.2 Joint Distributions and Conditional Probability
• 8.2 The Uniform Distribution
• 8.2.1 Additional Properties of the Uniform Distribution
• 8.3 The Exponential Distribution
• 8.3.1 Additional Properties of the Exponential Distribution
• 8.3.2* Example: Balls and Bins with Feedback
• 8.4 The Poisson Process
• 8.4.1 Interarrival Distribution
• 8.4.2 Combining and Splitting Poisson Processes
• 8.4.3 Conditional Arrival Time Distribution
• 8.5 Continuous Time Markov Processes
• 8.6 Example: Markovian Queues
• 8.6.1 M/M/1 Queue in Equilibrium
• 8.6.2 M/M/1/K Queue in Equilibrium
• 8.6.3 The Number of Customers in an M/M/∞ Queue
• 8.7 Exercises
• 9 The Normal Distribution
• 9.1 The Normal Distribution
• 9.1.1 The Standard Normal Distribution
• 9.1.2 The General Univariate Normal Distribution
• 9.1.3 The Moment Generating Function
• 9.2* Limit of the Binomial Distribution
• 9.3 The Central Limit Theorem
• 9.4* Multivariate Normal Distributions
• 9.4.1 Properties of the Multivariate Normal Distribution
• 9.5 Application: Generating Normally Distributed Random Values
• 9.6 Maximum Likelihood Point Estimates
• 9.7 Application: EM Algorithm For a Mixture of Gaussians
• 9.8 Exercises
• 10 Entropy, Randomness, and Information
• 10.1 The Entropy Function
• 10.2 Entropy and Binomial Coefficients
• 10.3 Entropy: A Measure of Randomness
• 10.4 Compression
• 10.5* Coding: Shannon’s Theorem
• 10.6 Exercises
• 11 The Monte Carlo Method
• 11.1 The Monte Carlo Method
• 11.2 Application: The DNF Counting Problem
• 11.2.1 The Naïve Approach
• 11.2.2 A Fully Polynomial Randomized Scheme for DNF Counting
• 11.3 From Approximate Sampling to Approximate Counting
• 11.4 The Markov Chain Monte Carlo Method
• 11.4.1 The Metropolis Algorithm
• 11.5 Exercises
• 11.6 An Exploratory Assignment on Minimum Spanning Trees
• 12 Coupling of Markov Chains
• 12.1 Variation Distance and Mixing Time
• 12.2 Coupling
• 12.2.1 Example: Shuffling Cards
• 12.2.2 Example: Random Walks on the Hypercube
• 12.2.3 Example: Independent Sets of Fixed Size
• 12.3 Application: Variation Distance Is Nonincreasing
• 12.4 Geometric Convergence
• 12.5 Application: Approximately Sampling Proper Colorings
• 12.6 Path Coupling
• 12.7 Exercises
• 13 Martingales
• 13.1 Martingales
• 13.2 Stopping Times
• 13.2.1 Example: A Ballot Theorem
• 13.3 Wald’s Equation
• 13.4 Tail Inequalities for Martingales
• 13.5 Applications of the Azuma–Hoeffding Inequality
• 13.5.1 General Formalization
• 13.5.2 Application: Pattern Matching
• 13.5.3 Application: Balls and Bins
• 13.5.4 Application: Chromatic Number
• 13.6 Exercises
• 14 Sample Complexity, VC Dimension, and Rademacher Complexity
• 14.1 The Learning Setting
• 14.2 VC Dimension
• 14.2.1 Additional Examples of VC Dimension
• 14.2.2 Growth Function
• 14.2.3 VC dimension component bounds
• 14.2.4 ε-nets and ε-samples
• 14.3 The ε-net Theorem
• 14.4 Application: PAC Learning
• 14.5 The ε-sample Theorem
• 14.5.1 Application: Agnostic Learning
• 14.5.2 Application: Data Mining
• 14.6 Rademacher Complexity
• 14.6.1 Rademacher Complexity and Sample Error
• 14.6.2 Estimating the Rademacher Complexity
• 14.6.3 Application: Agnostic Learning of a Binary Classification
• 14.7 Exercises
• 15 Pairwise Independence and Universal Hash Functions
• 15.1 Pairwise Independence
• 15.1.1 Example: A Construction of Pairwise Independent Bits
• 15.1.2 Application: Derandomizing an Algorithm for Large Cuts
• 15.1.3 Example: Constructing Pairwise Independent Values Modulo a Prime
• 15.2 Chebyshev’s Inequality for Pairwise Independent Variables
• 15.2.1 Application: Sampling Using Fewer Random Bits
• 15.3 Universal Families of Hash Functions
• 15.3.1 Example: A 2-Universal Family of Hash Functions
• 15.3.2 Example: A Strongly 2-Universal Family of Hash Functions
• 15.3.3 Application: Perfect Hashing
• 15.4 Application: Finding Heavy Hitters in Data Streams
• 15.5 Exercises
• 16 Power Laws and Related Distributions
• 16.1 Power Law Distributions: Basic Definitions and Properties
• 16.2 Power Laws in Language
• 16.2.1 Zipf’s Law and Other Examples
• 16.2.2 Languages via Optimization
• 16.2.3 Monkeys Typing Randomly
• 16.3 Preferential Attachment
• 16.3.1 A Formal Version
• 16.4 Using the Power Law in Algorithm Analysis
• 16.5 Other Related Distributions
• 16.5.1 Lognormal Distributions
• 16.5.2 Power Law with Exponential Cutoff
• 16.6 Exercises
• 17 Balanced Allocations and Cuckoo Hashing
• 17.1 The Power of Two Choices
• 17.1.1 The Upper Bound
• 17.2 Two Choices: The Lower Bound
• 17.3 Applications of the Power of Two Choices
• 17.3.1 Hashing
• 17.3.2 Dynamic Resource Allocation
• 17.4 Cuckoo Hashing
• 17.5 Extending Cuckoo Hashing
• 17.5.1 Cuckoo Hashing with Deletions
• 17.5.2 Handling Failures
• 17.5.3 More Choices and Bigger Bins
• 17.6 Exercises
• Further Reading
• Index