### Skapa referens, olika format (klipp och klistra)

**Harvard**

Jonasson, J. (2011) *Mixing time bounds for overlapping cycles shuffles.*.

** BibTeX **

@article{

Jonasson2011,

author={Jonasson, Johan},

title={Mixing time bounds for overlapping cycles shuffles.},

journal={ELECTRONIC JOURNAL OF PROBABILITY},

issn={1083-6489},

volume={16},

issue={46},

pages={1281-1295},

abstract={Consider a deck of n cards. Let p(1), p(2), ... , p(n) be a probability vector and consider the mixing time of the card shuffle which at each step of time picks a position according to the p(i)'s and move the card in that position to the top. This setup was introduced in [5], where a few special cases were studied. In particular the case p(n-k) = p(n) = 1/2, k = circle minus(n), turned out to be challenging and only a few lower bounds were produced. These were improved in [1] where it was shown that the relaxation time for the motion of a single card is circle minus(n(2)) when k/n approaches a rational number.
In this paper we give the first upper bounds. We focus on the case m := n - k = left perpendicularn/2right perpendicular. It is shown that for the additive symmetrization as well as the lazy version of the shuffle, the mixing time is O (n(3) log n). We then consider two other modifications of the shuffle. The first one is the case p(n-k) = p(n-k+1) = 1/4 and p(n) = 1/2. Using the entropy technique developed by Morris [7], we show that mixing time is O(n(2) log(3) n) for the shuffle itself as well as for the symmetrization. The second modification is a variant of the first, where the moves are made in pairs so that if the first move involves position n, then the second move must be taken from positions m or m + 1 and vice versa. Interestingly, this shuffle is much slower; the mixing time is at least of order n(3) log n and at most of order n(3) log(3) n.
</br></br>
It is also observed that results of [1] can be modified to improve lower bounds for some k = o(n).},

year={2011},

keywords={comparison technique, Wilson's technique, relative entropy },

}

** RefWorks **

RT Journal Article

SR Print

ID 144572

A1 Jonasson, Johan

T1 Mixing time bounds for overlapping cycles shuffles.

YR 2011

JF ELECTRONIC JOURNAL OF PROBABILITY

SN 1083-6489

VO 16

IS 46

SP 1281

OP 1295

AB Consider a deck of n cards. Let p(1), p(2), ... , p(n) be a probability vector and consider the mixing time of the card shuffle which at each step of time picks a position according to the p(i)'s and move the card in that position to the top. This setup was introduced in [5], where a few special cases were studied. In particular the case p(n-k) = p(n) = 1/2, k = circle minus(n), turned out to be challenging and only a few lower bounds were produced. These were improved in [1] where it was shown that the relaxation time for the motion of a single card is circle minus(n(2)) when k/n approaches a rational number.
In this paper we give the first upper bounds. We focus on the case m := n - k = left perpendicularn/2right perpendicular. It is shown that for the additive symmetrization as well as the lazy version of the shuffle, the mixing time is O (n(3) log n). We then consider two other modifications of the shuffle. The first one is the case p(n-k) = p(n-k+1) = 1/4 and p(n) = 1/2. Using the entropy technique developed by Morris [7], we show that mixing time is O(n(2) log(3) n) for the shuffle itself as well as for the symmetrization. The second modification is a variant of the first, where the moves are made in pairs so that if the first move involves position n, then the second move must be taken from positions m or m + 1 and vice versa. Interestingly, this shuffle is much slower; the mixing time is at least of order n(3) log n and at most of order n(3) log(3) n.
</br></br>
It is also observed that results of [1] can be modified to improve lower bounds for some k = o(n).

LA eng

OL 30