In 1973, Thorp introduced the following card shuffling procedure. Cut
the deck into two equal piles. Drop the first card from the left pile
or the right pile according to the outcome of a fair coin flip; then
drop from the other pile. Continue this way, flipping an independent
coin each time, until both piles are empty.

Despite its simple description, the Thorp shuffle has been hard to
analyze. It has long been believed that the mixing time is polynomial
in log of the number of cards. We prove the first such bound.

Lecture #10799

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.

• 10799-10799-QuickTime.mov (582 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.

• 10799-10799-MPEG-1 DVD.mpg (673 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

• 10799-10799-DVD PCM Audio.aiff (492 MB - Audio Only)
• 10799-10799-MPEG-2 120min High Quality Encode.m2v (1121 MB - Video Only)

Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included).

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