Fastest mixing Markov chain problem for the union of two cliques

Abstract

A symmetric, random walk on a graph G can be defined by prescribing weights to the edges in such a way that for each vertex the sum of the weights of the edges incident to the vertex is at most one. The fastest mixing, Markov chain (FMMC) problem for G is to determine the weighting that yields the fastest mixing random walk. We solve the FMMC problem in the case that G is the union of two complete graphs.

Keywords:

• fastest mixing
• Markov chain
• subdominant eigenvalues
• second largest eigenvalue modulus
• random walk

AMS Subject Classifications:

• 05C50
• 15A03

Acknowledgements

The authors thank the referee for thoughtful comments and suggestions that improved this article exposition.

Notes

1. This remark also follows from extending the definition of u and v to allow real values and noting that ρ₂ is continuous on Mark(G).