Probabilistic techniques NTIN022, ZS 2020/21

Tuesday 12:20-13:50, distant form, ZOOM. (Information to connect on request.) Continuation of the lectures 1 - 7 by Martin Tancer.
EXAM QUESTIONS: (final list by Jan 13, 2021). LaTeX forms of lecture notes: in final or semifinal (things to be added are not relevant for the exam) form by Jan 13. Note improved definitions of Markov chains.
1.1. Define basic notions of the probabilistic method - (discrete) prob. space, union bound, independence of events, the random graph G(n,p), conditional probability, (discrete) random variable, expected value, independent random variables, ... - and illustrate them by examples.
1.2. Prove by the probabilistic method the bound R(k) > 2^{k/2} for the Ramsey numbers.
2.1. State and prove the Erdos--Ko--Rado theorem.
3.1. Prove two applications of linearity of expectations: Szele's theorem and balancing vectors.
3.2. Alterations: state and prove weak Turan's theorem.
4.1. Alterations: prove that there exist graphs with arbitrarily high chromatic number and (simultaneously) girth.
4.2. Alterations: prove that there exist n points in the unit square such that the minimum area of a triangle spanned by three of them is >> 1/n^2.
5.1. Describe Frievalds' randomized algorithm for matrix multiplication testing.
6.1. Define the notion of threshold function. Prove that p=p(n)=1/n is the threshold function for triangle contínment in G(n, p). State the generalization for balanced graphs.
7.1. State LLL and prove its applications: coloring hypergraphs; edge disjoint paths; directed cycles.
8.1. Prove that every discrete probability space is atomic and contains only boundedly many independent coin tosses.
8.2. Explain Buffon's needle problem, Bertrands' paradox and Valtr's theorem on random convex chains.
8.3. Prove the upper bound R(k)<4^k on Ramsey numbers and give the 1947 proof of P. Erdos of the lower bound R(k)>2^{k/2}.
9.1. Prove the symmetric LLL with the bound that 4dp is at most 1.
9.2. Prove Bernstejn's theorem on large deviations.
10.1. Describe the Rabin-Knuth algorithm for randomized primality testing, what does the algorithm exactly achieve?
10.2. This will not be examined: Describe the randomized algorithm for 2-SAT and analyze it by Markov chains (I am not satisfied with my exposition of this topic).
11.1. Give a reasonably detailed outline of the proof of Polya's theorem on random walk on Z^d.
12.1. Give a reasonably detailed outline of the proof of the theorem on existence of stationary distribution for a finite Markov chain.
13.1. Define Poisson random variables, give their basic properties, and prove them.
13.2. State the Janson inequalities and compute by them the limit for n-->oo of the probability Pr(G(n, c/n) contains no triangle).
Nov 24, 2020. Slides to the 8th lecture - handwritten version (the last 10th page is spoiled by the scanner but hopefully still readable). Correction: in the set system G(n,p), E is an element of P(binom([n], 2)), not a subset. Slides to the 8th lecture - LATEX version (final version of Jan 13, 2021). CONTENT: Some interesting books on the probability theory. Discrete probability spaces. Every discrete probability space is atomic, proof by transfinite induction. Independent coin tosses. Lemma on independence, proof. Theorem: in every discrete probability space there are only boundedly many independent coin tosses, proof. Buffon's needle problem, derivation of the formula. Bertrand's paradox. Theorem of P. Valtr on random convex chains of points, an open problem mentioned. Enumerative review of the lower bound on the Ramsey number R(k). Proof of the upper bound that R(k) is less than 4^k (thus R(k) is a well defined thing). Remarks on upper and lower bounds on R(k).
Dec 1, 2020. Slides to the 9th lecture - handwritten version. Slides to the 9th lecture - LATEX version (final version of Jan 13). CONTENT: The LLL (Lovasz Local Lemma). Dependency digraph. Lemma on independence, proof as before. General and symmetric LLL. Proof of the symmetric form with the slightly weaker bound that 4dp is at most 1, after the textbook of Mitzenmacher and Upfal. Remarks on the algorithmic LLL (J. Beck, G. Tardos and others). Chernoff's bounds. Review of random variables. Theorem (S. Bernstejn): Pr(X>t)=Pr(X less than -t) is less than exp(-t^2/2n) if X is a sum of n independent random variables with values 1 and -1 (attained with the same probability 1/2), proof. A generalization, no proof.
Dec 8, 2020. Slides to the 10th lecture - handwritten version. Slides to the 10th lecture - LATEX version (semifinal version by Jan 13). CONTENT: The law of iterated logarithm mentioned. An idiosyncratic description of the Rabin-Knuth algorithm for randomized primality testing. Markov chains. Transition matrix. A randomized algorithm for 2-SAT and its analysis by Markov chains (after the textbook of Mitzenmacher and Upfal).
Dec 15, 2020. Slides to the 11th lecture - LATEX version (final version of Jan 13, 2021). CONTENT: Again definition of a Markov chain. The Radon-Nikodym theorem mentioned. The existence theorem for Markov chains, no proof. Two examples: Ehrenfest model and random walk on Z^k. The 1st Borel-Cantelli lemma, proof. Derivation of the formula (2) for the probability P_i(X_n=i infinitely often). Theorem on persistent (stationary) and transient states, proof. Lemma, proof left as an exercise. Polya's theorem that in the random walk on Z^k all states are persistent for k<3, and all are transient for k>2, detailed proof for k=1, 2 and 3.
Dec 22, 2020. Slides to the 12th lecture - handwritten version. Slides to the 12th lecture - LATEX version (semifinal form of Jan 13, 2021). CONTENT: Irreducible and aperiodic finite Markov chains. If GCD(a_1, ..., a_k)=1 (a_i are integers) then for every large n the equation n=a_1b_1 +...+ a_kb_k has a solution in nonnegative integers b_i, proof. Stationary distribution of a finite Markov chain. Theorem: every finite, irr. and ap. Markov chain has stationary distribution, proof by means of three lemmas. L1, proof. L2, proof. L3, proof. Balls and bins. For the same number n of balls and bins, Pr(maximum load > 3log n/loglog n) < 1/n, proof. Bucket sort.
Jan 5, 2021. Slides to the 13th lecture - LATEX version (final version of Jan 13, 2021). CONTENT: Poisson random variable. Sum of Poisson RV is a Poisson RV, proof. Numbers of randomly moving particles have Poisson distribution, proof. Some results of J. Beck. Binomial distributions converge to a Poisson distribution, proof. Random subsets. Random subsets exist, proof. Statement of three Janson inequalities. For any c>0, the limit of Pr(G(n, c/n) contains no triangle) is exp(-c^3/6), proof by the first Janson inequality.

January 2021