Mixing time of card-cyclic to random shuffle
主 题: Mixing time of card-cyclic to random shuffle
报告人: 宁巍杨 （Univ. of Washington 数学系）
时 间: 2011-12-12 15:00-16:00
地 点: 理科一号楼1493
Given $n$ cards labeled $1$ to $n$ on the desk, at time $t$ we remove card with label $t$ mod $n$ and reinsert it back into the stack at a random location. Define one round of shuffle by $n$ consecutive such shuffles such that each card has been removed and reinserted exactly once. We show that $\\Theta(\\log n)$ rounds of shuffle is sufficient and necessary to get the whole stack well mixed. This answers a question by Ross Pinsky. Joint work with Ben Morris and Yuval Peres.
