Mixing of Permutations by Biased Transposition

Shahrzad Haddadan, Peter Winkler

Introduction

The study of Markov chains on permutations is a cornerstone of theoretical computer science, with applications ranging from search engine ranking algorithms to the modeling of self-organizing lists. A fundamental question in this field is the "mixing time"—the time required for a system to reach its stationary distribution. While "simple" adjacent transposition chains (where all items have equal weight) are well-understood, "biased" versions, such as the Gladiator Chain, present significant analytical challenges. In the Gladiator Chain, items (gladiators) have varying strengths, and adjacent items swap positions based on a probability proportional to their relative strengths: $s_g / (s_g + s_{g'})$.

Methodology: The Particle Bridge

The authors address the complexity of the Gladiator Chain by employing a "divide and conquer" strategy. A central innovation is the Particle Bridge, which formally links a system of $n$ unique items to a simpler system of $k$ types of indistinguishable particles. By proving that the mixing time of the unique gladiator system is bounded by $O(n^8)$ times the mixing time of the particle system, the researchers can focus on a significantly smaller state space.

The analysis further decomposes the process into "Whisking" (swapping items of identical strength) and "Sifting" (swapping items of different strengths). This allows for the application of the Comparison Method and the Canonical Paths technique.

Canonical Paths and Geometric Bounds

To bound the mixing time of the particle system, the authors utilize the Canonical Paths technique. This method involves defining specific "routes" between any two possible arrangements of particles and ensuring that no single transition (or "road") becomes overly congested.

Figure 1: Geometric representation of canonical paths between particle configurations in a multi-type system.

As shown in Figure 1, these paths can be visualized as trajectories through a high-dimensional lattice representing the state space. By using $q$-binomial coefficients to provide precise mathematical bounds on the "congestion" of these paths, the authors establish a polynomial time limit for the system's convergence. The introduction of a third particle type significantly increases complexity, requiring the definition of specific "Jump" and "Hop" moves to maintain efficient paths.

Key Results and Implications

The paper provides the first polynomial-time mixing bound for the Gladiator Chain with three distinct strength classes, providing strong evidence for Fill’s Conjecture (2003). Key findings include:

  • Three-Type Particle Mixing: Linear particle systems with three types (A, B, and C) mix in $O(n^{10})$ time, assuming a sufficient strength gap ($s_A/s_B < 1/2$ and $s_B/s_C < 1/2$).
  • Gladiator Chain Bound: The full gladiator chain with three teams is shown to mix in $O(n^{18})$ time.
  • Hierarchical Extensions: The results extend to ternary tree hierarchies, achieving a mixing bound of $O(n^{14} \log n)$.

Conclusion

While the current proof is limited to a constant number of strength classes and specific strength ratios, it provides the theoretical framework necessary to eventually tackle the general case of an arbitrary number of unique strengths. The $n^{18}$ exponent suggests that while the chain is "rapidly mixing" in a theoretical sense, more efficient paths or different proof techniques may be needed to reach a tight general bound for practical applications.

Summary updated

BibTeX
@inproceedings{haddadan2017mixing,
  author = {Shahrzad Haddadan and Peter Winkler},
  title = {{Mixing of Permutations by Biased Transposition}},
  booktitle = {STACS},
  year = {2017},
  doi = {10.4230/lipics.stacs.2017.41},
}
Figure