Trapped or Free: Understanding Random Walk

Dynamics

Aritrabha Majumdar(BMAT2311)

[Link] (2nd year)

Indian Statistical Institute, Banglaore Center

Notes : Talk on Random Walk 1

1 Basic Setup

We consider the line of integers, namely Z. Now, we consider a bug is walking on this line. Say, as an
example, the bug starts at the origin, and moves to 1, then to 2, then to 3, then to 2, then to 1, then to 2
again, then to 1, then to origin, then to −1, then to origin again. Taking each stationary time increment
as 1, we obtain the graph given below.

Now, we would like to look into a more formal definition of the mess hapenning. We fix N ∈ N, and we
say the configuration space is given by the following binary sequence of length N

ΩN = ω = (ω1 , . . . , ωN ) ∈ {−1, +1}N

Now we write
Xk (ω) = ωk
To denote the position of the random walk at time k. The position of the random walk after n steps (or
after time n) is
X
n
Sn (ω) = Xk (ω), 1 ≤ n ≤ N, S0 (ω) = 0
k=1

Thus ∀ω ∈ ΩN , we obtain a trajectory (Sn )Nn=0 , which we call a path. As a probability distribution on
ΩN , we take the uniform distribution, i.e.

|A|
P(A) = , A ⊆ ΩN
2N
Now we give a formal definition.

Definition: The sequence of rankdom variables (Sn )N n=0 on finite probability space (ΩN , P) is known
as a Simple Random Walk of length N starting
` at 0. Note that it has independent increments. Even, we
can have a strongr condition, that is, Xm Xn , m, n ∈ N.
Notes : Talk on Random Walk 2

2 Distribution of Sn and Probability of returning to the origin

We want to find out P(Sn = x). So we write

 
1
Xn ∼ Reidemester
2
 
Xn + 1 1
=⇒ ∼ Ber
2 2
 
Sn + n 1
=⇒ ∼ Bin n,
2 2
2n


n+x
=⇒ P(Sn = x) = 2

2n
Observe that the distribution is symmetric around origin. Moreover, the maximal probability is achieved
at the middle, or when x = 0 and n is even. We have
 
2n −2n
P(S2n = 0) = 2
n

n √
Now we apply Stirling’s Approximation n! = ne 2πn for large n, and obtain
1
P(S2n = 0) ∼ √
πn
Now, is it really a coincidence that we obtain the mode when the random walk returns to the origin, or
doees it have deeper significance? We will observe them at the following sections.

3 Random Walk in Higher Dimensions

Now we extend the formal definition of teh random walk on Z to random walk on 𝟋d , d ∈ N.
We fix d ∈ N. For x ∈ Zd , we write v
u 
u Xd
u
||x|| = t x2j 
j=1

For given N ∈ N, we have


ΩN = ω = (ω1 , . . . , ωN ) | ωk ∈ Zd , |ωk | = 1, ∀1 ≤ n ≤ N
In the similar fashion as we did before, we can define Xk (ω) = ωk , 1 ≤ k ≤ N , and
X
n
Sn (ω) = Xk (ω), 1 ≤ n ≤ N, S0 (ω) = 0.
k=1
|A|
We stil have an uniform distribution; i,e for A ⊆ ΩN , P(A) = (2d) −N . We also observe that Sn in this

case is a d dimensional random vector.

 
(1)
Sn
 . 
Sn =  
 ..  , 0 ≤ n ≤ N, Sn ∈ Z, j = 1, 2, . . . , d
(j)

(d)
SN
Now, George Polya showed that for random walk in Z, We have
 d
P(Sn = 0) = Θ n− 2
Which holds when d = 1.
Notes : Talk on Random Walk 3

4 Recurrence and Transience

Let a ∈ N and we define σa = min{n ∈ N | Sn = a} is the first hitting time of a after time 0. We define
a random walk is recurrent if P(σ0 < ∞) = 1. Otherwise, it is transient.

4.1 An Important Result

We start by claiming
X
n
P(Sn = 0) = P(σ0 = i)P(Sn−i = 0) , n ∈ N
i=1

Now we take z ∈ [0, 1] and consider two generating functions

∞
X ∞
X
G(0, z) = z n P(Sn = 0) F (0, z) = z n P(σ0 = n)
n=0 n=0

The motivation of the function G is obtained from Random Walk Green’s Function. This is defined by
∞ ∞ ∞
!
X X
X
G(x, 1) = P(Sn = x) = E 1{Sn =x} = E 1Sn =x
n=0 n=0 n=0

So it gives us expected number of visits to x. Observe {σ0 = 0} = ϕ and P(S0 = 0) = 1. Now

X XX
n
G(0, z) = 1 + z n P(Sn = 0) = 1 + z i P(σ0 = i)z n−i P(Sn−i = 0)
n∈N n∈N i=1
X X
=1+ z P(σ0 = i)
i
z P(Sj = 0) = 1 + F (0, z)G(0, z)
j

i∈N j∈N0

−1
This can be rewritten as F (0, z) = 1 − G(0, z) . Now we have some interesting observations.

X
N
1
P(σ0 = n) = F (0, 1) = lim F (0, z) = 1 − lim
n=1
z↑1 z↑1 G(0, z)

If we have
∞
X
G(0, 1) = P(Sn = 0) < ∞
n=0

Then clearly F (0, 1) < ∞, i.e the walk is transient. On the other hand, if
∞
X
G(0, 1) = P(Sn = 0) = ∞
n=0

Then we fix ε > 0 and Nε ∈ N. such that

X
N
2
P(Sn = 0) ≥
n=0
ε

Then for z sufficiently close to 1, we have z n ≥ 12 , which gives

X
N
1
z n P(Sn = 0) ≥
n=0
ε
Notes : Talk on Random Walk 4

. So we have
1 1
≤ PN ≤ε
n=0 z P(Sn = 0)
G(0, z) n

Since our ε is arbitray, we have

lim G(0, z)−1 = 0
z↑1

So, F (0, 1) = 0, and the walk is recurrent.

4.2 Recurrence in 1D

As we have already seen,

1
P[S2n = 0] ∼ √
πn
Now
∞
X 1
√ =∞
n=0
πn
Hence, the random walk is indeed recurrent.

4.3 Recurrence in 2D

We could have done this in the traditional way we have already seen, but here we introduce even sleeker
proof for 2D. Let us consider a corner walk, in which each move adds with equal probability one of
{(1, 1), (−1, −1), (1, −1), (−1, 1)} to the current location. The advantage of this walk is it is independent
in each coordinate and they resemble simple random walk in Z. So
n o n o c
(1) (2)
P{X2t = (0, 0)} = P(0,0) X2t P(0,0) X2t ∼
n
Now, the random walk in Z2 is the 45 degrees rotation of the corner walk. Now, if we consider Y = AX,
(1)
then jacobian of the inverse transform has determinant 1 , and it is pretty easy to observe that Y2t and
(2) P∞ 1
Y2t are indeed independent. As we know n=1 n = ∞, the random walk is recurrent.

In general, what we have is

∞
X ∞
X c
P(Sn = 0) = d
n=0 n=0 n2
This sum is divergent iff d = 1, 2, i.e the random walk is recurrent when d = 1, 2 and transient when d ≥ 3.
Below, we present a more rigorous proof of this, which does not involve Polya’s Recurrence Theorem.

4.4 Approaching the Problem using Fourier Analysis

We know that a finite measure µ on Zd uniquely determines its characteristic function

X
ϕµ (k) = E eikx = eik·x µ({x}), x ∈ Zd
x∈Zd
Notes : Talk on Random Walk 5

Pd
Here k · x = i=1 ki xi is the standard inner product. Now, we are willing to retrieve µ ({x}). So we use
Fourier Inversion Formula

Z
1
µ({x}) = e−ik·x ϕµ (k)dk
(2π)d [−π,π)d

Now, we already know that

1
µ(x) = 1{|x|=1} , x ∈ Zd
2d

Via symmetry: we derive an useful representation of ϕµ (k)

1X
d
ϕµ (k) = cos (kj )
d j=1

As X1 , . . . , Xn are iid random variables; we apply The convolution rule of characteristic function and
obtain

! Z
X
n
1
P (Sn = x) = P Xi = x = e−ik·x (ϕ(k))n dk
i=1
(2π)d [−π,π)d

∴ For z ∈ [0, 1]; we have

∞
X ∞
X Z
1
G(0, z) = z P (Sn = 0) =
n
d
z n (ϕ(k))n dk
n=0 n=0
(2π) [−π,π)d
Z
1 dk
=
(2π) [−π,π)d 1 − zϕ(k)
d

As limz↑1 G(0, z) = G(0, 1); Hereby we com say

Z
dk
G(0, 1) < ∞ ⇐⇒ <∞
(−π,π)d 1 − ϕ(k)

Now, we use a bound for (1 − cos k) ts obtain our desired result.

2kj2 ki2
⩽ 1 − cos k j ⩽
π2 22
Xd 2
2kj X d Xd
kj2
=⇒ ⩽ d − cos k j ⩽
j=1
π2 j=1 j=1
2

2 X 2 1 X k2 2
d d
=⇒ k ⩽ 1 − ϕ(k) ⩽ k
dx2 j=1 j 2d j=1 2 j
Notes : Talk on Random Walk 6

dπ 2 1 1 1
=⇒ ⩾ ⩾ 2d
2 ∥k∥2 1 − ϕ(k) ∥k∥2
Z Z Z
dA2 dk d(k dk
=⇒ ⩾ ⩾ 2d
2 [−π,π]d ∥k∥2 [−π,π) d 1 − ϕ(k) [−π,π) d ∥k∥ 2

Now, f (k) = 1
∥k∥2 is a function on R+ and f : R+ → [0, ∞). So, we can write

Z Z
dk d−1

π 1 d−1
= 2 Vol S r dr
[−π,π)d ∥k∥
2 2
0 r
Z

π π d−3
= 2 Vol S d−1 0 r dr
Z 0
Z
dk
2 π d−3
∴ ⩽ d Vol s d−1
π r dr
[π,π)d 1 − ϕ(k) 0

This is enough to claim that G(0, 1) < ∞ ⇐⇒ d ⩾ 3

On the other hand; we use.

Z Z
dk
π
⩾ 4d Vol S d−1 rd−3 dr
[−π,π)d 1 − ϕ(k) 0

To claim G(0, 1) = ∞ ⇐⇒ d = 1, 2

5 Conclusion

As we explored today, recurrence demonstrates how some systems, no matter how random, have a certain
inevitability in their behavior, while transience highlights the unpredictable journey where some paths
are taken once and never again. These concepts extend far beyond mathematics—they represent a way
of thinking about dynamics, movement, and the probability of return in many real-world systems. So to
conclude this talk, i just want to restate a famous quote by Shizuo Kakutani

”A drunk man will find his way home, but a drunk bird may get lost forever.”