My question is regarding the coupling of the Thorp-Shuffle, as described in Morris/Rogaway/Stegers, Thorp-Shuffle Encryption. On pages 7 to 9, they describe and implement a coupling. It's all fairly elementary up until equation (5), where they show that the coupling time $T$ satisfies $P(T > 2n-1) \le p$, where $p = nl2^{2-n}$ (top of page 9). To do this, they say the following.

Let $A$ be the event that at some time in $\{n-1,n,...,2n-2\}$ the card $z_{l+1}$ is adjacent* to some card of smaller index in the $Y$ or $Z$ process**. Unless $A$ occurs, coupling occurs by time $2n-1$.

*By "adjacent", they mean that, as bit strings, all but their first (leftmost) bit agree, ie $x$ is adjacent to $x + N/2 \text{ mod } N$, where $N = 2^n$. (See 2/3rds of the way down page 7.) **When they say $Y$ or $Z$, $Y$ hasn't been defined; I assume they mean $X$ and $U$? However, by definition of the coupling, the positions of cards $z_1, ..., z_l$ are the same in $X$ and $U$.

Now, my question is this: how can we deduce if coupling has not occurred by time $2n-1$ then $A$ has occurred, ie unless $A$ occurs then coupling occurs by time $2n-1$? I don't see why coupling means that the cards can't be adjacent.

If anyone has any better tags, please do add away! I wanted to tag thorp, mixing, total variation or coupling, but none of these exist -- even Markov chain doesn't!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.