Mixing times of Markov chains for self‐organizing lists and biased permutations
Mixing times of Markov chains for self‐organizing lists and biased permutations
复制标题
用于自组织列表和有偏排列的马尔可夫链的混合时间
DOI：
10.1002/rsa.21082
复制
发表时间：
2022
影响因子：
1
通讯作者：
Streib, Amanda Pascoe
中科院分区：
文献类型：
--
作者：
Bhakta, Prateek;Miracle, Sarah;Randall, Dana;Streib, Amanda Pascoe
我们研究了有偏排列上马尔可夫链的混合时间，这是一个与自组织列表有关的问题。我们被给予概率{pi，j}，$$\Left\{p}_{i，j}\Right\}，对于所有i≠j，$$i\ne j，$$使得pi，j=1−pj，i$${p}_{i，j}=1-{p}_{j，i}$$。链ℳnn$${\mathcal{M}}_{nn}$$迭代地选择两个相邻的元素i$$i$$和j$$j$$，并以概率pi，j$${p}_{i，j}$$交换它们。人们猜想，当概率集是“正偏的”时，ℳnn$${\mathcal{M}}_{nn}$$是快速混合的，即：{pi，j≥1/2}，$$\left\{{p}_{i，j}\ge 1/2\right\}，$$表示所有i<；j$$i<；j$$。我们定义了两个一般类，并首次证明了ℳnn$${\mathcal{M}}_{nn}$$对两者都是快速混合的。我们还证明了链可以有指数混合时间，从而反驳了这个猜想的最一般版本。
We study the mixing time of a Markov chain on biased permutations, a problem related to self‐organizing lists. We are given probabilities {pi,j},$$ \left\{{p}_{i,j}\right\}, $$ for all i≠j,$$ i\ne j, $$ such that pi,j=1−pj,i$$ {p}_{i,j}=1-{p}_{j,i} $$. The chain ℳnn$$ {\mathcal{M}}_{nn} $$ iteratively chooses two adjacent elements i$$ i $$ and j$$ j $$, and swaps them with probability pi,j$$ {p}_{i,j} $$. It has been conjectured that ℳnn$$ {\mathcal{M}}_{nn} $$ is rapidly mixing whenever the set of probabilities are “positively biased,” that is, {pi,j≥1/2},$$ \left\{{p}_{i,j}\ge 1/2\right\}, $$ for all i<j$$ i<j $$. We define two general classes and give the first proofs that ℳnn$$ {\mathcal{M}}_{nn} $$ is rapidly mixing for both. We also demonstrate that the chain can have exponential mixing time, disproving the most general version of this conjecture.
登录
查看更多内容
DOI：
--
发表时间：
1982-07
期刊：
--
影响因子：
--
作者：
P. Flajolet
通讯作者：
P. Flajolet
IRMA，斯特拉斯堡（法国）
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--
影响因子：
1.3
作者：
I. Benjamini;Noam Berger;C. Hoffman;Elchanan Mossel
通讯作者：
Elchanan Mossel
使用指数度量对有偏差的晶格配置进行采样
影响因子：
1.3
作者：
Sam Greenberg;A. Streib;Dana Randall
通讯作者：
Dana Randall
可逆马尔可夫链的比较定理
DOI：
--
发表时间：
1993
期刊：
影响因子：
--
作者：
P. Diaconis;L. Saloff‐Coste
通讯作者：
L. Saloff‐Coste