Probability (for Computer Science)

Winter 2017 at ENS Lyon

General information

The topics we are planing to cover include



The grading scheme will take into account


Date Topic References
Jan 30th Probability spaces, events, independence, conditioning. Examples: Veryfing polynomial identities and matrix multiplication.
Ch 1 of [MU] with slightly more formal definitions for prob space
Feb 1st 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
Feb 8th 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]
Feb 27th 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.
Mar 5th 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)
Mar 13th 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]
Mar 20th 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
Mar 28th 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]