Analysis of top to bottom-$k$ shuffles
| dc.creator | Goel, Sharad | |
| dc.date | 2006-03-09 | |
| dc.date.accessioned | 2026-07-07T07:06:41Z | |
| dc.date.available | 2026-07-07T07:06:41Z | |
| dc.description | A deck of $n$ cards is shuffled by repeatedly moving the top card to one of the bottom $k_n$ positions uniformly at random. We give upper and lower bounds on the total variation mixing time for this shuffle as $k_n$ ranges from a constant to $n$. We also consider a symmetric variant of this shuffle in which at each step either the top card is randomly inserted into the bottom $k_n$ positions or a random card from the bottom $k_n$ positions is moved to the top. For this reversible shuffle we derive bounds on the $L^2$ mixing time. Finally, we transfer mixing time estimates for the above shuffles to the lazy top to bottom-$k$ walks that move with probability 1/2 at each step. | |
| dc.description | Published at http://dx.doi.org/10.1214/10505160500000062 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org) | |
| dc.identifier | https://arxiv.org/abs/math/0603209 | |
| dc.identifier | http://arxiv.org/abs/math/0603209 | |
| dc.identifier | Annals of Applied Probability 2006, Vol. 16, No. 1, 30-55 | |
| dc.identifier | doi:10.1214/10505160500000062 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/110117 | |
| dc.subject | Probability | |
| dc.subject | 60 (Primary) 68 (Secondary) | |
| dc.title | Analysis of top to bottom-$k$ shuffles | |
| dc.type | text |