Jiří Sgall, Robert Šámal

Přednáška Pravděpodobnostní techniky (NTIN022) 2016/17

Přednáška: Pá 12:20 v S5, cvičení: Pá 14:00 v S6 (většina práce formou domácích úkolů). Informace o cvičeních: web cvičícího -- 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 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)

Probraná témata

6.10.2016: Jak dokázat existenci grafu házením korunou: dolní odhad na Ramseyova čísla, $R(k) > 2^{k/2}$, kde $R(k,k)$ je Ramseyovo číslo, minimální počet vrcholů grafu, který zaručeně má nezávislou množinu nebo kliku s $k$ vrcholy. Připomenutí a přehled základních pojmů z pravděpodobnosti: pravděpodobnostní prostor, union bound -- subaditivita pravděpodobnosti, nezávislé jevy. Odhady pro faktoriál, kombinační čísla, $1+x \le e^x$.
13.10.2016: Další aplikace základní metody: formule v CNF, kde každá klauzule má $k$ literálů a počet klauzulí je menší než $2^k$ je splnitelná. Pokračování úvodního přehledu praděpodobnosti: náhodné veličiny, linearita střední hodnoty, distribuce, nezávislé veličiny. Přehled distribucí (diskrétních i spojitých). Využití linearity střední hodnoty: Počet pevných bodů náhodné permutace. Existuje turnaj s mnoha hamiltonovskými cestami.
20.10.2016: MAX-SAT -- jak splnit mnoho klauzulí ve formuli. Každý graf má řez obsahující alespoň polovinu hran. (a metoda na derandomizaci -- nalezení řezu efektivním algoritmem) Plus-mínusové součty vektorů mohou být malé i velké.
Metoda změny Slabá Turánova věta: $\alpha(G) \geq n/2d$, kde $\alpha$ je max. velikost nezávislé množiny v grafu s $n$ vrcholy a průměrným stupněm $d$.
Markovova nerovnost Existence grafů s libovolně velkým obvodem a barevností.
4.11.2016: Bayesovo pravidlo. Aplikace na testování násobení matic.
Konstrukce množiny bodů ve čtverci bez malých trojúhelníků. (Metoda změny.)
Rozptyl, standardní odchylka, kovariance. Výpočet rozptylu pro součet náhodných veličin.
11.11.2016 -- přednáška se nekonala
18.11.2016 -- přednáška se nekonala
25.11.2016: Čebyševova nerovnost (s důkazem). Náhodné grafy, zavedení prahové funkce. Prahová funkce pro "obsahovat $K_4$" je $n^{2/3}$. Prahová funkce pro "obsahovat libovolný podgraf" (pomocí hustoty podgrafu, pro balancované grafy).
2.12.2016 -- přednáška dvakrát: Čebyševova nerovnost -- další aplikace: odhad prostředního binomického čísla, množiny s různými součty Lovászovo lokální lemma -- znění, aplikace (splnitelnost řídkých formulí, existence hr.disjunktních cest, cvičení s prostými zobrazeními). Černovova/Chernoffova nerovnost -- znění (zatím jen "symetrická"), aplikace (max. stupeň v $G(n,1/2)$, diskrepance). Důkaz lokálního lemmatu a znění v obecné verzi.
9.12.2016: Důkaz Černovovy nerovnosti. Dalších mnoho verzí (některé s důkazem). Aplikace na zaokrouhlování lineárního programu ($k$-párování v hypergrafu).
16.12.2016: Balls and bins. Dolní odhad přímým výpočtem. Poissonovo rozdělení, Poissonovská aproximace. Horní odhad přes Poissonovskou aproximaci. Síla dvou výběrů, znění odhadů s naznačením důkazu. [MU 5.1-5.4, 14.1]
6.1.2017: Markovovy řetězce. Definice časově homogenních diskrétních řetězců. Aplikace: Algoritmy pro 2-SAT a 3-SAT. [MU 7.1-7.2]
13.1.2017: Markovovy řetězce. Klasifikace stavů: transientní, pozitivně rekurentní, nulově rekurentní. Klasifikace řetězců: ireducibilni, (a)periodické, ergodické. Stacionární distribuce, její existence a jednoznačnost pro konečné ergodické řetězce. Poznámky ke stacionárním distrubucím. Spojité Markovovy řetězce, exponenciální rozdělení a jejich vztah. [MU 7.3, 8.3, 8.5]