Tereza Klimošová, Mykhaylo Tyomkyn

Lecture on Probabilistic techniques (NTIN022) 2022/23


Lecture: Mon, 9:00, S1. Exercise classes: Mon, 17:20, S6 (TA Denys Bulavka). Webpage for exercise classes.

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


Zkoušky/Exams

Exam times will be scheduled by individual arrangement. Please let Mykhaylo Tyomkyn know by email: tyomkyn@kam , where `kam' stands for kam.mff.cuni.cz, when you are available to take an exam.

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 an old webpage.

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 or you may get a revised version online

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

Topics covered

Oct 3 (TK)
Overview of basic notions in probability: probability space, union bound. Erdős-Rényi random graph. Probabilistic approach for a proof of existence of certain graphs: $R(k,k) > 2^{k/2-1}$, where $R(k,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. Estimates of factorial and binomial coefficients. Continuation with basic notions: Independent events, conditional probability, law of total probability. Application: CNF formula where every clause contains $k$ different literals and the number of clauses is less than $2^k$ is satisfiable. [MV 1, 2.1, AS 1.1]
Oct 10 (TK)
Erdős-Ko-Rado theorem. Further probabilistic concepts: random variables, expectation, independent random variables, linearity of expectation, product of expectations of independent random variables, indicators of random events. Applications: expected number of fixed points in a random permutation, tournaments with many Hamiltonian paths. [MV 1, 2.3, 3.1, 3.2, AS 2.1]
Oct 17 (TK)
Further applications of linearity of expected value: balancing vectors, $\pm$ sums of unit vectors can be achieved both high and low. With derandomization: MAXCUT - existence of a cut in a graph with many edges; MAXSAT - satisfying many clauses in a formula. Alterations: weak Turán theorem. Markov's inequality. [MV 3, 4.0 4.1, AS 2.1, 2.2, 2.4, your own notes (MAXCUT, derandomization (see AS 15 for idea of derandomization on a different example)]
Oct 24 (TK)
Showing the existence of graphs with arbitrarily high chromatic number and girth. Geometric/continuous application of alterations: Points in unit square and triangles of small area. [MV 4.2, AS 3.3]
Oct 31 (TK)
Testing $AB = C$ for three given $n \times n$ matrices faster than matrix multiplication. Variance, standard deviation, covariance. Variance of a sum of random variables. Chebyshev's inequality. Lower bound for a middle binomial coefficient. Threshold functions - preliminaries: triangle counts in G(n,p) - expectation and variance, to be continued during the next lecture. [MV 5.1, 5.2, 5.3, your own notes for matrix multiplication]
Nov 7 (TK)
Threshold function definition. Threshold function for containment of a balanced graph $H$. Lovász local lemma, symmetric version, general version (no proof). General implies symmetric. [MV 5.3, 6.1]
Nov 14 (TK)
Three applications of Lovász local lemma (symmetric version): routing in a graph by edge disjoint paths, two-colorability of a sparse hypergraph, and cycles of length divisible by $k$ in directed graphs. A sketch of an application of an asymmetric version: lower bound on Ramsey number R(3,l). [MU 6.7.1 (with slightly different constants), MV 6.2--6.3, your own notes for the application of asymmetric LLL]
Nov 21 (MT)
Basic Chernoff's bound. Applications: max degree in $G(n,1/2)$, combinatorial discrepancy. A more general variant of Chernoff's bound. [MV 7.1--7.2]
Nov 28 (MT)
Application of Chernoff to randomized rounding for the k-matching problem. Markov chains: definition, representation by finite automata and by matrices. Algorithms for 2-SAT and for 3-SAT (will be finished next time). [MV 7.2, MU 7.1]
Dec 5 (MT)
Finishing 2-SAT and 3-SAT algorithms. More Markov chains: accesible/communicating states, states transient/recurrent, and null/positive recurrent, examples. [MU 7.1, 7.2]
Dec 12 (MT)
Periodic/aperiodic states/MC. Ergodic states/MC. Example: Gambler's ruin. Theorem about stationary distribution of a Markov chain: proof based on these notes by Prof Sgall, and these by Prof Whitt (Columbia). [MU 7.2, 7.3]
Dec 19 (MT)
Balls and bins: birthday paradox, maximum load, bucket sort. Poisson distribution. [MU 5.1--5.3]
Jan 2 (MT)
Balls and bins: the Poisson approximation. A lower bound on max load. handwritten notes [MU 5.4]