论文标题
完美的改组，较少的懒惰换位
Perfect shuffling with fewer lazy transpositions
论文作者
论文摘要
懒惰的换位$（a，b，p）$是随机排列，其标识与概率$ 1-p $和s_n $中的thresposition $ 1-p $（a，b）\ in s_n $具有概率$ p $。如果它们的组成分布均匀分布，则必须将一系列独立的懒惰换位序列？众所周知，有长度$ \ binom {n} 2 $的序列，但是序列较短吗？这是由Fitzsimons在2011年提出的，并在2018年由Angel和Holroyd独立。我们通过构建长度$ \ frac23 \ binom {n} 2+o（n \ log n \ log n）$来负面回答这个问题，并考虑一些相关问题。
A lazy transposition $(a,b,p)$ is the random permutation that equals the identity with probability $1-p$ and the transposition $(a,b)\in S_n$ with probability $p$. How long must a sequence of independent lazy transpositions be if their composition is uniformly distributed? It is known that there are sequences of length $\binom{n}2$, but are there shorter sequences? This was raised by Fitzsimons in 2011, and independently by Angel and Holroyd in 2018. We answer this question negatively by giving a construction of length $\frac23 \binom{n}2+O(n\log n)$, and consider some related questions.
