**Tuesday, 13:45 - 14:10 h, Room: H 3021**

**Sarah Miracle**

Mixing times of self-organizing lists and biased permutations

**Coauthors: Prateek Bhakta, Dana Randall, Amanda P. Streib**

**Abstract:**

Sampling permutations from *S*_{n} is a fundamental problem from probability theory. The nearest neighbor transposition chain is known to mix in time *Θ(n*^{3} *log* n) in the unbiased case and time *Θ(n*^{2}) in the constant bias case. It was conjectured that the chain is always rapidly mixing when the inversion probabilities are positively biased, i.e., we put nearest neighbor pair *x** in order with bias **1/2 ≤ p*_{xy} ≤ 1 and out of order with bias *1-p*_{xy}. We prove the chain is rapidly mixing for two classes: "Choose Your Weapon,'' where we are given *r*_{1}, … , r_{n-1} with *r*_{i} ≥ 1/2 and *p*_{x,y}=r_{x} for all *x** (the dominant player chooses the game, thus fixing their probability of winning), and "League hierarchies,'' where there are two leagues and players from the A-league have a fixed probability of beating players from the B-league, players within each league are divided into sub-leagues, and so forth recursively. Moreover, we also prove that the conjecture is false by exhibiting values for the **p*_{xy}, with *1/2 ≤ p*_{xy} ≤ 1 for all *x**, but for which the chain will require exponential time to converge. *

* *

*
*Talk 2 of the invited session Tue.2.H 3021

**"Sampling, sorting and graph traversal: Algorithms for finding permutations"** [...]

Cluster 2

**"Combinatorial optimization"** [...]