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]
Apr 3rd Convergence of random variables: almost sure and in probability. as => in prob but converse not true.
Weak and strong law of large numbers (on the way, Borel-Cantelli).
See lectures 4 and 5 of this course
Apr 10th Convergence in distribution, central limit theorem (proof sketch only).
Started Markov chains, definition, representation (matrix, graph). Example with analysis of 2-SAT algorithm.
See lecture 6 of this course and Ch 7 of [MU]
Apr 24th Finished the analysis of 2-SAT algorithm and discussed 3-SAT.
Notion of recurrent and transient states and different characterizations of it. Random walks on Z^d (recurrent for d <= 2 and transient for d > 2). Irreducible Markov chain.
Ch 7 of [MU]
May 2nd For an irreducible MC, if one state is recurrent then for all i,j probability to reach j starting at i is 1.
Definition of a stationary distribution. Obstacles to convergence: reducibility and periodicity.
For an irreducible MC with a stationary distribution, all states are recurrent
For an irreducible and aperiodic MC, for any states i,j there is an n0 such that P_{i,j}^{n} > 0 for all n > n0.
Main convergence theorem: For an irreducible and aperiodic MC with stationary distribution \pi, P_{i,j}^n -> \pi_j
Sufficient condition for stationary distribution: finite expected return time h_{i,i}. \pi_i = 1/h_{i,i} is then a stationary distribution.
For finite irreducible MC, h_{i,i} is always finite.
Ch 7 of [MU]
May 9th Important class of MCs: Random walks on graphs. Expected return time of i = 2 |E|/deg(i). Cover time for any graph is upper bounded by 4 |V| |E|.
Introduction to statistics.
Ch 7 of [MU]
May 15th Maximum Likelihood estimator. Hypothesis testing, p-value. Ch 1 of notes and parts from other chapters