Markov-kedjor och blandningstider
Markov Chains and Mixing Times är en bok om Markov-kedjors blandningstider . Den andra upplagan skrevs av David A. Levin och Yuval Peres . Elizabeth Wilmer var medförfattare på den första upplagan och är krediterad som bidragsgivare till den andra upplagan. Den första upplagan publicerades 2009 av American Mathematical Society , med en utökad andra upplaga 2017.
Bakgrund
En Markov-kedja är en stokastisk process som definieras av en uppsättning tillstånd och, för varje tillstånd, en sannolikhetsfördelning på tillstånden. Utgående från ett initialt tillstånd följer det en sekvens av tillstånd där varje tillstånd i sekvensen väljs slumpmässigt från fördelningen som är associerad med det föregående tillståndet. I den meningen är den "minneslös": varje slumpmässigt val beror bara på det nuvarande tillståndet och inte på staternas tidigare historia. Under milda restriktioner kommer en Markov-kedja med en ändlig uppsättning tillstånd att ha en stationär fördelning som den konvergerar till, vilket innebär att, efter ett tillräckligt stort antal steg, sannolikheten att vara i varje tillstånd kommer att nära den för den stationära fördelningen, oberoende av initialtillståndet eller det exakta antalet steg. Blandningstiden för en Markov-kedja är antalet steg som krävs för att denna konvergens ska ske, med en lämplig grad av noggrannhet . En familj av Markov-kedjor sägs blandas snabbt om blandningstiden är en polynomfunktion av någon storleksparameter av Markovkedjan, och blandas långsamt annars. Den här boken handlar om ändliga Markov-kedjor, deras stationära distributioner och blandningstider, och metoder för att avgöra om Markov-kedjor snabbt eller långsamt blandas.
Ett klassiskt och välbekant exempel på detta fenomen involverar att blanda kortlekar: utgående från en icke-slumpmässig initial kortlek, hur många blandningar krävs för att nå en nästan slumpmässig permutation ? Detta kan modelleras som en Markov-kedja vars tillstånd är beställningar av kortleken och vars sannolikheter för övergång från tillstånd till stat ges av någon matematisk modell av slumpmässig blandning som Gilbert-Shannon-Reeds- modellen . I denna situation innebär snabb blandning av Markov-kedjan att man inte behöver utföra ett stort antal blandningar för att nå ett tillräckligt randomiserat tillstånd. Utöver kortspel uppstår liknande överväganden i beteendet hos de fysiska systemen som studeras inom statistisk mekanik , och för vissa randomiserade algoritmer .
Ämnen
Boken är uppdelad i två delar, den första mer inledande och den andra mer avancerad. Efter tre kapitel med introduktionsmaterial om Markov-kedjor, definierar kapitel fyra sätten att mäta avståndet för en Markov-kedja till dess stationära distribution och den tid det tar att nå det avståndet. Kapitel fem beskriver koppling , en av standardteknikerna för att begränsa blandningstider. I den här tekniken sätter man upp två Markov-kedjor, en med start från det givna initiala tillståndet och den andra från den stationära fördelningen, med övergångar som har rätt sannolikheter inom varje kedja men inte är oberoende av kedja-till-kedja, i en sådan sätt att de två kedjorna sannolikt kommer att flytta till samma tillstånd som varandra. På detta sätt kan blandningstiden begränsas av tiden för de två kopplade kedjorna att synkronisera. Kapitel sex diskuterar en teknik som kallas "starka stationära tider" med vilken man för vissa Markov-kedjor kan bevisa att ett slumpmässigt val av en stopptid från en viss fördelning kommer att resultera i ett tillstånd som hämtas från den stationära fördelningen.
Efter ett kapitel om nedre gränser för blandningstid baserat på "flaskhalsförhållandet" och isoperimetriskt tal , täcker de nästa två kapitlen i den första delen två viktiga exempel: kortblandning och slumpmässiga vandringar på grafer . Kapitel 10 och 11 behandlar ytterligare två parametrar som är nära relaterade till blandningstiden, träfftiden vid vilken Markov-kedjan först når ett specificerat tillstånd, och täckningstiden vid vilken den först har nått alla tillstånd. De diskuterar också tidsreversibla Markov-kedjor och deras koppling till elektriska nätverk. Det sista kapitlet i denna del diskuterar sambandet mellan spektralgapet i en Markov-kedja och dess blandningstid.
Den andra delen av boken innehåller många fler exempel där denna teori har tillämpats, inklusive Glauber-dynamiken på Ising-modellen , Markov-modeller för kromosomomarrangemang , den asymmetriska enkla uteslutningsprocessen där partiklar slumpmässigt hoppar till obemannade intilliggande utrymmen och slumpmässigt går i lamptändargruppen . Ämnen som tas upp i den andra delen av boken inkluderar mer om spektralgrafer och expandergrafer , vägkoppling (där en sekvens av mer än två Markov-kedjor kopplas i par), kopplingar mellan koppling och jordflyttarens avstånd , martingaler , kritiska temperaturer , "cutoff-effekten" där sannolikhetsfördelningen av kedjan snabbt övergår mellan oblandad och blandad, den utvecklande mängdprocessen (en härledd Markov-kedja på uppsättningar av tillstånd i den givna kedjan), Markov-kedjor med oändligt många tillstånd och Markov-kedjor som arbetar i kontinuerlig tid snarare än genom en diskret sekvens av steg. Ett gästkapitel av Jim Propp och David B. Wilson beskriver koppling från det förflutna , en metod för att erhålla prover dragna exakt från den stationära distributionen snarare än (som man får från Markov-kedjans Monte Carlo- metoder) approximationer till denna distribution. Det sista kapitlet samlar öppna problem inom detta område.
Publik och mottagning
Den här boken kan användas antingen som referens av forskare inom områden som använder dessa metoder, eller som grund för en kurs på forskarnivå, särskilt en begränsad till det mer introduktionsmaterial i bokens första del där endast kunskaper på grundnivå av sannolikhetsteori och linjär algebra krävs. Recensenten Rick Durrett menar dock att bokens innehåll skulle vara för avancerat för grundkurser, även vid universitet på forskningsnivå, och recensenten Takis Konstantopoulos föreslår att bokens innehåll skulle uppskattas bättre av en läsare som redan har fått en viss exponering för materialet. att den täcker.
Recensenten Olle Häggström kallar boken "auktoritativ och mycket läsvärd". Recensenten HM Mai skriver att dess förklaringar är noggranna och "välmotiverade", och att skriften är "klar och tydlig". Recensenten László Lakatos kallar det "en lysande guide till den moderna teorin om Markov-kedjor". Och recensenten David Aldous förutspår att det "länge kommer att förbli den definitiva läsningen" på detta område.