Dr. Miracle Presents Research at Dagstuhl Computational Seminar

September 25, 2017 / By: UST CISC Department

CISC Assistant Professor Sarah Miracle recently gave a talk at the Dagstuhl Computational Counting Seminar in Wadern, Germany. Founded in 1990, Schloss Dagstuhl quickly became established as one of the world’s premier meeting centers for informatics research. Attended by nearly 45,000 national and international researchers over the past 25 years, the seminar and workshop series aim to promote application-oriented research, support advanced vocational training, and facilitate the transfer of knowledge between researchers in the field of informatics. The full title and abstract are below.

 

Title:

Mixing Times of Markov Chains for Self-Organizing Lists and Biased Permutations

Abstract:

In this talk I discuss a biased version of the nearest-neighbor transposition Markov chain on the set of permutations where neighboring elements i and j are placed in order (i,j) with probability pi,j. The goal is to identify the class of parameter sets P = {pi,j} for which this Markov chain is rapidly mixing.

In joint work with Prateek Bhakta, Dana Randall, and Amanda Streib, we use a reduction from biased permutations to Asymmetric Simple Exclusion Processes (ASEPs) to show that the chain may be slow in the most general setting, even if P is positively biased (i.e., 1 ≥ pi,j ≥ ½ for all i < j). We then prove the chain is rapidly mixing for two new classes. The first is "Choose Your Weapon," where we are given r1, . . . , rn-1 with 1 ≥ ri ≥ ½ and pi,j = ri for all i < j. In the second class "League Hierarchies," the probabilities are based on binary trees.

Finally, in joint work with Amanda Streib, we consider distributions arising from k-class particle processes, where the elements are divided into k classes and the probability of exchanging neighboring elements depends on the particular classes the elements are in. We further require that k is a constant, and all probabilities between elements in different classes are bounded away from 1/2. These particle processes arise in the context of self-organizing lists and our result also applies beyond permutations to the setting where all particles in a class are indistinguishable. Additionally we show that a broader class of distributions based on trees is also rapidly mixing.