||Probability spaces, events, independence, conditioning. Examples: Veryfing polynomial identities and matrix multiplication.
|| Ch 1 of [MU] with slightly more formal definitions for prob space
|| Examples of probability spaces, Borel sets, Lebesgue measure. Random variables and expectation. Linearity of expectation.
|| Beginning of ch 2 of [MU] with more formal definitions. See also lecture notes 1,2,3 from this course
|| Geometric and binomial distributions. Coupon collector problem. Randomized quicksort. Markov's inequality.
Variance. Variance of a sum of independent random variables. Chebychev's inequality.
|| Continuing ch 2 and beginning of ch 3 of [MU]
|| Chernoff bounds for binomial(n,1/2) and sums of independent 0,1 random variables. Sampling application of Chernoff. Load balancing (Chernoff + union bound method).
|| Ch 4 of [MU]. See also [O'Do] on Chernoff bounds and load balancing.
|| Random processes. Balls and bins: birthday problem, maximum load (ln n)/(ln ln n) for n = m. Poisson approximation (Bin(n,c/n) similar to Poi(c)) Random graphs: isolated vertices. Branchings processes (definition and analysis of expected size of generation n). Defined conditional expectation (for discrete rvs).
|| Ch 5 [MU]. Lecture notes on random graphs (also has a chapter on branching processes)
Finished branching processes: extinction probability. The probabilistic method. Lower bound on Ramsey numbers. Using expectation argument: maximum satisfiability. Sample and modify: graphs with large girth.
Lovasz local lemma: sufficient condition for a formula to be satisfiable.
|| Ch 6 [MU]
Randomized algorithms. Monte-Carlo and Las Vegas. Examples: Min-cut (contractions), Miller-Rabin primality testing and finding an assignement satisfying 7/8 clauses.
Started coninuous distributions.
|| Ch 1 of [MU] for min-cut.
[O'Do] for Miller Rabin
Continuous distributions. Jointly continuous disctribution. Buffon's needle example. Minimum of n uniforms.
Examples: Uniform, exponential (with memoryless property), (Multivariate) Normal distribution.
Application: Johnson-Lindenstrauss for dimension reduction (without proof)
|| Ch 8 of [MU]