Wykład monograczny dla sekcji teoretyczej i zastosowań studiów matematycznych
udostępniony również dla studentów studiów informatycznych.
Podczas wykładu omówione zostaną spacery losowe na skończonych grafach. Dla
szeregu przykładów będziemy chcieli odpowiedzieć na pytanie: po jakim czasie
możemy uznać, że spacer losowy nie zależy od punktu startu. Pierwsze wykłady
będą poświęcone elementom łańcuchów Markowa. Dość szybko pokażemy zasadniczy
wynik, że rozkład takiego spaceru zbiega do miary stacjonarnej i tempo
zbieżności jest wykładnicze. Najciekawsze będą jednak konkretne przykłady
dużych grafów (a nawet bardzo dużych), gdzie ogólne wyniki niewiele mówią.
Poniżej kilka przykładów, które pojawią się podczas wykładu:
* Problem tasowania kart.
* MCMC (Markov Chain Monte Carlo), algorytm Metropolis i ich zastosowania w informatyce np. do przybliżonego zliczania obiektów kombinatorycznych, przybliżonego rozwiązywania problemów optymalizacyjnych (komiwojażera, plecakowego).
* Ekspandery i ich zastosowania.
#### Literatura:
* P. Diaconis.Group Representations in Probability and Statistics.
* O. Haggstrom. Finite Markov Chains and Algorithmic Applications.
* D. Levin, Y. Peres, E. Wilmer. Markov Chains and Mixing Times.
