Fastest Coupling of Random Walks

A new coupling of one-dimensional random walks is describedwhich tries to control the coupling by keeping the separationof the two random walks of constant sign. It turns out thatamong such monotone couplings there is an optimal one-step couplingwhich maximises the second moment of the difference (assumingthis is finite), and this coupling is ‘fast’ inthe sense that for a random walk with a unimodal step distributionthe coupling time achieved by using the new coupling at eachstep is stochastically no larger than any other coupling. Thisis applied to the case of symmetric unimodal distributions.