A Shuffle that Mixes Sets of any Fixed Size much Faster than it Mixes the Whole Deck

Details A Shuffle that Mixes Sets of any Fixed Size much Faster than it Mixes the Whole Deck A Shuffle that Mixes Sets of any Fixed Size much Faster than it Mixes the Whole Deck

2004-04-02

arxiv.org/abs/math/0404052v1

Rand. Struct. Alg., 9, 609 - 625 (1994)

Mathematics

Probability

20 pages

Scientific paper

Consider an n by n array of cards shuffled in the following manner. An element x of the array is chosen uniformly at random; Then with probability 1/2 the rectangle of cards above and to the left of x is rotated 180 degrees, and with probability 1/2 the rectangle of cards below and to the right of x is rotated 180 degrees. It is shown by an eigenvalue method that the time required to approach the uniform distribution is between n^2/2 and cn^2 ln n for some constant c. On the other hand, for any k it is shown that the time needed to uniformly distribute a set of cards of size k is at most c(k)n, where c(k) is a constant times k^3 ln(k)^2. This is established via coupling; no attempt is made to get a good constant.

Affiliated with

Also associated with

No associations

Rating

A Shuffle that Mixes Sets of any Fixed Size much Faster than it Mixes the Whole Deck does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Shuffle that Mixes Sets of any Fixed Size much Faster than it Mixes the Whole Deck, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Shuffle that Mixes Sets of any Fixed Size much Faster than it Mixes the Whole Deck will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-287391