Simple Random Walk

Let

X_{1}, X_{2}, \dots

be independent random variables with

P (X_{i} = 1) = p, P (X_{i} = - 1) = 1 - p .

The process

S_{0} = a

and

S_{n} = a + \sum_{k = 1}^{n} X_{k}

is a simple random walk starting at

a

Symmetric Simple Random Walk

A simple random walk is symmetric if

p = \frac{1}{2}

Spatial Homogeneity

For a simple random walk,

P (S_{n + 1} = y + 1 | S_{n} = y) = p, P (S_{n + 1} = y - 1 | S_{n} = y) = 1 - p,

and these probabilities do not depend on

y

The next position is

S_{n + 1} = S_{n} + X_{n + 1}

, and

X_{n + 1}

has the same distribution at every site.

Temporal Homogeneity

For a simple random walk, the one-step transition probabilities do not depend on the time

n

The increments

X_{1}, X_{2}, \dots

are identically distributed.

Markov Property

A simple random walk satisfies

P (S_{n + 1} = z | S_{0}, \dots, S_{n}) = P (S_{n + 1} = z | S_{n}) .

Once

S_{n}

is known, the next state is determined by the fresh increment

X_{n + 1}

, which is independent of the previous increments.

Position Distribution

S_{0} = 0

for a simple random walk, then

P (S_{n} = k) = (\binom{n}{\frac{n + k}{2}}) p^{\frac{n + k}{2}} {(1 - p)}^{\frac{n - k}{2}}

whenever

n + k

is even and

| k | \leq n

. Otherwise

P (S_{n} = k) = 0

To end at

k

, the walk must make

u

upward steps and

d

downward steps with

u + d = n

and

u - d = k

. Thus

u = \frac{n + k}{2}

and

d = \frac{n - k}{2}

. Choose which

u

of the

n

increments are upward.

Reflection Principle

For a symmetric simple random walk starting at

0

, paths from

0

b > 0

that hit level

a > 0

before time

n

are in bijection with paths from

0

2 a - b

n

steps.

Reflect the portion of the path after its first visit to

a

. This changes the endpoint from

b

2 a - b

, and applying the same reflection again recovers the original path.

Gamblers Ruin Probability

Let

S_{n}

be a simple random walk on

{0,1, \dots, N}

stopped when it hits

0

N

, and suppose

S_{0} = i

. If

p \neq \frac{1}{2}

, then

P_{i} (hit N before 0) = \frac{1 - {(\frac{1 - p}{p})}^{i}}{1 - {(\frac{1 - p}{p})}^{N}} .

p = \frac{1}{2}

, then this probability is

\frac{i}{N}

Let

h (i)

be the probability of hitting

N

before

0

from

i

. Then

h (0) = 0

h (N) = 1

, and

h (i) = p h (i + 1) + (1 - p) h (i - 1) .

Solving this second-order difference equation gives the displayed formula; in the symmetric case the solution is linear.

Symmetric Gamblers Ruin Bankruptcy Probability

In the symmetric case, a walk starting at

i \in {0, \dots, N}

hits

0

before

N

with probability

1 - \frac{i}{N} .

This is the complement of the probability of hitting

N

before

0