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!
