Robert Šámal, Martin Tancer
Lecture: Thu, 15:40, S6,
Exercise classes: Thu, 17:20, S6 (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 are scheduled in the IS. If you have special requiests, let us know by email:
samal@iuuk and tancer@kam, where `iuuk' stands for iuuk.mff.cuni.cz and `kam'
stands for kam.mff.cuni.cz.
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
Will be added during the term.
 Oct 3 (MT)

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}$, 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, $1 + x \leq e^x$. Continuation with basic notions: Independent
events, conditional probability. [MV 1, 2.1, AS 1.1]
 Oct 10 (MT)

Further applications of probabilistic approach: CNF formulas where each clause
has $k$ distinct literals and number of clauses is less than $2^k$ is satisfiable;
ErdősKoRado 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. [MV 1,
2.3, 3.1, AS 2.1, your own notes (CNF formulas)]
 Oct 17 (MT)

Applications of linearity of expected value: Number of fixed points in a random
permutation. 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. 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.) [MV 4.0, 4.2, AS 3.3, your own
notes (Bayes, multiplication testing)]
 Oct 31 (MT)

Finishing the proof from the last time. 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]
 Nov 7 (MT)

Proof that $1/n$ is a threshold function for triangle containment.
Threshold function for containment of a balanced graph $H$. HardyRamanujan
theorem (the number of primes dividing an integer $n$ is typically close to
$\ln \ln n$); final computations in the proof only sketched. [MV 5.3, AS 4.2]
 Nov 14 (RS)

Lovász local lemma, symmetric version.
Three applications: twocolorability of a sparse hypergraph, routing in a graph by edge disjoint paths, and cycles of length divisible by $k$ in directed graphs.
 Nov 21 (RS)

Statement of the general Local Lemma. General implies symmetric. (But proof of general LL is skipped.) Remarks about algorithmic version.
Basic Chernoff inequality. Comparison to Chebyshev inequality.
Several easy applications.
Comparison to Central Limit Theorem.
[MU 7.2 or MV 7.17.2.]
 Nov 28 (RS)

More variants of the Chernoff inequality. [MU, O'D starting on page 84]
Randomized routing in a hypercube [MU 4.5.1].
 Dec 5 (RS)

Markov chains: definition, representation by finite automata and by matrices. Algorithms for 2SAT and for 3SAT.
Markov chain on a finite path and on an infinite path.
[MU 7.1]
 Dec 12 (RS)

More Markov chains: accesible/communicating states, states transient/recurrent, and null/positive recurrent, examples.
Periodic/aperiodic states/MC. Ergodic states/MC.
[MU 7.2, 7.3]
 Dec 18 (RS)

Finite irreducible aperiodic Markov chain is ergodic (with a proof).
Theorem about stationary distribution of a Markov chain. We omitted the proof.
Motivation of the ballsandbins: birthday paradox, bucketsort, maximum in a bin (upper bound). [MU 5.1]
 Jan 8 (RS)

Ballsandbins: lower bound on the maxload.
Poisson random variables, Poisson approximation for ballsandbins.
Power of two choices (without a proof). [MU 5.25.4]
board
(Corrected version  version before Jan 21 had a typo in the formula for Poisson distribution!)