Vi anser att en symmetrisk slumpmässig gång på en ansluten graf, där varje kant är märkt med sannolikheten för övergång mellan de två angränsande hörnen. Den tillhörande Markov-kedjan har en enhetlig jämviktsfördelning; konvergenshastigheten till denna fördelning, dvs. blandningshastigheten i Markov-kedjan, bestäms av övergångsmatrisens näst största (i magnitud). I detta papper tar vi upp problemet med att tilldela sannolikheter till grafens kanter på ett sätt som minimerar den näst största magnituden eigen value, dvs. problemet med att hitta den snabbaste blandning Markov kedjan på grafen. Vi visar att detta problem kan formuleras som ett konvext optimeringsproblem, som i sin tur kan uttryckas som ett semidefinit program (SDP). Detta gör att vi enkelt kan beräkna (globalt) snabbaste blandning Markov kedja för alla grafer med ett blygsamt antal kanter (säg, 1000) med hjälp av standard numeriska metoder för SDPs. Större problem kan lösas genom att utnyttja olika typer av symmetri och struktur i problemet, och mycket större problem (säg 100000 kanter) kan lösas med hjälp av en subgradient metod som vi beskriver. Vi jämför den snabbaste blandning Markov kedjan med de som erhållits med hjälp av två vanliga heuristik: den maximala graden metod, och Metropolis-Hastings algoritm. För många av de aktuella exemplen är den snabbaste blandningen av Markov-kedjan betydligt snabbare än de som erhålls med hjälp av dessa heuristiska metoder. Vi härleder Lagrange dubbla av den snabbaste blandning Markov kedjeproblem, vilket ger en sofistikerad metod för att erhålla (arbiträrt bra) gränser på den optimala blandningshastigheten, samt optimala förhållanden. Slutligen beskriver vi olika förlängningar av metoden, inklusive en lösning på problemet med att hitta den snabbaste blandning reversibla Markov kedjan, på en fast graf, med en given jämviktsfördelning.
Således kan den snabbaste blandning Markov Chain erhållas genom att minimera SLEM REF.
Fastest Mixing Markov Chain on A Graph
{'venue': 'SIAM REVIEW', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}