Tereza Klimošová, Martin Tancer

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

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

Zkoušky/Exams

Anotation

Organization remark

Lecture notes

Syllabus

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]