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


Sampling permutations from Sn is a fundamental problem from probability theory. The nearest neighbor transposition chain is known to mix in time Θ(n3 log n) in the unbiased case and time Θ(n2) 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 ≤ pxy ≤ 1 and out of order with bias 1-pxy. We prove the chain is rapidly mixing for two classes: "Choose Your Weapon,'' where we are given r1, … , rn-1 with ri ≥ 1/2 and px,y=rx 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 pxy, with 1/2 ≤ pxy ≤ 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" [...]


  Payday Loans In Ohio. The main advantage of Viagra Soft Tablets comparing with other products of this type is its faster on-set effect.