论文标题
自上而上的命中版本
The hit-and-run version of top-to-random
论文作者
论文摘要
我们研究了在对称组$ \ mathbf s_n $上随机步行的一个示例。我们的出发点是熟悉的{\ em自上而下}洗牌。在命中和跑步版本中，在每个{\ em单个步骤}中，在选择插入点，$ j $，在$ \ {1，\ dots，n \} $中均匀地随机，顶部卡插入$ j $ th的位置$ k $ k $ k $ in $ k $ in $ k $ in $ k $ in $ k $ in $ k $ in $ k $ in cob in $ \ \ \ \ \ {0,1,1，问题是，这会加速混合吗？我们表明，在$ l^2 $和SUP-NORM中，这最多可以加速混合，而恒定因素（独立于$ n $）。在总变化中分析此问题是一个有趣的开放问题。
We study an example of a {\em hit-and-run} random walk on the symmetric group $\mathbf S_n$. Our starting point is the well understood {\em top-to-random} shuffle. In the hit-and-run version, at each {\em single step}, after picking the point of insertion, $j$, uniformly at random in $\{1,\dots,n\}$, the top card is inserted in the $j$-th position $k$ times in a row where $k$ is uniform in $\{0,1,\dots,j-1\}$. The question is, does this accelerate mixing significantly or not? We show that, in $L^2$ and sup-norm, this accelerates mixing at most by a constant factor (independent of $n$). Analyzing this problem in total variation is an interesting open question.
