Probabilistic techniques NTIN022

Lecture: Tue, 9:00, S1, Tereza Klimošová and Matěj Konečný
Tutorials: Tue, 15:40, S8, Tomáš Hons and Giuseppe Pino, webpage for tutorials.

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

Office hours: By individual arrangement by email: tereza@kam and matej@kam, where 'kam' stands for kam.mff.cuni.cz.

Exams: Exam times will be scheduled by individual arrangement. Let both of us know by email: tereza@kam and matej@kam, where 'kam' stands for kam.mff.cuni.cz, when you are available to take an exam.

Annotation: 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.

Syllabus:
  • Basic notions and methods: events, expected value and its linearity, conditional probability, Bayes' rule.
  • Basic inequalities and estimates: Markov's and 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.
References:
  • [AS] N. Alon, J. Spencer: The Probabilistic Method, J. Wiley and Sons 1993, 2008, 2015, pdf.
  • [MU] M. Mitzenmacher, E. Upfal: Probability and Computing, Cambridge University Press, 2005, pdf.
  • [MR] M. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press, 1995.
  • [O'D] R. O'Donell: Probability and Computing, lecture notes .
  • [[MV] J. Matoušek, J. Vondrák: The Probabilistic Method, ITI Series (preprints Institute of Computer Science, MFF UK), 2002-087; pdf .
Topics covered
  • Sept 29 (MK): Motivation, quick overview of basic stuff (probability spaces, independence, conditional probability, union bound). Colourability of hypergraphs with few edges. Random graph G(n,p). Proof that the Ramsey number R(k) > 2^(k/2-1). [MV 1, 2.1, 2.2]
  • Oct 6 (MK): Erdős-Ko-Rado theorem. Random variables and linearity of expectation: Overview, expected number of fixed points in a random pertumation, Szele's theorem (Hamiltonian paths in tournaments), "MAXCUT" with a sketch of derandomization via conditional expectation. [MV 1.1, 2.3, 3]
  • Oct 13 (MK): Markov's inequality. Method of alteration: Weak Turán's theorem, existence of graphs with arbitrarily large girth and chromatic number, Heilbronn's triangle problem. [MV 4, AS 3.3, this AI generated note for Heilbronn]
  • Oct 20 (MK): Variance (and motivation (and also covariance (and correlation (but only mentioned (correlation, covariance was covered fully and professionally)))). Chebyshev's inequality. Estimating the central binomial coefficient. Threshold function for G(n,p) containing a triangle. [MV 5.1, 5.2, 5.3]