Tereza Klimošová, Martin Tancer
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),
2002087; 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, Chernofftype 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/21}$, 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ősKoRadova 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, twocolorability 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.16.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 kmatching problem. (Some
steps were only sketched.)
[MV 7.17.2.]
 Dec 5 (TK)

Markov chains: definition, representation by finite automata and by matrices. Algorithms for 2SAT and for 3SAT (will be finished next time).
[MU 7.1]
 Dec 12 (TK)

Finishing 3SAT 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.15.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 ballsandbins. Ballsandbins: lower bound on the maxload. [MU 5.35.4]