Robert Šámal, Martin Tancer

Lecture on Probabilistic techniques (Přednáška Pravděpodobnostní techniky (NTIN022)) 2017/18

Lecture: Mo 15:40 in S4, Exercise classes: Mo 17:20 in S6. Webpage for exercise classes: web of Jan Voborník.

List of topics covered by lectures is at the bottom of this webpage.

Anotation

Probabilistic techniques are a major tool of discrete mathematics, they are also frequently used in design and analysis of algorithms and other areas of computer science. The lecture introduces basic notions, methods, and estimates and illustrates them on examples from computer science and discrete mathematics.
If you are interested in more details about the lecture, you may check the topics covered last year (in Czech).

Organization remark

Exercise classes will be based on individual work of the attendants (homeworks; they are supposed to be solved during the semester).

Lecture notes

[MV] J. Matoušek, J. Vondrák: The probabilistic method ITI Series (preprints Institute of Computer Science, MFF UK), 2002-087; available in the library of MFF UK.

Syllabus

Basic notions and methods: events, expected value and its linearity, conditional probability, Bayes' rule.
Basic inequalities and estimates: Markov's a Chebyshev's inequality, Chernoff-type estimates.
Probabilistic method: basic method and alteration method, Lovász local lemma.
Advanced techniques: balls and bins model, basic estimates and applications, Markov chains, stationary distribution, basic continuous distributions as limits of discrete ones, properties and applications. Illustration of the methods on examples from various areas of discrete mathematics and theoretical computer science.

References

N. Alon, J. Spencer: The Probabilistic Method, J. Wiley and Sons 1993, 2008, 2015.
[MU] M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005.
[MR] R. Motwani, P. Raghavan: Randomized algorithms, Cambridge University Press, 1995.
J. Spencer: Ten lectures on the probabilistic method, SIAM, 1987
kapitola ze skript J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky (pokrývá jen úvodní část přednášky)

Topics covered

Oct 2 (MT): Probabilistic approach for a proof of existence of certain graphs: $R(k) > 2^{k/2}$, where $R(k)$ is the Ramsey number, the minimal number of vertices that guarantees that a graph has an independent set or a clique with $k$ vertices. Overview of basic notions in probability: probability space, union bound, independent events, conditional probability. Estimates of factorial and binomial coefficients, $1 + x \leq e^x$. Expected value (at the moment only for a finite probability space).
Oct 9 (MT): Further applications of probabilistic approach: CNF formulas where each clause has $k$ literals and number of clauses is less than $2^k$ is satisfiable; Erdős-Ko-Rado theorem. Further basic notions from probability theory: random variables; expected value; independent variables; linearity of expected value; for independent variables, product of expected values is the expected value of product. Applications of linearity of expected value: Number of fixed points in a random permutation.
Oct 16 (MT): Further applications of linearity of expected value: tournaments with many Hamiltonian paths; MAXSAT - satisfying many clauses in a formula; MAXCUT - existence of a cut in a graph with many edges (derandomization of MAXCUT, sketched also MAXSAT); balancing vectors, $\pm$ sums of unit vectors can be achieved both high and low. Alterations: weak Turán theorem.
Oct 23 (MT): Markov's inequality. An existence of graphs with arbitrarily high chromatic number and girth. Bayes theorem. Application: testing $AB = C$ for three given $n \times n$ matrices faster than matrix multiplication. Geometric/continuous application of alterations: Points in unit square and triangles of small area. (Not finished yet.)
Oct 30 (MT): Finishing the proof from the last time. Variance, standard deviation, covariance. Variance of a sum of random variables. Chebyshev's inequality. Threshold functions. The function $1/n$ is a threshold function for triangle containment.
Nov 6 (MT): Threshold function for containment of a balanced graph $H$. Lower bound for a middle binomial coefficient. Chernoff inequality. Combinatorial discrepancy via Chernoff.
Nov 13 (RS): Variants of Chernoff inequality, comparison to Central Limit Theorem. Several easy applications. Longer application to randomized rounding to solve a k-matching problem. [MV 7.2]
Nov 20 (RS): Finishing the k-matching problem. Randomized routing in a hypercube [MU 4.5.1].
Nov 27 (MT): Lovász local lemma, symmetric and general version. Proof skipped, only shown: general implies symmetric. Two applications: edge disjoint paths and cycles of length divisible by $k$ in directed graphs.
Dec 4 (JSg): Markov chains: definition, representation by finite automata and by matrices. Algorithms for 2-SAT nad for 3-SAT. Markov chain on a finite path and on an infinite path. [MU 7.1]
Dec 11 (RS): More Markov chains: accesible/communicating states, states transient/recurrent, and null/positive recurrent, examples. Periodic/aperiodic states/MC. Ergodic states/MC. Theorem about stationary distribution. Start of the proof. [MU 7.2, 7.3]
Dec 18 (RS): Proof of the theorem about stationary distribution of Markov chains. Notes on the stationary distribution. Motivation of the balls-and-bins (birthday paradox). [MU 5.1]
Jan 8 (RS): Balls-and-bins: upper and lower bound on the max-load. Poisson random variables, Poisson approximation for balls-and-bins. [MU 5.2-5.4]