Metoda Probabilistyczna

Prowadzący

Marcin Kotowski
Michał Kotowski

Opis

dice.jpg

Metoda probabilistyczna polega na zastosowaniu rachunku prawdopodobieństwa do rozwiązywania problemów kombinatorycznych. Na przykład zamiast konstruować explicite jakiś obiekt o żądanych własnościach (kolorowanie grafu, strategię wygrywającą w grze, kod do przesyłania wiadomości itp.) pokazujemy, że losowy wybrany obiekt posiada taką własność z niezerowym prawdopodobieństwem. Tego typu niekonstruktywne techniki, wprowadzone po raz pierwszy przez Paula Erdösa, okazały się niezwykle skuteczne zarówno w czystej matematyce (m. in. w kombinatoryce, grafach losowych, geometrii), jak i w informatyce teoretycznej i algorytmice (np. w teorii złożoności czy algorytmach randomizowanych). Obecnie rachunek prawdopodobieństwa to podstawowe narzędzie z przybornika każdego szanującego się kombinatoryka (i nie tylko).

Program zajęć

Na program zajęć będzie składać się zarówno omówienie wybranych technik probabilistycznych (m.in. liniowość wartości oczekiwanej, metoda drugiego momentu, lemat lokalny Lovasza), jak i wyrobienie u uczestników ogólnej intuicji kombinatoryczno-rachunkowej. Poznane narzędzia zastosujemy do rozwiązywania problemów z kombinatoryki, teorii liczb, teorii grafów, geometrii itd. Przewidziane będzie dużo zadań do samodzielnego zrobienia, w tym zadanie okołoolimpijskie rozwiązywalne przy użyciu rachunku prawdopodobieństwa.

Wymagania

Poziom trudności będzie umiarkowany - warto lubić kombinowanie/kombinatorykę.

  • znajomość podstaw kombinatoryki i rachunku prawdopodobieństwa ($\binom{n}{k}$, wzór Stirlinga na n!, zmienna losowa, niezależność zdarzeń itp.)
  • może się przydać: pewna biegłość w stosowaniu nierówności (na poziomie nierówności średnich)

Z podstawowymi pojęciami można się zapoznać np. z tych notatek: http://www.math.ucdavis.edu/~gravner/MAT135A/resources/lecturenotes.pdf (rozdziały 1-5 i 7 - większość rzeczy w tym skrypcie jest bardziej zaawansowana, niż będziemy potrzebować, więc się nie przejmujcie). W razie jakichkolwiek problemów (inne materiały, wyjaśnienie pojęć itd.), piszcie!

Zadania kwalifikacyjne

Zadania są podzielone na dwie części - obowiązkową i dodatkową. Każdy uczestnik warsztatów powinien zrobić część obowiązkową (i to raczej bezbłędnie), a poza tym rozwiązać $k \leq 3$ spośród zadań dodatkowych. W przypadku dużej ilości chętnych o przyjęciu będzie decydować łączna suma punktów (to oznacza, że być może wystarczą 2 zadania dodatkowe, żeby zostać przyjętym, ale jeśli będzie dużo chęŧnych, to mogą być potrzebne 3 itd.)

Rozwiązania należy wysyłać na adres: moc.liamg|1ikswotok.lahcim#moc.liamg|1ikswotok.lahcim, tam też należy wysyłać uwagi co do zadań, pytania, wątpliwości itd. Można wysyłać rozwiązania na raty, przesyłać rozwiązania częściowe itp. Powodzenia!

w razie trudności ze zrozumieniem zadań - nie wahajcie się pisać

Zadania obowiązkowe

1. Zmienne losowe $X, Y, Z$ są parami niezależne. Czy zmienne $X+Y$ oraz $Z$ zawsze są niezależne?

2. Dwaj gracze rzucają niezależnie $n$ razy niesymetryczną monetą, na której orzeł wypada z prawdopodobieństwem $p$. Jakie jest prawdopodobieństwo, że otrzymają po tyle samo orłów? Wynik należy wyrazić zwartym wzorem dla $p = 1/2$ (dla dowolnego $p$ - jeśli potrafisz).

3. Udowodnij tożsamości:
a) $\sum_{k=0}^{n} k\binom{n}{k} = n2^{n-1}$
b) $\sum_{j=0}^{k}\binom{m}{j}\binom{n-m}{k-j} = \binom{n}{k}$

4. Na przyjęciu jest $6$ osób, z których każde dwie znają się lub nie. Udowodnić, że istnieją $3$ osoby, które znają się wzajemnie lub nie znają się wzajemnie.

5. Która funkcja rośnie szybciej (powiemy, że $f$ rośnie szybciej niż $g$, jeśli $\frac{f}{g} \rightarrow \infty$ dla $n \rightarrow \infty$): (wskazówki - wzór Stirlinga; jeśli f rośnie szybciej niż g, to jak się ma log f do log g, albo co można powiedzieć o log(f/g)? jak taka podpowiedź nie wystarczy, to piszcie)
a) $n^{\log n}$ czy $(\log n)^n$
b) $n^{\log(\log(\log n))}$ czy $(\log n)!$
c*) $(n!)!$ czy $((n-1)!)! (n-1)!^{n!}$ (proszę potraktować ten podpunkt jako "z gwiazdką", tj. nie w 100% obowiązkowy)

Zadania dodatkowe

Lista może ulec rozszerzeniu o nowe zadania.

6. (errata - treść uległa zmianie) Ile jest funkcji $f : \{1, \ldots, N \} \to \{1, \ldots, k \}$, $k > n$, takich, że $f(i + 1) > f(i) + i$ dla każdego $i = 1, \ldots, N - 1$? Wariant prostszy: znajdź ilość funkcji takich, że $f(i+1) > f(i) + 1$

7. Rozważmy zbiór $\{ 1, \ldots, N \}$ i losowo wybraną permutację $\pi$ tego zbioru (każda permutacja ma takie samo prawdopodobieństwo wystąpienia). Cykl długości $k$ to taki ciąg indeksów $i_{1}, \ldots, i_{k}$, że $\pi(i_{1}) = i_{2}, \pi(i_{2}) = i_{3}, \ldots, \pi(i_{k}) = i_{1}$.
a) Jakie jest prawdopodobieństwo, że $\pi$ zawiera cykl długości $m$?
b) Ile cykli długości $m$ wystąpi średnio w $\pi$?

8. a) pokazać, że każdą klikę można przedstawić jako sumę rozłącznych ścieżek różnych długości. (Klika to graf zawierający wszystkie możliwe krawędzie)
b) pokazać, że graf daje się przedstawić jako suma rozłącznych cykli wtedy i tylko wtedy, gdy każdy wierzchołek jest parzystego stopnia.

9. Załóżmy, że mamy niesymetryczną monetę (na której orzeł wypada z nieznanym prawdopodobieństwem), którą możemy wykonać $N$ rzutów. Zaproponować metodę zasymulowania za pomocą tej monety $L < N$ rzutów monetą symetryczną (przy czym $L$ może być losowe; im średnio $L$ większe, tym lepiej).

10. Niech $v_1, \dots, v_n$ będą wektorami w $\mathbb{R}^d$. Pokaż, że istnieje taki zbiór indeksów $I \subseteq \{1,2,\dots, n\}$, że zachodzi nierówność (kropka oznacza iloczyn skalarny):

(1)
\begin{align} 4 (\sum_{i \in I} v_i) \cdot (\sum_{j \notin I} v_j) \geq \sum_{i \neq j} v_i \cdot v_j \end{align}
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License