Łańcuchy Markowa i czasy mieszania
Łańcuchy Markowa i czasy mieszania to książka o czasach mieszania łańcuchów Markowa . Drugie wydanie zostało napisane przez Davida A. Levina i Yuvala Peresa . Elizabeth Wilmer była współautorką pierwszego wydania i jest uznawana za współautorkę drugiego wydania. Pierwsza edycja została opublikowana w 2009 roku przez American Mathematical Society , z rozszerzoną drugą edycją w 2017 roku.
Tło
Łańcuch Markowa to proces stochastyczny zdefiniowany przez zbiór stanów i dla każdego stanu rozkład prawdopodobieństwa stanów. Zaczynając od stanu początkowego, następuje sekwencja stanów, w której każdy stan w sekwencji jest wybierany losowo z rozkładu związanego ze stanem poprzednim. W tym sensie jest „bez pamięci”: każdy przypadkowy wybór zależy tylko od aktualnego stanu, a nie od przeszłej historii stanów. Przy łagodnych ograniczeniach łańcuch Markowa ze skończonym zbiorem stanów będzie miał rozkład stacjonarny do którego się zbiega, co oznacza, że po wystarczająco dużej liczbie kroków prawdopodobieństwo znalezienia się w każdym stanie będzie zbliżone do prawdopodobieństwa rozkładu stacjonarnego, niezależnie od stanu początkowego lub dokładnej liczby kroków. Czas mieszania łańcucha Markowa to liczba kroków potrzebnych do zajścia tej zbieżności z odpowiednim stopniem dokładności. Mówi się, że rodzina łańcuchów Markowa szybko się miesza , jeśli czas mieszania jest funkcją wielomianową pewnego parametru wielkości łańcucha Markowa, a wolno się miesza W przeciwnym razie. Ta książka dotyczy skończonych łańcuchów Markowa, ich stacjonarnych rozkładów i czasów mieszania oraz metod określania, czy łańcuchy Markowa mieszają się szybko, czy wolno.
Klasycznym i znanym przykładem tego zjawiska jest tasowanie talii kart: zaczynając od nielosowej początkowej talii kart, ile tasowań potrzeba, aby osiągnąć prawie losową permutację ? Można to modelować jako łańcuch Markowa, którego stany są uporządkowaniem talii kart i którego prawdopodobieństwa przejścia między stanami są określone przez pewien matematyczny model losowego tasowania, taki jak model Gilberta – Shannona – Reedsa . W tej sytuacji szybkie mieszanie łańcucha Markowa oznacza, że nie trzeba wykonywać ogromnej liczby przetasowań, aby osiągnąć stan wystarczająco losowy. Poza grami karcianymi podobne rozważania pojawiają się w zachowaniu badanych układów fizycznych mechaniki statystycznej i niektórych losowych algorytmów .
Tematy
Książka jest podzielona na dwie części, pierwszą bardziej wprowadzającą i drugą bardziej zaawansowaną. Po trzech rozdziałach materiału wprowadzającego do łańcuchów Markowa, rozdział czwarty definiuje sposoby mierzenia odległości łańcucha Markowa od jego rozkładu stacjonarnego oraz czasu potrzebnego do osiągnięcia tej odległości. Rozdział piąty opisuje sprzęganie , jedną ze standardowych technik ograniczania czasów mieszania. W tej technice tworzy się dwa łańcuchy Markowa, jeden wychodzący z danego stanu początkowego, a drugi z rozkładu stacjonarnego, z przejściami, które mają odpowiednie prawdopodobieństwa w każdym łańcuchu, ale nie są niezależne od łańcucha do łańcucha, w taki sposób, w jaki oba łańcuchy prawdopodobnie przejdą do tych samych stanów, co inne. W ten sposób czas mieszania może być ograniczony czasem synchronizacji dwóch połączonych łańcuchów. W rozdziale szóstym omówiono technikę zwaną „silnymi czasami stacjonarnymi”, za pomocą której w przypadku niektórych łańcuchów Markowa można udowodnić, że losowy wybór czasu zatrzymania z określonego rozkładu da w rezultacie stan wyciągnięty z rozkładu stacjonarnego.
Po rozdziale poświęconym dolnym granicom czasu mieszania w oparciu o „stosunek wąskich gardeł” i liczbę izoperymetryczną , kolejne dwa rozdziały pierwszej części omawiają dwa ważne przykłady: tasowanie kart i błądzenie losowe po wykresach . Rozdziały 10 i 11 omawiają jeszcze dwa parametry ściśle związane z czasem mieszania, czasem uderzenia w którym łańcuch Markowa po raz pierwszy osiąga określony stan, oraz czas pokrycia, w którym po raz pierwszy osiągnął wszystkie stany. Omawiają również odwracalne w czasie łańcuchy Markowa i ich połączenia z sieciami elektrycznymi. Ostatni rozdział tej części omawia związek między przerwą widmową łańcucha Markowa a czasem jego mieszania.
Druga część książki zawiera wiele innych przykładów zastosowania tej teorii, w tym dynamikę Glaubera na modelu Isinga , modele przegrupowań chromosomów Markowa , proces asymetrycznego prostego wykluczenia, w którym cząstki losowo przeskakują do niezajętych sąsiednich przestrzeni oraz przypadkowe chodzi w grupie latarników . Tematy omówione w drugiej części książki obejmują więcej grafów widmowych i grafów ekspandera , sprzężenie ścieżek (w którym sekwencja więcej niż dwóch łańcuchów Markowa jest połączona parami), połączenia między sprzężeniem a odległością poruszającego się ziemi , martyngały , temperatury krytyczne , „efekt odcięcia”, w którym rozkład prawdopodobieństwa łańcucha przechodzi szybko między niezmieszane i mieszane, ewoluujący proces zbioru (pochodny łańcuch Markowa na zbiorach stanów danego łańcucha), łańcuchy Markowa z nieskończenie wieloma stanami oraz łańcuchy Markowa, które działają w czasie ciągłym, a nie w dyskretnej sekwencji kroków. Rozdział gościnny autorstwa Jima Proppa a David B. Wilson opisuje sprzężenie z przeszłości , metodę uzyskiwania próbek pobranych dokładnie z rozkładu stacjonarnego, a nie (jak uzyskuje się z metod Monte Carlo łańcucha Markowa ) przybliżeń do tego rozkładu. W ostatnim rozdziale zebrano otwarte problemy w tej dziedzinie.
Publiczność i odbiór
Ta książka może być wykorzystana albo jako źródło informacji przez naukowców zajmujących się dziedzinami wykorzystującymi te metody, albo jako podstawa kursu na poziomie magisterskim, w szczególności takiego, który ogranicza się do bardziej wprowadzającego materiału w pierwszej części książki, gdzie wiedza na poziomie licencjackim Wymagana jest znajomość teorii prawdopodobieństwa i algebry liniowej . Jednak recenzent Rick Durrett sugeruje, że treść książki byłaby zbyt zaawansowana na studia licencjackie, nawet na uniwersytetach badawczych, a recenzent Takis Konstantopoulos sugeruje, że treść książki byłaby lepiej doceniona przez czytelnika, który miał już pewien kontakt z materiałem, który obejmuje.
Recenzent Olle Häggström nazywa książkę „autorytatywną i bardzo czytelną”. Recenzent HM Mai pisze, że jego wyjaśnienia są ostrożne i „dobrze umotywowane”, a pismo jest „przejrzyste i jasne”. Recenzent László Lakatos nazywa to „genialnym przewodnikiem po współczesnej teorii łańcuchów Markowa”. A recenzent David Aldous przewiduje, że „na długo pozostanie ostateczną lekturą obowiązkową” w tej dziedzinie.