Co łączy PageRank Google'a, symulowane wyżarzanie, part-of-speech tagging, szyfry strumieniowe, kody splotowe? Analizę każdego z wymienionych algorytmów/protokołów/gier można przeprowadzić poprzez badanie własności odpowiadających im procesów Markowa (Łańcuch Markowa jest ciągiem zdarzeń losowych, w którym kolejny stan zależy tylko od stanu obecnego).
Celem wykładu jest zapoznanie studentów z zagadnieniami łańcuchów Markowa z dyskretnym czasem, na przestrzeeniach skończonych.
Pojęcia, techniki:
- procesy Markowa, rozkłady stacjonarne, szybka zbieżność
- coupling, path coupling,
- strong stationary times,
- Hidden Markov Model (Viterbi, Baum-Welch)
- martyngały.
Poruszane zagadnienia:
- kolorowanie grafów (zliczanie kolorowań, samplowanie kolorowań),
- symulowane wyżarzanie,
- analiza anonimowości (transakcje blockchainowe, sieci miksujące),
- bezpieczeństwo generatorów pseudolosowych i szyfrów strumieniowych,
- Risk Limiting Audits,
- Gambler's ruin problem, independent chip model.
