Handout on Transience of a 3D
Random Walk
Problem. Consider a three-dimensional
symmetric
simple random walk Zn which goes up, down, left, right,
forward or backward with equal probabilities 1/6. Prove that it is
transient.
Solution
Suppose not, i.e. Zn is recurrent. Then it must
eventually hit the origin, point (0,0,0)
with probability 1, regardless where it starts, that is for any Z0. Fix some number r>0 and consider another
walk, Xn, which coincides with Zn until the moment when it hits
the ball B(r) of radius r around the origin (0,0,0). However, when the
walk X hits the ball B(r), it stops forever. Let T be the stopping time when X hits B(r). Then, since Z is recurrent, T must be finite a.s., since
for Zn to get to (0,0,0) it must enter B(r) at some point of time.
Suppose that I managed to find a non-negative function g(v), v in Z3, such that
- minimum of g(v)
for all v in B(r) is positive, say larger
than some epsilon>0
- there is a point w
in Z3, outside of B(r), such g(w)<epsilon
- Yn=g(Xn) is a supermartingale with
respect to the sequence X1, X2 ,...
Then we will get a contradiction. Indeed, since P(T is finite)=1, I can apply the Optional Stopping Theorem for
supermartingales to Yn,
It yields E(YT)<=Y0
Now start the walk at X0=w. Since XT is in B(r), YT=g(XT)>epsilon, hence E(YT)>epsilon.
On the other hand, Y0=g(w)<epsilon.
Thus epsilon<E(YT)<=Y0<epsilon which is
impossible.
Now the only thing to finish the proof, is to find such a function.
For any u=(x,y,z) let |u|=(x2+y2+z2)½ be
the distance from v to
the origin.
Now let us try g(u)=1/|u|a where a>0,
with convention that g(0)=1.
It satisfies the first two conditions I mentioned before; now I will
show that when 1>a>0, Yn is indeed a supermartingale,
provided r>0 is large enough.
That is, we need to establish that E(Yn+1|Xn,Xn-1,...,Xn+1)<=Yn i.e. E(Yn+1|Xn)<=Yn=g(Xn) (since Markov), which is
equivalent to E(g(Xn+1) | Xn=u)<=g(u) which in turn is equivalent
to E(g(Xn+1) - g(u) | Xn=u)<=0.
Suppose |u|>r
(otherwise, as we in the ball B(r)
it is trivial that E(g(Xn+1) | Xn=u)=g(u) since Xn+1=Xn)
Set u=(x,y,z) , and let
us compute
E (g(Xn+1) - g(u) | Xn=u)= 1/6 [g((x+1,y,z)-g(u)]+1/6 [g((x-1,y,z)-g(u)]+1/6 [g((x,y+1,z)-g(u)]+1/6 [g((x,y-1,z)-g(u)]+1/6 [g((x,y,z+1)-g(u)]+1/6 [g((x,y,z-1)-g(u)]
= 1/6 [((x+1)2+y2+z2)-a/2-(x2+y2+z2)-a/2]+1/6 [((x-1)2+y2+z2)-a/2-(x2+y2+z2)-a/2]+
+...+1/6 [(x2+y2+(z-1)2)-a/2-(x2+y2+z2)-a/2]
=1/6 ×|u|-a {[(1+(2x+1)/|u|2)-a/2-1]+[(1+(-2x+1)/|u|2)-a/2-1]+[(1+(2y+1)/|u|2)-a/2-1]
+[(1+(-2y+1)/|u|2)-a/2-1]+[(1+(2z+1)/|u|2)-a/2-1]+[(1+(-2z+1)/|u|2)-a/2-1]}
since (1+z)-a/2=1- a/2 z +a(a+2)/8
z2 + O(z3) by Taylor series
=1/6 ×|u|-a {[-a/2×(2x+1)/|u|2+a(a+2)/8×(2x+1)2/|u|4]+...+[-a/2×(-2z+1)/|u|2+a(a+2)/8×(-2z+1)2/|u|4]+O(|u|-3)}
=1/6 ×|u|-a {(-a/|u|2+a(a+2)×(x2+1)/|u|4)+(-a/|u|2+a(a+2)×(y2+1)/|u|4)+(-a/|u|2+a(a+2)×(z2+1)/|u|4)+O(|u|-3)}
=a/6
×|u|-a {(-3/|u|2+(a+2)×(x2+y2+z2)/|u|4)+O(|u|-3)}
=a/6 ×|u|-a-2 {(-3+(a+2))+O(|u|-3)}
since |u|2=x2+y2+z2
=a/6
×|u|-a-2 {(a-1)+O(|u|-3)}<0
when a<1 and |u| is sufficiently large,
say larger than some r. Now
this r
is exactly the radius of the ball I mentioned in the beginning of the
proof! Hence Yn=g(Xn) is a supermartingale and the
proof is finished.
Note: in fact, if a=½,
it is sufficient to choose r=3.