\magnification=1200
\input amssym.def
\input amssym
\input epsf 
%%  THIS BASELINESKIP WAS USED FOR SUBMISSION TO ANN PROB
%%
%\baselineskip=20pt
%%
%%
\def\med{\vskip 0.1 in \noindent}
\def\big{\vskip 0.2 in \noindent}
\def\small{\vskip 0.05 in \noindent}
\def\cl{\centerline}
\def\ve{\varepsilon}
\def\dt{\Delta t}
\def\dx{\Delta x}
\def\g{\gamma}
\def\o{\omega}
\def\r{\rho}
\def\ssq{\sigma^2}
\def\s{\sigma}
\def\l{\lambda}
\def\L{\Lambda}
\def\vp{\varphi}
\def\R{{\Bbb R}}
\def\Z{\Bbb Z}
\def\E{{\Bbb E}}
\def\P{{\Bbb P}}
\def\norm{||}
\def\ts{\tilde S}
\def \half {{\scriptstyle {1 \over 2}}}


\def\dist{\thicksim}
\def\vp{\varphi}

\cl{\bf FASTEST COUPLING OF RANDOM WALKS}
\med
\cl{L C G Rogers}\footnote{ }{Research supported
in part by EPSRC grant number GR/J97281}
\med
\cl{University of Bath}
\med
\cl{This draft: April 1997}
\med
\med
\cl{Tel: +44 1225 826224}
\cl{Fax: +44 1225 826492}
\cl{Email: lcgr@maths.bath.ac.uk}
\big
\cl{\bf Abstract}
\big
We describe a new coupling of one-dimensional random walks which
tries to control the coupling by keeping the separation of the 
two random walks of constant sign. It turns out that among
such monotone couplings there is 
an optimal one-step coupling which maximises the second moment 
of the difference (assuming this is finite), and this coupling
is `fast' in the sense that for a random walk with a unimodal step
distribution the coupling time achieved by using the new coupling at 
each step is
stochastically no larger than any other coupling. 
We apply this to the case of symmetric unimodal distributions.
\med
{\sl Abbreviated title:} FASTEST COUPLING OF RANDOM WALKS
\med
{\sl Key words and phrases:}
Coupling, random walk, unimodal, Cauchy, monotone coupling, maximal coupling.
\med
{\sl AMS 1991 Subject Classifications:} Primary 60J15

\vfill\eject




\cl{\bf FASTEST COUPLING OF RANDOM WALKS}
\med
\cl{\bf L C G Rogers}
\med
\cl{\bf University of Bath}
\big
{\bf 1. Introduction.} Over the last two decades or so,
the coupling method has established itself as a powerful technique for proving
convergence results, and has been applied to a large range of 
 processes, such as random walks, renewal processes, particle
systems; the beautiful survey by Lindvall [5] presents the main ideas
and many typical applications.   The object of this paper is to 
study `monotone coupling' of real-valued random walks; by this we mean
that if $(S_n)_{ n \geq 0}$ and $(S'_n)_{ n \geq 0}$ are two real-valued
random walks with common step distribution $F$ but different initial 
conditions, $S_0 < S'_0$, we shall be considering couplings (that is, 
joint laws for the two processes $S$ and $S'$) with the property that
$$
S_n \leq S'_n \;\;\hbox{\rm for all }\, n.
$$
A coupling is called {\it successful} if the coupling time $T \equiv
\inf \{ n: S_n=S'_n \} $ is almost surely finite, and we may and shall assume
that $S_n=S'_n$ for all $n \geq T$.
 

The advantage of looking at monotone couplings is that the difference
process $S'_n-S_n$ is a non-negative martingale\footnote{$^1$}{assuming that the 
step distribution has finite first moment}, and this guarantees the almost-sure
convergence of the difference as $n \rightarrow \infty$. This does not
(of course) ensure successful coupling, but helps in that direction. 

A coupling may be successful, but is it good? If ${\cal L} (\theta_n S)$ denotes the
law of the process $(S_n, S_{n+1}, S_{n+2},\ldots)$, the coupling inequality
(see I.2 in  [5]) gives the bound on the total-variation norm
$$
\norm  {\cal L} (\theta_n S) - {\cal L} (\theta_n S') \norm \leq 2 \P(T>n),
$$
and for a coupling to be good, we would want the bound to be tight. In fact, it
is known (see Goldstein [2], Thorisson [8]) that one {\it can} 
construct a coupling for which the
coupling inequality holds with equality for all $n$, but the 
Goldstein-Thorisson construction is quite
abstract. If we call such a coupling a {\it fastest} coupling\footnote{$^2$}
{also known as a {\it maximal} coupling}, then the main 
result of this paper is an explicit construction of a fastest coupling 
in the special case where
the step distribution is unimodal. 


In more detail, in Section 2 we shall consider just a single step of the random walks $S$
and $S'$, assuming that $S_0=0$ and $S'_0=a >0$. We shall then  construct
a pair $(X,Y)$ such that
\small
(1.i) $X \leq Y$ almost surely;
\small
(1.ii) $X$ has law $F$ and $Y$ has law $F_a \equiv \delta_a * F$;
\small
(1.iii) $\E \; \varphi(Y-X)$ is maximal for any non-negative decreasing
convex function $\varphi$.
\small
To amplify, we aim to maximise $\E \; \varphi(Y-X)$ over choice of joint laws
of $(X,Y)$ which satisfy (1.i) and (1.ii).  It is not obvious that there
should be a unique joint law which achieves this maximum whatever convex decreasing
$\varphi \geq 0$ we take, but this is what happens, as we shall prove in Section 2.
The joint law of $(X,Y)$ is given explicitly in term of the marginals; see (4).
Our problem (1) is a problem of Monge-Kantorovich type; for  surveys, see
for example, [2] or [7]. The result proved here appears to be new.

The motivation for trying to achieve (1.iii) is that we would like to maximise
$\E \,[ (X-Y)^2 ]$, so as to create a difference process with the largest possible
quadratic variation, and so hopefully with a short coupling time.  
If $F$ has finite second moment, then the joint law which optimises (1.i)--(1.iii)
also maximises the second moment of the difference $X-Y$, but the problem is 
well posed without assuming finite second moments, and the generality of 
(1.iii) is needed for the next stage of the paper.

The optimality property of Section 2 is myopic, 
in that for a given step distribution
we seek to achieve a `best' coupling of the single step about to be made, 
but it turns out that {\it in the case where $F$ is unimodal}, this myopic
strategy is globally optimal; the coupling is fastest.
This is proved in Section 3. 

The construction of Sections 2 and 3 is concrete, but not particularly
easy to visualise. However, as we show in Section 4, in the case of {\it symmetric}
unimodal step distributions, the construction is much more explicit, and we
are able to derive a simple expression for the total-variation distance:
$$\eqalign{
\norm  {\cal L} (\theta_n S) - {\cal L} (\theta_n S') \norm &= 2 \P(T>n)\cr
&= 2 \P ( |S_n| < a/2 ).\cr}
$$
We are then able to exhibit examples of random walks which couple very rapidly
indeed; while the best rate of convergence one can achieve in general is
$O(n^{-1/2})$ (see, for example, Lindvall \& Rogers  [6]), by taking symmetric
unimodal distributions with much fatter tails
we can get very fast couplings, even couplings for which the coupling time has
finite moments!



\med
{\bf Acknowledgement.}  It is a pleasure to thank Torgny Lindvall for
stimulating discussions on the issues discussed in  this paper, and other topics.
Anyone reading this article will join me in thanking also an exceptionally
diligent and perceptive referee, whose careful reading of the manuscript
resulted in many improvements.


\big
{\bf 2. Monotone coupling of a single step.}  
Here is the main result of this section.
\med
THEOREM 1. {\sl Suppose that $F$ and $G$ are two distribution functions, 
such that $G$ is stochastically larger than $F$:
$$
G(x) \leq F(x)\leqno(2)
$$
for all $x$, and suppose that $\vp : \Bbb R^+ \rightarrow \Bbb R^+$ is strictly 
convex and decreases to 0. The problem of finding a probability measure $P$ on
$\Bbb R^2$ such that:
\small
(3.i) $P$ is concentrated on $\{ (x,y): x \leq y\}$;
\small
(3.ii) the marginals of $P$ are $F$ and $G$;
\small
(3.iii) the payoff
$$\int \int \vp(y-x) P (dx, dy)$$
is maximised
\small
is solved by taking for $x \leq y$
$$\leqalignno{
P(x,y) &\equiv P((-\infty,x] \times (-\infty, y])\cr
&=\Gamma(x,y)\cr
&\equiv \sup_{s \leq x} \sup_{s\leq v \leq y} \left( G(v) -F(v)+F(s)
\right),&(4)\cr}
$$
and $P(x,y) = P(y,y)$ for $x >y$.}
\med
{\sl Remarks.} (i) The condition (2), that $G$ is stochastically
larger than $F$,  will certainly be satisfied if $G = F_a \equiv \delta_a * F$.
\small
(ii) It is tempting to conjecture that the Theorem might still be true if we
did not insist on (3.i), if we extend $\vp$
to $(-\infty,0)$ symmetrically. If this were the case, optimality would force
$X \leq Y$ $P$-almost surely. However, without (3.i) the result collapses,
and in Figure 1 we give a simple example concentrated on $\{ 0,1,\ldots,12 \}$
for which the conjecture fails. The positive integers shown in the grid need
to be normalised to become a probability distribution, but modulo 
this trivial transformation, what is shown in Figure 1 is
 the optimal monotone
coupling, as at (4). However, if $\vp(1) + \vp(7) > 2 \vp(3) $,
as is perfectly possible, then we can improve the payoff by increasing
the probability on the starred squares
 (6,5) and (2,7), and reducing the probability
on (2,5) and (6,9) to zero. This shows also that without the monotonicity
restriction the optimal joint law may be different for 
different $\vp$.
\small
(iii) In the example of Figure 1, notice also that the law $G$ is in fact
$F_1$, the law of the first marginal shifted up by 1.
\med
{\sl Proof.} To begin with, the payoff can be re-expressed as
$$\leqalignno{
\int \int \vp(y-x) P (dx, dy) &= \int \int \left( \int_{t=y-x}^{\infty}
 -\vp'(t) dt \right) P (dx, dy)\cr
&= \int \int \left( \int_{t=y-x}^{\infty} \int_{s=t}^{\infty} \vp''(ds)
  dt \right) P (dx, dy)\cr
&=\int_0^{\infty} \vp''(ds) \int_{-\infty}^{\infty} \P[Y \leq u, X > u-s] \;du.
&(5)\cr}
$$
Thus the problem can be seen as one of finding good upper bounds for
$ \P[Y \leq u, X > u-s]$ for pairs of random variables $(X,Y)$ with marginals $F$
and $G$, and for which $X \leq Y$.

\noindent
Take $x<y$ and observe that if $P$ satisfies (3.i) and (3.ii) then
$$\eqalign{
\P( Y \leq y, X > x ) & \leq F(y) - F(x) \cr
\P( Y \leq y, X > x ) & \leq G(y) - G(x), \cr}
$$
so that
$$\leqalignno{
P(x,y) &= G(y) - \P( Y \leq y, X > x ) &(6)\cr
&\geq G(y) - (F(y) - F(x)) \wedge (G(y)-G(x)) \cr
&=G(x) \vee (F(x)+G(y)-F(y)).\cr}
$$
Since $P(\cdot\; ,\cdot)$ is increasing in both arguments, we must have that
$$
P(x,y) \geq h(x,y) \equiv \sup_{x \leq v \leq y} \{ G(v)-F(v)+F(x) \} \leqno(7)
$$
The function $h$ is clearly increasing in its second argument, but not always
increasing in its first; we conclude that any $P$ satisfying (3.i) and (3.ii)
must satisfy the inequality
$$
P(x,y) \geq \Gamma(x,y) \equiv \sup_{s \leq x} h(s,y),\leqno(8)
$$
for all $x \leq y$, rewriting the definition of $\Gamma$ more briefly.
Combining (8), (6) and (5), we deduce that for any convex function $\vp$
decreasing to 0 and $P$ satisfying (3.i) and (3.ii)
$$
\E \;\vp(Y-X) \leq \int_0^{\infty} \vp''(ds) \int_{-\infty}^{\infty}
(G(u) - \Gamma(u-s,u)) du.
$$
The proof will be completed by showing that $\Gamma$ {\it is} a distribution function
satisfying (3.i) and (3.ii).

Firstly we show that the marginals of $\Gamma$ are correct. Noting that for 
$x \leq y$ we have $h(x,y) \leq G(y)$, we have that
$$\eqalign{
\lim_{x \rightarrow \infty} \Gamma(x,y) &= \Gamma(y,y)\cr
&=\sup_{s \leq y} h(s,y)\cr
&\leq G(y)\cr}
$$
and on the other hand $h(s,y) \geq G(s)$ for all $s \leq y$, so 
$$
\Gamma(y,y)=\sup_{s \leq y} h(s,y)\geq G(y),
$$
and the second marginal is seen to be $G$, as it should be. As for the
first marginal, we see that (because $G \leq F$)
$$
h(x,y) \equiv \sup_{x \leq v \leq y} \{ G(v)-F(v)+F(x) \} \leq F(x)
$$
for $x \leq y$, and letting $y \uparrow \infty$ we see that 
$$
\lim_{y \uparrow \infty} h(x,y) = F(x),
$$
from which immediately $\lim_{y \uparrow \infty} \Gamma (x,y) = F(x)$,
confirming the first marginal to be what it should be.

All that remains, therefore, is to prove that the function $\Gamma$ actually 
{\it is} a distribution function. To spell it out, this requires us to show that
for $x < x' \leq y < y'$,
$$
\Gamma(x',y')-\Gamma (x,y') -\Gamma (x',y) + \Gamma(x,y) \geq 0.\leqno(9)
$$
In fact, we really should show this inequality for {\it any} pairs $x<x'$ and 
$y<y'$, but since $\Gamma$ does not charge $\{ (x,y): x > y\}$, it is enough
to prove (9) for the more restricted range $x < x' \leq y < y'$.

If we define for $x \leq y$
$$
m(x,y) \equiv \inf_{v \in [x,y]} \left( F(v)- G(v) \right),\leqno(10)
$$
then we see that $m$ is non-negative, increasing in its first argument,
and decreasing in its second argument; and for $s \leq y \leq y'$,
$$
m(s,y') = m(s,y) \wedge m(y,y').
$$
Moreover, we can express $h$ in terms of $m$ as $h(x,y) = F(x) - m(x,y)$, so 
that $\Gamma(x,y) = \sup_{s \leq x} (F(s)-m(s,y))$, and for $u \leq y \leq y'$
we have
$$\eqalign{
\Gamma(u,y') &= \sup_{s \leq u} \{ F(s)-(m(s,y) \wedge m(y,y')) \} \cr
&=\sup_{s \leq u} \{ F(s)- m(s,y) +(m(s,y) -m(y,y'))^+ \}, \cr
\Gamma(u,y) &= \sup_{s \leq u} \{ F(s)- m(s,y) \}. \cr}
$$
Thus if we hold fixed $y$ and $y'$ with  $y < y'$ and let
 $s^* \equiv \inf \{ s \leq y : m(s,y) > m(y,y') \}$, we shall have that
$\Gamma(s,y')-\Gamma(s,y)$ will be zero for $s < s^*$, and will be increasing
for $s^* \leq s \leq y$. To see this, observe that the functions
$s \mapsto  F(s)- m(s,y)$ and
$s \mapsto  F(s)- m(s,y')$ differ by a non-negative incresaing function.
Any point of increase $s > s^*$ of $\Gamma (\cdot,y)$ is automatically 
a point of increase of  $\Gamma (\cdot,y')$, and the increase of 
 $\Gamma (\cdot,y')$ over a subinterval of $[s^*,y]$ is at least 
as large as the increase of  $\Gamma (\cdot,y)$.
  The inequality (9) follows.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\big
{\bf 3. Fastest coupling for unimodal distributions.} In this section, we shall
suppose that the step distribution $F$ is {\it unimodal}, which is to say that
there is some real value (without loss of generality, 0) such that to the 
right of that value $F$ is concave, and to the left of that value $F$ is convex.
We are going to use the monotone  coupling of two random walks with 
step distribution
$F$ inspired by Theorem 1, which we shall call the 
 convex-monotone (CM) coupling. 
In more detail, if $S_0=0$ and $S'_0=a>0$, we shall make the 
joint distribution of $(S_1,S'_1)$ according to the recipe (4), when we use
$G=F_a$. If the realised value of $(S_1,S'_1)$ is $(b,c)$ we then make the
joint law of $(S_2,S'_2)$ according to the recipe (4), taking the first marginal to 
be $F_b$ and the second marginal to be $F_c$. Subsequent steps of the process
are generated analogously.

The main result of this section will be the following.
\med
THEOREM 2. {\sl Assume that the step distribution $F$ is unimodal. Consider
two couplings $(S_n, S'_n)_{n \geq 0}$ and $(\ts_n, \ts'_n)_{n \geq 0}$, where
$S_0=\ts_0=0$ and $S'_0 = \ts'_0 =a>0$. Suppose that the coupling $(S,S')$
is the CM-coupling constructed in Theorem 1, and that $(\ts, \ts')$ is
any coupling.
If 
$$ 
T \equiv \inf \{ n \geq 0: S_n = S'_n \}, \quad \tilde T 
\equiv \inf \{ n \geq 0: \ts_n = \ts'_n \},
$$
then for any $n\geq 0$,
$$
\P(T \geq n) \leq \P(\tilde T \geq n).\leqno(11)
$$}
\med
{\sl Remarks.} Theorem 2 tells us that if the step distribution is unimodal, 
then the coupling time for the CM-coupling is stochastically smallest
among all couplings of the random walks, even without restricting the 
coupling to be monotone.
\med
{\sl Proof.}
In fact, what we shall prove is stronger than the statement of Theorem 2.

To begin with, let us fix $\l >0$ and define for each $n \in \Z^+$ the function
$$
V_n(a) \equiv \sup \{ \E \, \exp ( -\l |S'_n-S_n| ): S'_0=a, S_0=0 \},
$$
the sup being taken over all joint laws of $(S,S')$ with $S'_0=a$,
$S_0=0$.
The functions $V_n$ satisfy the dynamic programming equation
$$
V_{n+1}(a) = \sup \, \E \,\left[ V_n(S'_1-S_1) | S_0=0, S'_0=a \right].\leqno(12)
$$
It is clear that the function $V_n$ is symmetric about 0, and is bounded between
0 and 1. 
The key to the proof is the following result, which is of independent
interest.
\med
LEMMA 1. {\sl Fix $a>0$. Suppose that $\vp : \R \rightarrow \R^+$ is symmetric,
 convex and decreasing in $\R^+$, and that $F$ is unimodal. Then the problem
$$
\max \{ \; \E \, \vp(Y-X) \; : X \dist F,\;  Y \dist F_a \, \}
$$
is solved by the CM-coupling of $F$ and $F_a$.}
\med
{\sl Remarks.} (i) The point of Lemma 1 is that even without requiring
that $X \leq Y$, the optimal joint law will have this property, provided
$F$  is unimodal.  The earlier example of Figure 1 shows that this is not
true in general without unimodality.
\small
(ii) The proof provides a pretty description of the optimal joint law of 
$(X,Y)$. As a particular special case, if $F$ is symmetric about 0 and 
unimodal, with density $f$, we have
$$\eqalign{
\P( X \in dx, Y=X)  &= [f(x) \wedge f(x-a)] dx \quad \hbox{\rm for $x \in \R;$}\cr
\P( X \in dx, Y=a-X)&= [f(x)-f(x-a)]dx \quad \hbox{\rm for $x \leq a/2.$}\cr}
$$
{\sl Proof of Lemma 1.} As in the proof of Theorem 1, with $P$
denoting the joint law of $(X,Y)$, we estimate
$$\leqalignno{
\E\; \vp(Y-X)&=\int \int_{\{x>y\}} P(dx,dy) \int_{-\infty}^{y-x} dt
\int_{-\infty}^t \vp''(ds) \cr
&\quad\quad\quad\quad\quad\quad
+\int \int_{\{x\leq y\}} P(dx,dy) \int^{\infty}_{y-x} dt
\int^{\infty}_t \vp''(ds) \cr
&=\int_0^{\infty} \vp''(ds) \{ \int_0^s dt \left[ \P (X-t<Y<X)+
\P(X \leq Y \leq X+t) \right] \} \cr
&=\int_0^{\infty} \vp''(ds)\{ \E \left[ (s-X+Y)^+; Y<X \right]
+\E \left[ (s-Y+X)^+ ; Y \geq X \right] \}\cr
&=\int_0^{\infty} \vp''(ds) \int_{-\infty}^{\infty} dt
\left( 
\P[t-s< Y < X \leq t] + \P[ t-s < X \leq Y \leq t]\right)\cr
&=\int_0^{\infty} \vp''(ds) \int_{-\infty}^{\infty} dt\;
\P [ (X,Y) \in (t-s,t]^2 ]&(13).
\cr}
$$
Thus we want to make $\P [ (X,Y) \in (t-s,t]^2 ]$ as large as possible
for each $s$ and $t$, subject to the constraints of the marginals of 
$(X,Y)$ being $F$ and $F_a$.  Now it is clear that
$$
\P [ (X,Y) \in (t-s,t]^2 ] \leq \left( F(t)-F(t-s) \right)
\wedge \left( F_a(t)-F_a(t-s) \right),\leqno(14)
$$
and we shall now show that if $F$ is unimodal then the CM-coupling
achieves this obvious bound, and so must be optimal.

To prove this, we need to observe that if $F$ is unimodal, then the
function $x \mapsto F(x) - F(x-a)$ is non-negative,
and is increasing to the left of some point,
%$\xi(0,a)$ 
 decreasing to the right of that point. 
(Think of the slope of the chord from $(x-a,F(x-a))$ to $(x,F(x))$ as
$x$ increases!)
Thus for $x \leq y$
$$\eqalign{
\Gamma_a(x,y)
&\equiv \sup_{s \leq x} \sup_{s\leq v \leq y} \left( F_a(v) -F(v)+F(s)\right)\cr
&=\sup_{s \leq x}\left(F(s)-\inf_{s\leq v \leq y}\{ F(v)-F_a(v)\} \right)\cr
&=\sup_{s \leq x}\left(F(s)- \{F(s)-F_a(s)\} \wedge \{ F(y) -F_a(y)\} \right)\cr
&=\sup_{s \leq x}\left(F_a(s) \vee \{F_a(y)-F(y)+F(s)\}\right)\cr
&=F_a(x) \vee \{F_a(y)-F(y)+F(x)\}.\cr
}
$$
Now apply this: we obtain for the measure $\mu$ with distribution function 
$\Gamma_a$
$$\leqalignno{
\mu((x,y]\times (x,y]) &= 
\Gamma_a(y,y)-\Gamma_a(x,y)-\Gamma_a(y,x)+\Gamma_a(x,x)\cr
&=F_a(y)-\Gamma_a(x,y)\cr
&=\{F_a(y)-F_a(x) \} \wedge \{ F(y)-F(x) \},&(15)\cr
}
$$
as required. Thus the CM-coupling is the optimal coupling without monotonicity
constraint, assuming that $F$ is unimodal.
\big
To conclude the proof of Theorem 2, define for $c>0$ the function $\vp_c(x)
=(c-|x|)^+$, which is symmetric, and convex decreasing in $\R^+$.
\med
LEMMA 2. {\sl If we define for $a, c >0$
$$
\psi(a,c) \equiv \sup \{ \E\, \vp_c(Y-X) \; : X \dist F,  Y \dist F_a \},
\leqno(16)
$$
then for any $a,c>0$ we have
$$
\psi(a,c)+a = \psi(c,a)+c.\leqno(17)
$$}

Before we prove Lemma 2, let us see how Theorem 2 follows from it. 
From (16) it is clear that $\psi$  is convex in its second
argument, since the optimal joint law is the same whatever $c$. From
Lemma 2, therefore, $\psi$ is also convex in its {\it first} argument.
Now 
$$\eqalign{
V_1(a)&\equiv \sup \{ \E\, \exp(-\lambda |Y-X|) \; ;
Y\dist F_a, X\dist F \} \cr
&=\int \int \Gamma_a(dx,dy)\; \exp(-\lambda |y-x|), \quad \hbox{\rm
by Lemma 1;}\cr
&=\int \int \Gamma_a(dx,dy)\; \int_0^{\infty} \l^2 e^{-\l c}
(c-|y-x|)^+ \; dc \cr
&=\int_0^{\infty} \l^2 e^{-\l c} \psi(a,c) \; dc \cr}
$$
is thus a convex function of $a>0$, and is plainly symmetric in $a$.
Similarly, if we suppose that $V_n(\cdot)$ is symmetric, and convex in 
$\R^+$, then it is clear that $V_n$ must be decreasing
in $\R^+$, since it is bounded and convex. Next,
 for $a>0$ we have
$$\eqalign{
V_{n+1}(a)&\equiv \sup \{ \E\, V_n(Y - X) \; ;
 X\dist F,
Y\dist F_a \} \cr
&=\int \int \Gamma_a(dx,dy)\; V_n(|y-x|) \cr
&=\int \int \Gamma_a(dx,dy)\; \int_0^{\infty} V_n''(dc) \;
(c-|y-x|)^+  \cr
&=\int_0^{\infty} V_n''(dc)\;  \psi(a,c) \cr}
$$
is convex in $a>0$, and by induction $V_n$ is convex in $\R^+$
whatever $n$, and the optimal joint law of the steps of the 
random walk is given by the myopic policy.

\big
{\sl Proof of Lemma 2.} We prove the result firstly under the 
assumption that the distribution $F$ is strictly unimodal, 
that is, $F$ is strictly convex in $(-\infty,0)$ and strictly
concave in $(0,\infty)$. The choice of 0 as the mode is of course
an unimportant convention.  

For each $a>0$, there is for each $t>0$ a unique solution
$x = \xi(t,a)$ to the equation
$$
F(x)-F(x-a) = F(x+t) - F(x+t-a),
$$
because the function $x \mapsto F(x)-F(x-a)$ is strictly increasing
up to some point, then strictly decreasing. It is easy to verify that
$$
\xi(a,t)+a = \xi(t,a)+t\leqno(18)
$$
for all $a,t>0$.

Now from (13) we have
$$
\E\; \vp_c(Y-X) =\int_{-\infty}^{\infty} dt\;
\P [ (X,Y) \in (t-c,t]^2 ],
$$
and from (15) we see that when the optimal joint law $\Gamma_a$
is used this is equal to 
$$\eqalign{
\psi(a,c) &\equiv 
\E\; \vp_c(Y-X) \cr
&= 
\int_{-\infty}^{\infty} \;(F(s)-F(s-c))\wedge (F_a(s) - F_a(s-c))\; ds\cr
&=\int_{-\infty}^{\xi(a,c)+a} \;(F(s-a)-F(s-a-c)) \; ds
+\int_{\xi(a,c)+a}^{\infty} \; (\bar F(s-c) - \bar F(s))\; ds,\cr
&\quad\quad\quad\quad 
\quad\quad 
\quad\quad 
\hbox{\rm where $\bar F \equiv 1-F$;}\cr
&\quad\cr
&=\int_{\xi(a,c)-c}^{\xi(a,c)} F(s)\; ds
+ \int_{\xi(a,c)-c+a}^{\xi(a,c)+a} \bar F(s)\; ds\cr
&\quad\cr
&=\int_{\xi(c,a)-a}^{\xi(c,a)+c-a} F(s)\; ds
+ \int_{\xi(c,a)}^{\xi(c,a)+c} \bar F(s)\; ds\cr
&\quad\cr
&=\int_{\xi(c,a)-a}^{\xi(c,a)} F(s)\; ds
+ \int_{\xi(c,a)-a+c}^{\xi(c,a)+c} \bar F(s)\; ds\cr
&\quad\cr
&\quad\quad\quad\quad \quad\quad\quad\quad\quad\quad\quad
+\int_{\xi(c,a)}^{\xi(c,a)+c-a} F(s)\; ds
+ \int_{\xi(c,a)}^{\xi(c,a)+c-a} \bar F(s)\; ds\cr
& \quad\quad\quad\cr
&=\psi(c,a)+c-a.\cr}
$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\big
{\bf 4. Symmetric unimodal steps.} Throughout this section,
we assume that the step distribution $F$ is symmetric
and unimodal, with a density $f$. The case where $F$ has an atom at 0 is an
easy extension which we leave to the interested reader, in order to keep notation
simple.  We need a simple result firstly about convolutions of symmetric
unimodal distributions.
\med
LEMMA 3. {\sl Suppose that $F$ and $G$ are symmetric unimodal distributions
with densities $f$ and $g$ respectively. Then $F * G$ is again  symmetric unimodal.

\med
Proof. } In the case where $F$ is uniform on $[-b,b]$ we have that the density of $F*G$
is
$$
x \mapsto \int_{x-b}^{x+b} g(y) \; {dy \over 2b},
$$
which is clearly unimodal and symmetric. But the general symmetric unimodal density
$f$ can be expressed as a mixture of uniform distributions over symmetric intervals
of different lengths; if we define a probability measure on $(0,\infty)$
by $m(dx) = -2xf'(x)dx$, then
$$ 
       f(x) = \int_x^{\infty} \; {m(da) \over 2a}.
$$
The result follows.
\med
Thus the density $f_n$ of $S_n$ is symmetric about 0 and unimodal;
consequently,
$$\eqalign{
\norm  {\cal L} (\theta_n S) - {\cal L} (\theta_n S') \norm 
&=\norm  {\cal L} (S_n) - {\cal L} (S_n') \norm \cr
&=2 \P ( |S_n| < a/2 ). \cr}
$$
Indeed, 
$$\eqalign{
\norm  {\cal L} (S_n) - {\cal L} (S_n') \norm &=
\int | f(x-a/2)-f(x+a/2) | \; dx  \cr
&=2 \int_0^{\infty}(  f(x-a/2)-f(x+a/2) ) \; dx \cr
&=2 \, \P ( |S_n| < a/2 ). \cr}
$$
By what we have proved in Section 3, it must therefore be the case that
$$
\P ( |S_n| < a/2 ) = \P (T>n)
$$
for the CM-coupling. To see this,  we know already that the optimal coupling $\Gamma_
a$
is described by
$$\eqalign{
\P( X \in dx, Y=X)  &= [f(x) \wedge f(x-a)] dx \quad \hbox{\rm for $x \in \R;$}\cr
\P( X \in dx, Y=a-X)&= [f(x)-f(x-a)]dx \quad \hbox{\rm for $x \leq a/2.$}\cr}
$$
So if $h_n(a)\equiv \P[ T>n |  S_0=0, S_0'=a ]$ for $a>0$, we have the recursion
$$\eqalign{
h_n(a) &= \int_{-\infty}^{a/2}  \{ f(x)-f(x-a) \} h_{n-1}(a-2x) dx \cr
 &=\int_0^{\infty} h_{n-1}(t) \{ f({a-t \over 2}) - f({a+t \over 2}) \} {dt \over 2},
\cr
}$$
and if we extend the definition of $h_n$ to negative reals by $h_n(-y)=-h_n(y)$ for 
all
$y>0$, we have more simply for all real $a$
$$
h_n(a)=\int_{-\infty}^{\infty} h_{n-1}(t) f({a-t \over 2}) {dt \over 2}\; .
$$
Thus if $g(t) \equiv \half f(\half t)$, we have the convolution equation
$$
h_n = h_{n-1} * g, \quad \quad n \geq 1,
$$
which is solved by
$$
h_n(a) = (g^{*n} * h_0)(a) = \P[2S_n <a] -\P[2S_n >a]=\P[ |S_n| \leq a/2],
$$
as we were expecting.

As examples of this, we could take the symmetric stable
random walks. We may think of these as symmetric stable L\'evy
processes viewed at integer times
(see Chapter VIII of Bertoin [1] for more on stable processes).

If the step distribution is symmetric and stable with index $\alpha
\in (0,2]$, we shall have
$$
\P[T>n]=\P [ |S_n| \leq a/2 ] = \P [ |S_1| \leq \half a n^{-1/\alpha} ].
$$
For large $n$, this behaves like $n^{-1/\alpha} $, so for any $\alpha < 1$, the
coupling time would have a finite first moment!  Note that for $\alpha=2$, the
Gaussian case, we obtain the (typical) rate $O(n^{-1/2})$ of convergence 
for distributions
with finite second moments. To see why this is typical,
observe that the rate $O(n^{-1/2})$  can always be achieved for
any step distribution (see, for example, Lindvall \& Rogers [5]), and we have the
trivial bound
$$\eqalign{
\norm  {\cal L} (\theta_n S) - {\cal L} (\theta_n S') \norm &\geq | \P(S_n\leq a/2)
-\P(S'_n \leq a/2) |  \cr
&=\P ( |S_n| < a/2). \cr
}$$
This is $O(n^{-1/2})$ by a local version of the Central Limit Theorem provided
the distribution is non-lattice; see, for example, Theorem 2.5.4 in Durrett [3].

\vfill\eject

\centerline{\bf REFERENCES}
\med
[1] BERTOIN, J.. {\sl L\'evy Processes}, Cambridge Univ. Press, Cambridge, 1996.
\med
[2] CUESTA-ALBERTOS, J.~A., MATRAN, C., RACHEV, S.~T. \& 
R\"USCHENDORF, L.. Mass transportation problems in probability 
theory, {\sl Math. Scientist, \/ \bf 21}, 34--72, 1996.
\med
[3] DURRETT, R.. {\sl Probability: Theory and Examples}, Wadsworth \& Brooks/Cole,
Belmont, Ca., 1991.
\med
[4] GOLDSTEIN, S.. Maximal coupling, {\sl Z. Wahrscheinlichkeitsth.
verw. Gebiete \/ \bf 46}, 193--204, 1979.
\med
[5] LINDVALL, T.. {\sl Lectures on the Coupling Method}, J. Wiley \&
Sons, New York, 1992.
\med
[6] LINDVALL, T., \& ROGERS, L.~C.~G.. Coupling of multidimensional
diffusions by reflection, {\sl Ann. Probability, \/ \bf 14}, 
860--872, 1986.
\med
[7] RACHEV, S.~T.. The Monge-Kantorovich mass transference problem and its
stochastic applications, {\sl Th. Prob. Applications, \/ \bf 29}, 647--676,
1985.
\med
[8] THORISSON, H.. On maximal and distributional coupling, {\sl
Ann. Probability, \/ \bf 14}, 873--876, 1986.
\big
\big
\small
\hfill\hbox{School of Mathematical Sciences}
\small
\hfill\hbox{University of Bath}
\small
\hfill\hbox{Bath BA2 7AY}
\small
\hfill\hbox{Great Britain}


\vfill
\eject
\epsfxsize=6 in
%\epsfbox{cppic.ps}
\bye
