Abstrakt. Vi anser att en Markov process på en ansluten graf, med kanter märkta med övergångshastigheter mellan intilliggande hörn. Fördelningen av Markovprocessen konvergerar till den enhetliga fördelningen med en hastighet som bestäms av det näst minsta eigenvärdet λ 2 i Laplacian i den viktade grafen. I detta dokument anser vi att problemet med att tilldela kanterna övergångssatser för att maximera λ 2 under en linjär begränsning av skattesatserna. Detta är problemet med att hitta den snabbaste blandning Markov processen (FMMP) på grafen. Vi visar att FMMP-problemet är ett konvext optimeringsproblem, som i sin tur kan uttryckas som ett semidefinitprogram, och därför effektivt lösas numeriskt. Vi formulerar en dubbel av FMMP problem och visar att det har en naturlig geometrisk tolkning som en maximal varians veckling (MVU) problem, dvs. problemet med att välja en uppsättning punkter att vara så långt ifrån varandra som möjligt, mätt med deras varians, samtidigt som lokala avstånd begränsningar. Detta MVU-problem är nära relaterat till ett problem som nyligen föreslagits av Weinberger och Saul som en metod för att "undvika" högdimensionella data som ligger på ett lågdimensionellt grenrör. Dualiteten mellan FMMP- och MVU-problemen kastar ljus över båda problemen och gör att vi kan karakterisera och i vissa fall hitta optimala lösningar.
Dessutom, graden av konvergens av en Markov process på en graf till den enhetliga fördelningen bestäms av algebraic konnektivitet REF.
The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem
{'venue': 'SIAM REVIEW', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}