论文标题
懒惰掉期的部分洗牌
Partial shuffles by lazy swaps
论文作者
论文摘要
我们可以在$ n $ point设置上制作的最少的随机换位数量是多少（这意味着我们交换成对的元素与给定概率）是多少，以确保每个元素均匀分布 - 从某种意义上说，$ i $映射到$ j $的可能性为$ j $ ins $ j $是$ 1/n $的$ i $和$ i $和$ j $？如果我们坚持认为每对均匀分布怎么办？ 在本文中，我们表明，第一个问题的最低限度约为$ \ frac {1} {2} n \ log_2 n $，当$ n $是$ 2 $的功率时，这是准确的。对于第二个问题，我们表明，令人惊讶的是，答案不是二次：$ O（n \ log^2 n）$随机换位足以满足。我们还表明，如果我们仅要求这对$ 1,2 $均匀分布，那么答案为$ 2N-3 $。这证明了Groenland，Johnston，Radcliffe和Scott的猜想。
What is the smallest number of random transpositions (meaning that we swap given pairs of elements with given probabilities) that we can make on an $n$-point set to ensure that each element is uniformly distributed -- in the sense that the probability that $i$ is mapped to $j$ is $1/n$ for all $i$ and $j$? And what if we insist that each pair is uniformly distributed? In this paper we show that the minimum for the first problem is about $\frac{1}{2} n \log_2 n$, with this being exact when $n$ is a power of $2$. For the second problem, we show that, rather surprisingly, the answer is not quadratic: $O(n \log^2 n)$ random transpositions suffice. We also show that if we ask only that the pair $1,2$ is uniformly distributed then the answer is $2n-3$. This proves a conjecture of Groenland, Johnston, Radcliffe and Scott.
