Disclaimer: Denna opublicerade enkät skrevs år 2000, och publiceras oredigerad i sin ursprungliga form, som svar på förfrågningar om en permanent URL som kan citeras. Det är alltså föråldrat och speglar inte den senaste tekniken 2016. Sammanfattning För många grundläggande provtagningsproblem är det bästa, och ofta det enda kända, sättet att lösa dem att ta en tillräckligt lång slumpmässig promenad på en viss Markovkedja och sedan återlämna det nuvarande tillståndet i kedjan. Tekniker för att bevisa hur lång "lång" är, dvs. antalet steg i kedjan man måste ta för att vara tillräckligt nära den stationära fördelningen av kedjan, är av stor betydelse för att få uppskattningar av drifttider för sådana provtagningsalgoritmer. I denna rapport undersöker vi befintliga tekniker för att begränsa blandningstiden för Markovkedjor. Blandningstiden för en Markov-kedja fångas exakt av "spektralt gap" av dess underliggande övergångsmatris. Den spektralgap är nära besläktad med en geometrisk parameter kallad "ledning" som är ett mått på markovkedjans "kantexpansion". Konduktivitet fångar också blandningstiden upp till kvadratfaktorer. Nedre gränser för ledning, som ger övre gränser på blandningstiden, erhålls vanligtvis genom en teknik som kallas "kanoniska stigar" där tanken är att hitta en uppsättning stigar, en mellan varje ojämlik källdestination par, så att ingen kant är mycket hårt överbelastad. Till skillnad från ledande, kan de kanoniska vägar närma sig inte alltid visa snabb blandning av en snabb blandning kedja. Det är känt att denna "drawback" försvinner om vi tillåter flödet mellan ett par stater att spridas längs flera vägar. Vi bevisar att för en stor klass av Markov-kedjor, inklusive alla de som vi använder i de provtagningsapplikationer vi kommer att vara intresserade av, kanoniska vägar fånga snabb blandning, dvs. vi visar att liten blandningstid innebär förekomsten av vissa samling av stigar med låg kant trängsel. Att tillåta flera vägar att styra flödet hjälper fortfarande en hel del i utformningen av sådana flöden, och detta illustreras bäst av ett nyligen resultat av Morris och Sinclair [34] om snabb blandning av en naturlig Markov kedja för provtagning 0-1 knapsack lösningar; detta resultat verkar vara kritiskt beroende av fraktionerade flöden. Ett helt annat tillvägagångssätt för att bevisa snabb blandning, som i själva verket historiskt föregick den ledande/kanoniska metoden, är "koppling". Koppling är en mycket elegant teknik och har använts för att bevisa snabb blandning av flera kedjor där design av bra kanoniska vägar verkar vara en hemsk uppgift. "Path Coupling" är en relaterad teknik upptäckt av Bubley and Dyer [5] som ofta oerhört minskar komplexiteten i att utforma goda kopplingar. Vi presenterar flera tillämpningar av Path Coupling i bevis på snabb blandning, och dessa leder alltid till mycket bättre gränser för blandningstid än känt med ledning, och dessutom Coupling baserade bevis brukar visa sig vara mycket enklare. Dessa tillämpningar motiverar frågan om huruvida Coupling verkligen kan göras att fungera när kedjan snabbt blandas. Denna fråga besvarades i det negativa i det mycket senaste arbetet av Kumar och Ramesh [27], som visade att ingen Coupling-strategi kan bevisa en snabb blandning av den berömda Jerrum-Sinclair-kedjan för provtagning av perfekta och nästan perfekta matchningar (kedjan är känd för att snabbt blandas via en kanonisk väg argument). * Datavetenskap Institutionen, Carnegie Mellon University, Pittsburgh, PA. guruswami@cmu.edu. Enkät skriven 2000 när författaren var student vid MIT. Antag att är en stor ändlig uppsättning av kombinatoriska strukturer (till exempel uppsättningen av genomförbara lösningar till en combinatorial optimering problem), och låt π vara en sannolikhetsfördelning på  och. Det allmänna "sampling" problemet är då att välja ett element av  på måfå enligt fördelningen π. Markovkedjan Monte Carlo-metoden, som är föremål för vår studie här, ger en elegant teknik för att effektivt lösa denna allmänna beräkningsuppgift i en mängd olika sammanhang. Provtagningsproblem är i sig intressanta, och dessutom visar sig ha många beräkningsapplikationer, de mest anmärkningsvärda är: • Ungefärlig beräkning: Här vill vi uppskatta storleken på  på en mycket god noggrannhet. Det är välkänt [23] att det, under förutsättning att ett visst tekniskt tillstånd som kallas självreducerbarhet är uppfyllt, är möjligt med nästan enhetlig provtagning (dvs. provtagning från en fördelning som ligger statistiskt nära den enhetliga fördelningen) i polynomtid om och endast om ungefärlig beräkning är möjlig. Detta har varit en av de främsta motiven, åtminstone ur datavetenskaplig synvinkel, bakom de snabba framsteg som har gjorts på detta område. Särskilt för en mängd räkna problem inklusive flera mycket svåra #P-fullständiga problem, Markov kedjan Monte Carlo metod är den enda kända metoden för att uppskatta antalet genomförbara lösningar. • Statistisk fysik: Här kommer utrymmet att representera möjliga konfigurationer av det statistiska mekaniska systemet, och π är en "naturlig" sannolikhetsfördelning på  och där sannolikheten för en konfiguration är relaterad till dess energi. Uppgiften är att ta prov konfigurationer enligt π, för att undersöka egenskaper hos en "typisk" fysisk konfiguration. I denna rapport fokuserar vi bara på provtagningsproblemet och utelämnar kopplingarna till att räkna eftersom dessa vid det här laget innebär standardminskningar. Markovkedjan Monte Carlo-metoden har varit en stor framgångssaga när det gäller att lösa provtagningsproblem. Det löser provtagningsproblemet genom följande metod. En underliggande "Markov-kedja" M på statsrymden  ska anges genom en stokastisk övergångssannolikhetsmatris av dimension  för x x x y) th post anger sannolikheten P(x, y) att kedjan rör sig från stat x för att ange y i ett enda steg (vi antar att tillstånd av M är märkta med element av  ska). Börjar vid alla tillstånd x 0, Det finns en naturlig slumpmässig gång X 0 = x 0, X 1, X 2,. .. definieras på M sådan att Pr[X t+1  till X 0,. .., X t ] = Pr[X t+1  på X t ] där den senare villkorade sannolikheten anges av matrisen P, dvs. Pr[X t+1 = y på X t = x] = P(x, y). Med andra ord börjar vi vid tillstånd X 0 och vid varje tidpunkt steg t, vi gör en övergång till ett nästa tillstånd X t+1 genom att flytta till ett slumpmässigt tillstånd från det nuvarande tillstånd X t enligt övergångssannolikheterna i kedjan. Lägg märke till Markovkedjornas avgörande "glömma egendom": tillståndet vid tidpunkten t + 1 beror probabilistiskt på tillståndet vid tidpunkten t, men inte på staten vid något annat tillfälle. För att ta prov enligt en distribution π definieras Markov-kedjan M på ett sådant sätt att den är ergodisk, d.v.s. har en (unik) stationär fördelning η på  och så att Pr[X t = y tillX 0 = x] → η(y) som t → ❌, för alla par av stater x, y  och dessutom är övergångssannolikheterna uppsatta så att η = π. Nu kan vi ta prov från  ska enligt π enligt följande: från ett godtyckligt tillstånd i  ska, ta en slumpmässig promenad på Markov kedjan (som vi löst kommer att hänvisa till som "simulering av Markov kedjan" i uppföljaren) för ett visst antal, T, av steg, och sedan utdata det slutliga tillståndet. M:s ergodicitet innebär att vi genom att ta T tillräckligt stort kan se till att utgångstillståndet är godtyckligt nära den önskade distributionen π. En av de mest tilltalande sakerna med denna metod är dess enkelhet - i själva verket i de flesta tillämpningar är det inte svårt att bygga en Markov kedja med ovanstående egenskaper. Metodens crux, som också är dess klibbpunkt, är att få bra övre gränser på blandningstiden för kedjan, dvs. antalet simuleringssteg T som krävs innan Markovkedjan är nära sin stationära fördelning. Denna 2 är kritisk eftersom detta utgör den avgörande faktorn i körtiden för varje provtagningsalgoritm som använder kedjan. Eftersom vårt mål är att prov från en uppsättning som är mycket stor, skulle vi vilja att T att vara mycket mindre än storleken på  på, säga som mest ett polynom i logaritmen av  på. Vi kommer att hänvisa till sådana kedjor som snabb blandning. Under årens lopp har flera djupa och nya analytiska verktyg utvecklats och förfinats till bundna blandningstider för Markovkedjor. Syftet med denna rapport är att kartlägga kända tekniker för att bevisa snabb blandning, att presentera representativa exempel på deras användning och att jämföra och jämföra deras omfattning, deras relativa styrkor och begränsningar samt deras tillämplighet i olika sammanhang. Organisering. Vi börjar i nästa avsnitt genom att granska relevanta definitioner och egenskaper hos Markovkedjor, och genom att ge en exakt karakterisering av när en Markovkedja snabbt blandas i termer av sina spektralegenskaper. I avsnitt 3 diskuterar vi begreppet ledning och dess förhållande till spektralgapet i kedjan. Avsnitt 4 diskuterar den kanoniska vägen tillvägagångssätt och några av dess generaliseringar som ger gränser på ledning och spektral gap, och visar också att för en stor klass av kedjor en liten blandningstid innebär förekomsten av en viss samling goda kanoniska vägar. Vi presenterar sedan en illustrativ tillämpning av denna teknik på problemet med provtagning 0-1 knapsack lösningar i Avsnitt 5. I avsnitt 6 diskuteras Coupling som är ett helt annat sätt att begränsa blandningstiden, ger ett belysande exempel på Coupling i handling, och även diskuterar Path Coupling, som är ett användbart designverktyg vid konstruktion av Couplings. Flera eleganta tillämpningar av Path Coupling presenteras i Avsnitt 7. I avsnitt 8 diskuterar vi det senaste resultatet av [27] som visar att kopplingen i själva verket är svagare än konduktansen, eftersom det finns kedjor med stor konduktans som inte kan visas vara snabb blandning genom någon Coupling-strategi. Slutligen avslutar vi med några kommentarer och öppna frågor i avsnitt 9. Erkännanden. Denna undersökning skrevs som en del av författarens Area Examination vid MIT, vars mål var att kartlägga tidningarna av Bubley och Dyer [5], Anil Kumar och Ramesh [27], och Morris och Sinclair [34]. I denna undersökning (särskilt avsnitten 5, 6.4, 7.1 och 8) används liberala delar av innehållet i dessa dokument. Detta arbete påverkades också i hög grad av Jerrums [19] läsning av undersökningen och Sinclairs [37], bland flera andra tidningar. Jag vill tacka Kumar och Ramesh för att ha skickat mig en kopia av den senaste versionen av deras papper [27]. En Markov-kedja på tillståndsrymden är helt specificerad av övergångsmatrisen P vars ingång P(x, y) representerar sannolikheten för att kedjan rör sig från tillstånd x till tillstånd y är en enda övergång, dvs. P(x, y) = Pr[X t+1 = y]X t = x] för alla t ≥ 0. Således för att studera och analysera egenskaperna hos Markov kedjan, räcker det att undersöka egenskaperna hos denna matris P. Med början från en initial distribution μ (0), fördelningen av kedjan efter t steg μ (t) tydligt ges av μ (t) = μ (0) P n (här ser vi distributionerna som radvektorer i R ). Således, när man använder en Markov kedja för att slumpmässigt prov från dess tillstånd utrymme, måste vi studera utvecklingen av μ (t) som t ökar, och vi skulle vilja μ (t) att (snabbt) närma sig en begränsande stationär distribution, säger π; det är inte förvånande att π måste fastställas under steg i kedjan. Definition 2.1 En radvektor π  på R är en stationär fördelning för en Markov-kedja M med övergångsmatris P om a) π(x) ≥ 0 för alla x  en, b)..x.. π(x) = 1, och c) π = πP.
En omfattande undersökning av tekniker för att begränsa blandningstiden för en Markov Chain är REF.
Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}