Name
Abstract | ||
|---|---|---|
E. Thorp introduced the following card shuffling model. Suppose the number of cards is even. Cut the deck into two equal piles, then interleave them as follows. Choose the first card from the left pile or from the right pile according to the outcome of a fair coin flip. Then choose from the other pile. Continue this way, flipping an independent coin for each pair, until both piles are empty. We prove an upper bound of Od3 for the mixing time of the Thorp shuffle with 2d cards, improving on the best known bound of Od4. As a consequence, we obtain an improved bound on the time required to encrypt a binary message of length d using the Thorp shuffle. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1017/S0963548312000478 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
thorp shuffle,equal pile,e. thorp,following card shuffling model,time bound,fair coin,markov chain,mixing time.,left pile,right pile,independent coin,binary message,mixing time | Pile,Discrete mathematics,Fair coin,Combinatorics,Upper and lower bounds,Encryption,Deck,Shuffling,Mathematics,Binary number | Journal |
Volume | Issue | ISSN |
22 | 1 | 0963-5483 |
Citations | PageRank | References |
3 | 0.45 | 3 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ben Morris | 1 | 127 | 8.78 |