# Probabilistic techniques (NTIN022) 2015/16

Lecture: Wed 15:40 in S5, exercises: Wed 17:10 in S5 (but most of the work is homework problems, the exercise session at school will not happen every week). Information about exercises: web page of the TA -- Tomáš Toufar.

Seznam probrané látky najdete na konci teto stranky (průběžně doplňováno).

Rozsah výuky: ZS 2/2 Z, Zk

### Anotace

Pravděpodobnostní metoda je způsob důkazu existence kombinatorických objektů "počítáním". Pro mnoho důležitých objektů je to jediný známý důkaz. Pravděpodobnostní metoda se stále častěji objevuje i v návrhu a analýze algoritmu a v dalších odvětvích informatiky a patří k nejdůležitějším nástrojům diskrétní matematiky.
O náplní přednášky si můžete udělat představu podle látky probrané minule, letos ale (se změnou názvu) přichází několik nových témat: zejména Markovovské řetězce a modely "balls-and-bins". Letos se přednáška bude (patrně) přednášet česky.

### Organizační poznámky

Cvičení probíhá hlavně formou individuální práce posluchačů (domácí úkoly, třeba řešit průběžně během semestru).

### Učební text

Skripta J. Matoušek, J. Vondrák: The probabilistic method vyšla v ITI Sériích (preprintova řada Institutu teoretické informatiky MFF UK) pod číslem 2002-087 a je k dispozici v informatické knihovně MFF UK.

### Sylabus

Basic notions and methods: events, expected value and its linearity, conditional probability, Bayes' rule.
Basic inequalities and estimates: Markov's a 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. Illustration of the methods on examples from various areas of discrete mathematics and theoretical computer science.

### References

• 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.
• J. Spencer: Ten lectures on the probabilistic method, SIAM, 1987
• kapitola ze skript J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky (pokrývá jen úvodní část přednášky)

## Covered topics

Oct 7 How to prove existence of a graph by tossing a coin: $R(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. Overview of basic notions in probability: probability space, union bound, independent events.

Oct 14 Another application of basic probabilistic method: a formula in CNF, where every clause has $k$ literals and number of clauses is less than $2^k$ is satisfiable. Continuing in the Overview of basic probability: random variables, linearity of expectation, distribution, independent variables. List of distributions, both discrete and continuous:

Two application of linearity of expectation: The expected number of fixed points in a random permutation. Tournaments with many Hamiltonian paths. (Method of indicator variables.)

Oct 21 MAX-SAT -- how to satisfy many clauses in a formula.
Given a graph with $m$ edges, there is a cut of the graph with at least $m/2$ edges. Plus a method to derandomize this proof -- find an algorithm, that really finds the cut.
Method of alterations Weak Turán's theorem: $\alpha(G) \geq n/2d$ where $\alpha$ is the independence number of a graph with $n$ edges and average degree $d$.
Markov's inequality The existence of graphs with arbitrarily large girth and chromatic number.

Nov 4 Bayes law.
Probabilistic proof of the existence of a set of $n$ points in the square such that the area of each triangle formed by these $n$ points has area at least $\frac 1{100n^2}$.
The second moment method: variance, covariance, variance of a sum of random variables.
Chebyshev inequality. Application to an estimate of the middle binomial coefficient.

Nov 11 Probability that $G(n,p)$ has some monotone graph property (e.g., containing a triangle) is (for a fixed $n$) a nondecreasing function of $p$. Proof: coupling.
Treshold functions. The treshold function for property that $G(n,p)$ contains a triangle is $\frac1n$ (a proof using Chebyshev inequality). The treshold function for property that $G(n,p)$ contains a fixed subgraph $H$ is $n^{-1/\rho}$ where $\rho$ is the maximal density of a subgraph of $H$.
Given $n$ unit vectors, they can be equipped with signs $-1$ or $1$ such that the norm of their sum (with respect to the signs) is at most $\sqrt n$. (At least $\sqrt n$ can be reached as well.) (Note about Khintchin's inequality.)

Nov 18 Lovász local lemma: motivation, definitions, statement of the three versions. Two easy applications: satifiability of a "sparse" $k$-SAT formula and selecting disjoint paths. Proof of the basic version.

Nov 25 Chernoff bounds: Definitions, statement. Connections to the binomial distribution and central limit theorem. Easy application: amplification of the error probability for randomized algorithms (BPP languages). Application: Routing in hypercube networks. [MU 4.5.1, also MR 4.2 with the combinatorial lemma for the bound on delay]

Dec 2 Chernoff bounds: Proofs of the binomial version (uniformly random $-1,+1$ variables) and the multiplicative version. Comparison of the bounds. Estimating an unknown mean. [MU 4.1-4.3]

Dec 9 Balls and bins: Routing in hypercubes (continued). Balls and bins model, statement of the bounds, proof of the lower bound. [MU 5.1-5.2]

Dec 16 Balls and bins: Poisson approximation, upper bound proof for balls and bins. The power of two choices: statement without proofs. [MU 5.4, 14.1]

Jan 5 Markov chains: definition, Markov (memoryless) property, time-homogeneous discrete Markov chains. Applications: 2-SAT algorithm, 3-SAT randomized algorithm in time $O(1.334^n)$. Classification of states: transient, positive recurrent, null recurrent. [MU 7.1-7.2]

Jan 12 Markov chains: Example: Gambler's ruin. Classification of chains: irreducible, (a)periodic, ergodic. Stationary distribution, its existence and uniqueness for finite ergodic chains. Notes on the stationary distribution. Continuous time Markov processes, exponential distribution: definitions, relation between them. [MU 7.3, 8.3, 8.5]