Wykład monograczny dla sekcji teoretyczej i zastosowań studiow matematycznych
udostępniony rownież dla studentow studiow informatycznych.
Podczas wykładu omowione zostaną spacery losowe na skończonych grafach. Dla
szeregu przykładow 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ńcuchow 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 grafow (a nawet bardzo dużych), gdzie ogolne wyniki niewiele mowią.
Poniżej kilka przykładow, ktore 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 obiektow kombinatorycznych, przybliżonego rozwiązywania problemow 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.
