Martin Tancer
Lecture: Tue, 12:20, S10,
Exercise classes: Thu, 12:20, S7 (TA Denys Bulavka
and 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.
At the moment the plan is teaching with presence of the students
in the lecture room without a hybrid form. In case of difficulties, send me an
email and we will try to find some solution. You can find my email on my homepage.
Lecture contents
Exams
If you are interested in exams: I have scheduled three dates for exams in the
study information system (SIS). However, it is also possible to agree on a
different date. Send me an email, if you need a different date.
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 expected contents of the lecture,
you may check one of
the previous lectures
(some changes may occur).
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).
Slides from 2020
In case that you would find them useful, here are some slides from 2020 (not
for all lectures). However, they were intended for online teaching and it is
not guaranteed that they will match the lectures this year. Use on your own
risk: Lecture 1 , Lecture 2, Lecture 3, Lecture 4, Lecture 5, Lecture 6, Lecture 7.
Topics covered
 Oct 5 (taught by Matěj Konečný)

Motivation. 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, $e^x \geq 1+x$. Continuation with basic notions: Independent
events, conditional probability. [MV 1, 2.1, AS 1.1]
 Oct 12

Satisfiability of CNF formulas. ErdősKoRado theorem. Further notions: random
variables, expectation, linearity of expectation, independent random variables,
product of expectation for independent random variables, indicators.
Application: number of fixed points in a random permutation. [MV 1, 2.3, 3.1,
AS 2.1, slides above (CNF formulas)]
 Oct 19

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, slides above (MAXCUT, derandomization)]
 Oct 26

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 (proof started but not yet finished). [MV 4.0, 4.2, AS
3.3, slides above (Bayes)]
 Nov 2

Finishing the proof from the last time. 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 the middle binomial coefficient. [MV 5.1, 5.2, slides for matrix
multiplication]
 Nov 9

Threshold functions. The
function $1/n$ is a threshold function for triangle containment. An auxiliary
lemma for harder implication. Threshold
function for containment of a balanced graph $H$. [MV 5.3]
 Nov 16

Motivation. Dependency graph. Lovász local lemma, symmetric an general version. Shown how general implies symmetric but otherwise left without proof.
Two applications of Lovász local lemma: 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.) [MV
6.16.3]

 Nov 23

Chernoff's inequality for binomial distribution. Application:
combinatorial discrepancy. More general version of Chernoff's inequality for
sum of independent random variable attaining values in [0,1]. Application:
Randomized rounding (not finished). [MV, 7.1, 7.2]
 Nov 30
 Randomized rounding (proof finished). Markov chains:
definition, representation via transition matrix and via directed graph.
Relation between mth power of the transition matrix and probability of
transition from one state to another in m steps. [MV 7.2, MU 7.1]
 Dec 7

Randomized algorithms for 2SAT and for 3SAT. [MU 7.1]
 Dec 14
 More Markov chains: accesible/communicating states, transient/recurrent,
and null/positive recurrent states, examples. Gambler's ruin.
Periodic/aperiodic states/MC. Ergodic states/MC. Theorem about stationary distribution of a Markov chain (proof next time).
[MU 7.2, 7.3]
 Dec 21

Theorem about stationary distribution of a Markov chain (sketch of a proof
based on the PerronFrobenius theorem and Jordan decomposition; an alternative
proof can be found here). Balls and bins: birthday paradox, maximum load.
[MU 5.1]
 Jan 4

Bucket sort. Poisson distribution, its expected value.
Sum of independent Poisson random variables is a Poisson random variable.
Poisson distribution is a limit of the binomial distribution. Approximation for
ballsandbins. [MU 5.25.3]