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

Lecture: Thu, 14:00, S3, Exercise classes: Wed, 15:40, S7 (TA Matěj Konečný). Webpage for exercise classes: web of Matěj Konečný.

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

Zkoušky/Exams

Exam times will be scheduled by individual arrangement. Let both of us know by email: tereza@kam and tancer@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 .

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

• [AS] 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.
• [O'D] R. O'Donell: Probability and Computing lecture notes
• J. Spencer: Ten lectures on the probabilistic method, SIAM, 1987
• One chapter of J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics. (covers just a first part of the class).

Topics covered

Oct 3 (TK)
Overview of basic notions in probability: probability space, examples, union bound. 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. [MV 1, 2.1, AS 1.1]
Oct 10 (TK)
Aplikace pravděpodobnostního přístupu: CNF formule kde každá klauzule má $k$ různých literálů a počet klauzulí méně než $2^k$ je splnitelná. Erdős-Ko-Radova věta. Další pravděpodobnostní koncepty: náhodné veličiny, střední hodnota, nezávislé náhodné veličiny, linearita střední hodnoty, součin středních hodnot pro nezávislé náhodné veličiny, indikátorové náhodné veličiny. Aplikace: střední hodnota počtu pevných bodů v náhodné permutaci. [MV 1, 2.3, 3.1, AS 2.1, vlastní poznámky (CNF formule)]
Oct 17 (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. [MV 3, 4.1, AS 2.1, 2.2, 2.4, your own notes (MAXCUT, derandomization)]
Oct 24 (MT)
Markov's inequality. Showing the existence of graphs with arbitrarily high chromatic number and girth. Bayes theorem. Geometric/continuous application of alterations: Points in unit square and triangles of small area. [MV 4.0, 4.2, AS 3.3, your own notes (Bayes)]
Oct 31 (MT)
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. The function $1/n$ is a threshold function for triangle containment. (A proof will be given on the next lecture.) [MV 5.1, 5.2, 5.3, your own notes for matrix multiplication]
Nov 7 (MT)
Proof that $1/n$ is a threshold function for triangle containment. Threshold function for containment of a balanced graph $H$. Lovász local lemma, symmetric version. [MV 5.3, 6.1]
Nov 14 (MT)
Small correction in the definition of dependency graph. Three applications of Lovász local lemma: routing in a graph by edge disjoint paths, two-colorability of a sparse hypergraph, and cycles of length divisible by $k$ in directed graphs. (In the last case, the bound on the degree in the dependency graph only sketched.) General version of Lovász local lemma. General implies symmetric. (General without proof.) [MU 6.7.1 (with slightly different constants), MV 6.1--6.3]
Nov 21
There is no lecture! (DOD)
Nov 28 (MT)
Finished the claim about the dependency graph from last time. Basic Chernoff's bound. Application: combinatorial discrepancy. Variant of Chernoff's bound. Application to randomized rounding for the k-matching problem. (Some steps were only sketched.) [MV 7.1-7.2.]
Dec 5 (TK)
Markov chains: definition, representation by finite automata and by matrices. Algorithms for 2-SAT and for 3-SAT (will be finished next time). [MU 7.1]
Dec 12 (TK)
Finishing 3-SAT algorithm. More Markov chains: accesible/communicating states, states transient/recurrent, and null/positive recurrent, examples. Periodic/aperiodic states/MC. Ergodic states/MC. Example: Gambler's ruin. Theorem about stationary distribution of a Markov chain (proof next time). [MU 7.2, 7.3]
Dec 19 (TK)
Theorem about stationary distribution of a Markov chain (partial proof based on these notes). Balls and bins: birthday paradox, maximum load, bucket sort. Poisson distribution. [MU 5.1-5.2]
Jan 9 (TK)
Sum of independent Poisson random variables is a Poisson random variable. Poisson distribution is a limit of the binomial distribution. Approximation for balls-and-bins. Balls-and-bins: lower bound on the max-load. [MU 5.3-5.4]