A deck of n cards is shuffled by repeatedly moving the top card
to one of the bottom k_n positions of the deck uniformly at random. How
many shuffles does it take to randomize the deck? For k_n = n, this is the
well-studied top to random walk and n log n shuffles are required; for k_n
= 2, this is the Rudvalis shuffle and order n3 log n shuffles are needed.
I plan to discuss the mixing time for this family of shuffles as k_n
ranges from a constant to n, showing that for large k_n the walks behave
like the top to random shuffle, while for small k_n the walks behave like
the Rudvalis shuffle. Some of the tools used to analyze these walks
include coupling, Wilson's lemma, and comparison techniques for random
walks on groups.

Lecture #10801

Need help? Visit our help pages at http://www.msri.org/communications/vmath/hints

Streaming Video

This is a high quality streaming video encoded with MPEG-4 and with 640x480 resolution.

Windows and Mac users, QuickTime 6.5 or later required
Linux users, please see our Linux Help Page on how to view our streaming videos

Follow this link to --- Watch the Video Now Via Streaming Video ---

Download QuickTime File

You can download the QuickTime file here. Right click on the link and "Save As..." to save to your local computer.

• 10801-10801-QuickTime.mov (426 MB)

Download MPEG File

You can download the MPEG file here. Right click on the link and "Save As..." to save to your local computer.

• 10801-10801-MPEG-1 DVD.mpg (437 MB)

Create a DVD

You can download the video and audio files here. Please note that you need both files to create a DVD. Right click on the link and "Save As..." to save to your local computer. You can find instructions on how to create a DVD on our help page at http://www.msri.org/communications/vmath/author

• 10801-10801-DVD PCM Audio.aiff (320 MB - Audio Only)
• 10801-10801-MPEG-2 120min High Quality Encode.m2v (729 MB - Video Only)

Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture.

If you would like to purchase a copy of this video for $15+shipping, please Click Here!

See more of our Streaming Videos on our main VMath - Streaming Video page.