Vi ger en systematisk utveckling av tillämpningen av matrisnormer för snabb blandning i spinnsystem. Vi visar att snabb blandning av både slumpmässig uppdatering Glauber dynamik och systematisk scan Glauber dynamik uppstår om någon matris norm av den associerade beroendematrisen är mindre än 1. Vi ger förbättrad analys för det fall där diagonalen i beroendematrisen är 0 (som i värmebad dynamik). Vi tillämpar matrisnorm metoder för slumpmässig uppdatering och systematisk scan Glauber dynamik för färgning olika klasser av grafer. Vi ger en allmän metod för att uppskatta en norm av en symmetrisk icke-regelbunden matris. Detta leder till förbättrade blandningstider för alla klasser av grafer som är ärftliga och tillräckligt glesa, inklusive flera klasser av gradbundna grafer såsom icke-regelbundna grafer, träd, plana grafer och grafer med given trädbredd och släkte. 1. Vad är det för fel på dig? Inledning. Ett spinnsystem består av en ändlig uppsättning platser och en ändlig uppsättning spins. En konfiguration är en tilldelning av en spin till varje plats. Webbplatser interagerar lokalt, och dessa interaktioner anger den relativa sannolikheten för möjliga (lokala) underkonfigureringar. Tillsammans ger dessa en väldefinierad sannolikhetsfördelning π på uppsättningen konfigurationer. Glauber dynamik är en Markov kedja vars tillstånd är konfigurationer. I övergångarna i Markov-kedjan uppdateras snurren en i taget. Markovkedjan konvergerar till den stationära distributionen π. Under varje övergång av slumpmässig uppdatering Glauber dynamik, en plats väljs enhetligt på måfå och en ny spinn väljs från en lämplig sannolikhetsfördelning (baserat på den lokala subkonfigurationen runt den valda platsen). Under en övergång av systematisk skanning Glauber dynamik, platserna uppdateras i en (deterministisk) systematisk ordning, en efter en. Återigen, uppdateringarna är från en lämplig sannolikhetsfördelning baserat på den lokala underkonfigurationen.
Den senaste tekniken för allmänna spinnsystem beror på Dyer, Goldberg och Jerrum REF, som bevisar att någon systematisk scan Glauber dynamik (på någon graf) har O(log n) blandningstid förutsatt någon matris norm av beroendematrisen i spinnsystemet begränsas bort från 1.
Matrix norms and rapid mixing for spin systems
{'venue': 'Annals of Applied Probability 2009, Vol. 19, No. 1, 71-107', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}