Random walk
Definition of Random walk
A random walk is the process by which randomly-moving objects wander away from where they
started. That is random walk is a process, a model or a rule to generate path sequence of random
motion. The mathematical formalization of a trajectory that consists of taking successive “random”
steps is known as a random walk. Random walk is sometimes called the Drunkard’s walk because
each step is made without thought and no direction is favored.
A simple random walk would be that on the integers, which starts at time zero (t=0), S0 = 0 and at
each step moves by 1 or −1 with equal probability (e.g. flips of an unbiased coin). To define this
walk formally, take independent random variables xi , each of which is 1 with probability 1/2 and
−1 with probability 1/2, and set 𝑆𝑛 = ∑𝑛𝑖=1 𝑥𝑖 . This sequence Sn is called the simple random walk
on integers.
One dimensional random walk
𝑙𝑖 = 𝑑𝑖𝑠𝑝𝑙𝑎𝑐𝑒𝑚𝑒𝑛𝑡 𝑜𝑓 𝑖 𝑡ℎ 𝑠𝑡𝑒𝑝 = ±𝑙
𝑥 = 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑡𝑟𝑎𝑣𝑒𝑙𝑙𝑒𝑑 𝑏𝑦 𝑅𝑎𝑛𝑑𝑜𝑚 𝑊𝑎𝑙𝑘𝑒𝑟 𝑎𝑓𝑡𝑒𝑟 𝑁 𝑠𝑡𝑒𝑝𝑠
𝑁
𝑥 = 𝑙1 + 𝑙2 + 𝑙3 + ⋯ + 𝑙𝑁 = ∑ 𝑙𝑖
𝑖=1
𝑥 = 𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑥 𝑓𝑜𝑟 𝑚𝑎𝑛𝑦 𝑖𝑛𝑑𝑒𝑝𝑒𝑛𝑑𝑒𝑛𝑡 𝑤𝑎𝑙𝑘𝑒𝑟𝑠
𝑥 = 〈𝑙1 + 𝑙2 + 𝑙3 + ⋯ + 𝑙𝑁 〉 = 〈𝑙1 〉 + 〈𝑙2 〉 + 〈𝑙3 〉 + ⋯ + 〈𝑙𝑁 〉 = 0
Equally probable to land Right/Left
Mean-Square (Root-Mean -Square) Displacement from Starting Point
𝑁
𝑥 = (𝑙1 + 𝑙2 + 𝑙3 + ⋯ + 𝑙𝑁 )(𝑙1 + 𝑙2 + 𝑙3 + ⋯ + 𝑙𝑁 ) = ∑ 𝑙𝑖 2 + 2 ∑ 𝑙𝑖 𝑙𝑗
2
𝑖=1 𝑖≠𝑗
Random walk Page 1
𝑁
〈𝑥 2 〉 = ∑〈𝑙𝑖 2 〉 + 2 ∑〈𝑙𝑖 𝑙𝑗 〉
𝑖=1 𝑖≠𝑗
〈𝑙𝑖 2 〉 = [(+𝑙 ∙ +𝑙) + (−𝑙 ∙ −𝑙)] = 𝑙 2
〈𝑙𝑖 𝑙𝑗 〉 = [(+𝑙 ∙ +𝑙) + (+𝑙 ∙ −𝑙) + (−𝑙 ∙ +𝑙) + (−𝑙 ∙ −𝑙)] = 0
〈𝑥 2 〉 = 𝑁𝑙 2
√〈𝑥 2 〉 = 𝑅𝑜𝑜𝑡 𝑚𝑒𝑎𝑛 − 𝑠𝑞𝑢𝑎𝑟𝑒 𝑑𝑖𝑠𝑝𝑙𝑎𝑐𝑒𝑚𝑒𝑛𝑡
= √𝑁 𝑙
displacement =(N)1/2 x step length
Question: Find the number of steps taken by a drunk-man to reach his car which is at 10 steps
straight-ahead from his starting position. (T U [Link]. 4th year 2076)
Question: A drunk person is advancing randomly with equal step size of 0.5 meter. How many
numbers of steps are needed to reach his home, which at 120 meter far? (T U [Link]. 4th year 2074)
One dimensional random walk
It is easy to understand that the number of different walks of n steps where each step is +1 or -1 is
clearly 2n. For the simple random walk, each of these walks is equally likely.
The random walk formalism
Consider a particle (or a drunkard person) moving in 1 dimension in steps of length s, with
probability p of stepping to the right & q = 1 – p of stepping to the left.
After N steps, the particle is at position:
x = ms (- N ≤ m ≤ N). (m is displacement)
Random walk Page 2
Let n1 be the number of steps to the right (of N), n2 be the number of steps to the left.
Clearly, N = n1 + n 2 (1)
Clearly also, x ≡ ms = (n1 - n2)s or, m = n1 - n 2 (2)
Combining (1) & (2) gives m = 2n1 – N (3)
Thus, if N is odd, so is m and if N is even, so is m.
The probability of a given particular sequence of N steps, with n1 steps to the right and n2=N-n1
steps to the left, is given by the product
(p.p.p….p.p.p) (q.q.q…..q.q.q) = pn1 qn2
The number of distinct possibilities is the same as counting the number of distinct ways we can
place N objects, n1 of one type & n2 of another in N = n1 + n2 places:
1st place: Can be occupied any one of N ways
2nd place: Can be occupied any one of N - 1 ways
3rd place: Can be occupied any one of N - 2 ways
…………………………………….
(N – 1)th place: Can be occupied only 2 ways
Nth place: Can be occupied only 1 way
All available places can be occupied in:
N(N-1)(N-2)(N-3)(N-4)·····(3)(2)(1) ≡ N! Ways
N! = “N-Factorial”
All n1! possible permutations of the 1st type of object lead to exactly the same N! possible
arrangements of the objects. Similarly, all n2! possible permutations of the 2nd type of object also
lead to exactly the same N! arrangements.
So, we need to divide the result by n1!n2!
So, the number of distinct ways in which N objects can be arranged with n1 of the 1st type & n2 of
the 2nd type is ≡ N!/(n1!n2!)
Which is the number of distinct ways of taking n1 right steps (out of total N).
The probability WN(n1) of taking N steps, with n1 to the right & n2 = N - n1 to the left is
WN(n1) = [N!/(n1!n2!)]pn1qn2
Or, WN(n1) = [N!/{n1!(N – n1)! }]pn1(1-p)n2
Often, this is written as
𝑵
WN(n1) = ( ) pn1qn2
𝒏𝟏
Random walk Page 3
This probability distribution is called the Binomial Distribution. We really want the probability
PN(m) that x = ms after N steps. This really the same as WN(n1) if we change notation:
PN(m) = WN(n1). But m = 2n1 – N, so n1 = (1/2)(N + m) &
n2 = N - n1 =N-(1/2)(N + m) = (1/2)(N - m). So the probability PN(m) that
x = ms after N steps is:
PN(m) = {N!/([0.5(N + m)]![0.5(N – m)!]}p0.5(N+m)(1-p)0.5(N-m)
For the common case of p = q = ½, this is:
PN(m) = {N!/([0.5(N + m)]![0.5(N – m)!]}(½)N
This is the usual form of the Binomial Distribution
As a trivial example, suppose that
p = q = ½, N = 3 steps:
P3(m) = {3!/[0.5(3+m)!][0.5(3-m)!](½)3 n n m=n –n
1 2 1 2
So 3 0 3
P3(3) = P3(-3) = (3!/[3!0!](⅛) = ⅛ 2 1 1
P3(1) = P3(-1) = (3!/[2!1!](⅛) = ⅜ 1 2 -1
0 3 -3
Drunkard's Walk
Question: A drunk starts out from a lamppost in the middle of the street, taking steps of equal
length either to the right or to the left with equal probability. What is the probability that the man
will again be at the lamppost after taking N steps if
a) N is even
Solution: Now, the probabilities p = q = 1/2 and m = 0 in the binomial distribution PN(m). The end
𝑁! 1
result is simply PN(m = 0) = 𝑁 2 2𝑁
([ ]!)
2
b) N is odd?
Solution: PN (m = 0) = 0, with even number of steps the location m is also even.
One-dimensional discrete case
Consider the sum of n independent identically distributed (i.i.d.) random variables xi,
Sn ≡ x1 + x2 + · · · + xn. (1)
In the simplest case all the steps are of size s, so xi= ± s.
Here Sn ≡ x(nΔt) can be regarded as the sum of n random variables or as the position of a single
walker at time t = nΔt, where n is the number of steps performed, and Δt the time required to
perform one step. Identically distributed random variables {xi} are characterized by moments
𝐸{𝑥𝑖𝑛 } that do not depend on i.
Random walk Page 4
The first and second moments for such a process are
∑ 𝑥𝑖 0 ∑ 𝑥𝑖2 ∑(±𝑠)2 𝑛𝑠2
E{xi} = = 𝑛 = 0 and 𝐸{𝑥𝑖2 } = ∑(𝑥𝑖 )2 = = = = 𝑠2 (2)
𝑛 𝑛 𝑛 𝑛
This can be expressed as
E{xixj} = δij s2 (3)
Where δij= 1 if i=j
0 otherwise
From (1)–(3), it follows that
E{x(nΔt)} = ∑𝑛𝑖 𝐸{𝑥𝑖 } = 0
And
∑𝑛𝑖 ∑𝑛𝑗 𝐸{𝑥𝑖 𝑥𝑗 } = ∑ 𝐸{𝑥𝑖2 } = 𝑛𝑠 2
Thus the variance of sn increases linearly with number of steps.
TU [Link]. 4th year 2073 (Model 2072)
Consider a random walk performed by a drunk-person with equal step 1. Calculate mean and
variance -of the steps
Let us consider that drunk-person begins from the origin and takes equal step 1. Consider the
idealized example of random walk for which the walker is restricted to a line (a one dimensional
random walk). Let the unit steps are taken to the right with probability p and to the left with
probability q (= 1 - p). (Assume independent movements).
Let us associate a variable Xi with the ith step defined as follows
Xi = + 1, if the ith step is towards the right,
= - 1, if the ith step is towards the left.
Then S = X1 + X2 + …. + Xn = ∑ Xi, represents the random distance moved from origin after n
steps.
E (Xi) = 1 x P + (-1) x q = p – q
E (Xi2) = 12 x P + (-1)2 x q = p + q = 1
Var (Xi) =E (Xi2)-[E(Xi)]2 = 1- (p-q)2 = (q + p)2- (p -q)2 = 4 pq
The continuous limit
The continuous limit of a random walk may be achieved by considering the limit n → and ∆t→ 0,
such that t ≡ ∆t n is finite. Then
𝑠2
𝐸{𝑥 2 (𝑡)} = 𝑛𝑠 2 = 𝑡
∆𝑡
To have consistency in the limits n → or ∆t→ 0 with s2 =D∆t, it follows that 𝐸{𝑥 2 (𝑡)} = 𝐷𝑡
Random walk Page 5
The linear dependence of the variance 𝑥 2 (𝑡) on t is characteristic of a diffusive process, and D is
termed the diffusion constant.
This stochastic process is called a Wiener process (or Brownian motion). It is assumed that for
n → or ∆t→ 0, the stochastic process x(t) is a Gaussian process. The equivalence
'random walk' ≡ 'Gaussian walk'
How does the shape of P[ x(n∆t )] change with time?
Under the assumption of independence,
P[ x(2∆t )]=P(x1) ⊗ P(x2)
[Convolution ( ⊗) is a mathematical operation on two functions (f and g) to produce a third
function that expresses how the shape of one is modified by the other.]
A delta distribution
uniform pdf with zero
mean and unit standard deviation,
Gaussian with zero
mean and unit standard deviation,
Lorentzian pdf with
Fig. 1 unit scale factor
A delta distribution
Uniform pdf with zero
Mean and unit standard
deviation,
Gaussian with zero
Mean and unit standard
deviation,
Lorentzian pdf with
unit scale factor
Fig. 2 Behavior of P(Sn) for i.i.d. random variables with n = 1, 2
for the pdfs of Fig. 1.
Random walk Page 6
Fig. 1 shows four different pdfs P(x) : (i) a delta distribution, (ii) a uniform distribution, (iii) a
Gaussian distribution, and (iv) a Lorentzian (or Cauchy) distribution. When one of these
distributions characterizes the random variables xi, the pdf P(Sn) changes as n increases (Fig.2).
From Fig. 2 it is seen that the functions P(Sn) for the delta and for the uniform distribution change
both in scale and in functional form as n increases, while the Gaussian and the Lorentzian
distributions do not change in shape but only in scale (they become broader when n increases).
When the functional form of P(Sn) is the same as the functional form of P(xi), the stochastic process
is said to be stable. Thus Gaussian and Lorentzian processes are stable distribution.
Moment generating function:
Let X denotes a random variable with probability density function f(X) if continuous (probability
mass function p(x) if discrete)
Then
mX(t) = the moment generating function of X
=E(etX)
∞
= ∫−∞ 𝑒 𝑡𝑥 𝑓(𝑥)𝑑𝑥 𝑖𝑓 𝑋 𝑖𝑠 𝑐𝑜𝑛𝑡𝑖𝑛𝑢𝑜𝑢𝑠
∑ 𝑒 𝑡𝑥 𝑝(𝑥) 𝑖𝑓 𝑋 𝑖𝑠 𝑑𝑖𝑠𝑐𝑟𝑒𝑡𝑒
L’Hopital’s Rule
𝑓(𝑥) 0 ∞ −∞ −∞ ∞
If f and g are differentiable functions and if lim𝑥→𝑐 is or or or or , then
𝑔(𝑥) 0 ∞ −∞ ∞ −∞
𝑓(𝑥) 𝑓′(𝑥)
lim𝑥→𝑐 𝑔(𝑥) = lim𝑥→𝑐 𝑔′(𝑥) (as long as the limit on the right exists or is infinite.)
Central limit theorem
The central limit theorem states that the sum of a number of independent and identically distributed
(i.i.d.) random variables with finite variances will tend to a normal distribution as the number of
variables grows.
A theorem which states that for any population with mean μ and finite standard deviation σ, the
𝜎
distribution of sample means for sample size n will have a mean μ and standard deviation 𝑛 and
√
will approach a normal distribution as n approaches infinity.
If x1, x2, ….., xn is a sample from a distribution with mean μ, and standard deviation σ then if n is
large 𝑥̅ = 𝑡ℎ𝑒 𝑠𝑎𝑚𝑝𝑙𝑒 𝑚𝑒𝑎𝑛 has a normal distribution with mean 𝜇𝑥̅ = 𝜇 and variance
𝜎2 𝜎
𝜎𝑥̅2 = (Standard deviation 𝜎𝑥̅ = )
𝑛 √𝑛
Random walk Page 7
Proof: (use moment generating functions)
We will use the following fact:
Let
m1(t), m2(t), …
denote a sequence of moment generating functions corresponding to the sequence of distribution
functions:
F1(x), F2(x), …
Let m(t) be a moment generating function corresponding to the distribution function F(x) then if
lim mi t m t for all t in an interval about 0.
i
Then lim Fi x F x for all x.
i
Let x1, x2, … denote a sequence of independent random variables coming from a distribution with
moment generating function m(t) and distribution function F(x).
Let Sn= x1+ x2 +……..+ xn then
𝑚𝑆𝑛 (𝑡) = 𝑚𝑥1+𝑥2+⋯+𝑥𝑛 (𝑡) = 𝑚𝑥1 (𝑡) 𝑚𝑥2 (𝑡) … . 𝑚𝑥𝑛 (𝑡) = [𝑚(𝑡)]𝑛
𝑥1 +𝑥2 +⋯+𝑥𝑛 𝑆𝑛
Now 𝑥̅ = =
𝑛 𝑛
𝑡 𝑡 𝑛
𝑚𝑥 (𝑡) = 𝑚( 1 )𝑆 (𝑡) = 𝑚𝑆𝑛 ( ) = [𝑚 ( )]
𝑛 𝑛 𝑛 𝑛
Let
𝑥̅ − 𝜇 √𝑛 𝜇 √𝑛
𝑧= = 𝑥̅ −
𝜎/√𝑛 𝜎 𝜎
[If X be a random variable with moment generating function mX(t). Let Y = bX + a
Then mY(t) = mbX + a(t) = E(e [bX + a]t) = eatmX (bt) ]
then
n
−
√n μ t √𝑛𝑡 √n μ t √𝑛𝑡
mz (t) = m √𝑛 𝜇√𝑛 (t) =e σ mx̅ ( ) = e− σ [m ( )]
(
𝜎
𝑥̅ −
𝜎
) 𝜎 𝜎𝑛
And
√n μ t 𝑡
ln [mz (t)] = − + n ln [m ( )]
σ 𝜎 √𝑛
Let
𝑡 𝑡 𝑡2
𝑢= or √𝑛 = and 𝑛 =
𝜎 √𝑛 𝑢𝜎 𝑢2 𝜎 2
Then
√n μ t 𝑡
ln [mz (t)] = − + n ln [m ( )]
σ 𝜎 √𝑛
Random walk Page 8
𝑡 2𝜇 𝑡2
= − 2 + 2 2 ln[m(𝑢)]
𝑢 𝜎 𝑢 𝜎
𝑡 2 ln[m(𝑢)] − μu
= 2
𝜎 𝑢2
Now
lim (𝑙𝑛[𝑚𝑧 (𝑡)]) = lim (𝑙𝑛[𝑚𝑧 (𝑡)])
𝑛→𝑥 𝑢→0
𝑡2 ln[m(𝑢)] − μu
= 2 lim
𝜎 𝑢→0 𝑢2
m′(𝑢)
𝑡2 −μ
m(u)
= 2 lim (𝑈𝑠𝑖𝑛𝑔 𝐿′ 𝐻𝑜𝑝𝑖𝑡𝑎𝑙 ′ 𝑠 𝑟𝑢𝑙𝑒)
𝜎 𝑢→0 2𝑢
m"(𝑢)m(u) − [m′(u)]2
𝑡2 [m(u)]2
= 2 lim (𝑈𝑠𝑖𝑛𝑔 𝐿′ 𝐻𝑜𝑝𝑖𝑡𝑎𝑙 ′ 𝑠 𝑟𝑢𝑙𝑒)
𝜎 𝑢→0 2
𝑡 2 m"(0) − [m′(0)]2
= 2
𝜎 𝑢2
2
𝑡 E(xi ) − [E(xi )]2 𝑡 2
2
= 2 =
𝜎 2 2
(k)
mx = k th derivative of mx (t)at t = 0.
= μk = E(X k )
mx (0) = 1
Thus
𝑡2
𝑡2
lim (𝑙𝑛[𝑚𝑧 (𝑡)]) = and lim [𝑚𝑧 (𝑡)] = 𝑒 2
𝑛→∞ 2 𝑛→∞
The last is recognized as the m.g.f. for standard normal distribution.
(𝑥−𝜇)2
1 −
Gaussian (or normal) distribution 𝑝(𝑥) = {𝑒 2𝜎2 }
√2𝜋 𝜎
The standard normal distribution is the normal distribution with mean μ = 0 and variance σ2 = 1
1 𝑥2
−
𝑝(𝑥) = {𝑒 2 }
√2𝜋 𝜎
Random walk Page 9
The speed of convergence
For independent random variables with finite variance, the CLT ensures that Sn will converge to a
stochastic process with pdf
1 𝑆𝑛2
𝑃𝐺 (𝑆𝑛 ) = exp (− 2 ) … … … (1)
√2𝜋 𝜎 2𝜎𝑛
How fast is this convergence? Chebyshev considered this problem for a sum Sn of i.i.d. random
variables xi. He proved that the scaled distribution function given by
𝑆
𝐹𝑛 (𝑆) = ∫ 𝑃̃ (𝑆̃𝑛 )𝑑 𝑆̃𝑛 … … … … … (2)
−∞
differs from the asymptotic scaled normal distribution function Φ(S) by an amount
𝑆2
𝑒 − 2 𝑄1 (𝑆) 𝑄2 (𝑆) 𝑄𝑗 (𝑆)
𝐹𝑛 (𝑆) − Φ(𝑆)~ ( 1/2 + + ⋯ + 𝑗/2 + ⋯ ) … . (3)
√2𝜋 𝑛 𝑛 𝑛
where the Qj (S) are polynomials in S, the coefficients of which depend on the first j + 2 moments of
the random variable {xi}.
Berry and Ess´een found a simpler solution. Their results are today called the Berry–Ess´een
theorems. The Berry–Ess´een theorems provide simple inequalities controlling the absolute
difference between the scaled distribution function of the process and the asymptotic scaled normal
distribution function. However, the inequalities obtained for the Berry–Ess´een theorems are less
stringent than what is obtained by the Chebyshev solution of Eq. (3). The Berry–Esseen theorem
(Berry–Esseen inequality) attempts to quantify the rate at which the convergence to normality takes
place.
Berry–Ess´een Theorem 1
Let the xi be independent variables with a common distribution function F such that
𝐸{𝑥𝑖 } = 0 (1)
𝐸{𝑥𝑖2 } = 𝜎 2 > 0 (2)
𝐸{|𝑥𝑖 |3 } ≡ 𝜌 < ∞ (3)
Then, for all S and n,
3𝜌
𝐹𝑛 (𝑆) − Φ(𝑆) ≤ (4)
𝜎 3 √𝑛
The inequality (4) tells us that the convergence speed of the distribution function of S n to its
asymptotic Gaussian shape is essentially controlled by the ratio of the third moment of the absolute
value of xi to the cube of the standard deviation of xi.
Berry–Ess´een Theorem 2
Theorem 2 is a generalization that considers random variables that might not be identically
distributed. Let the xi be independent variables such that
Random walk Page 10
𝐸{𝑥𝑖 } = 0 (1)
𝐸{𝑥𝑖2 } = 𝜎𝑖2 (2)
𝐸{|𝑥𝑖 |3 } ≡ 𝜎𝑖2 (3)
And define
𝑠𝑛2 ≡ 𝜎12 + 𝜎22 + ⋯ + 𝜎𝑛2 (4)
and
𝜌𝑛 = 𝑟1 + 𝑟2 + ⋯ + 𝑟2 (5)
Then for all S and n
𝜌𝑛
|𝐹𝑛 (𝑆) − Φ(𝑆)| ≤ 6 (6)
𝑠𝑛3
Basin of attraction
An attractor is a point or collection of points on which the system can limit. These often take the
form of fixed points, periodic orbits etc. The basin of attraction for an attractor is the set of points
which limit on the attractor. That is the basin of attraction is the set of states in the system within
which almost all states flow to one attractor. Informally, the basin of attraction is a set of points
from which a dynamical system spontaneously moves to a particular attractor.
The central limit theorem states that the sum of a number of independent and identically distributed
(i.i.d.) random variables with finite variances will tend to a normal distribution as the number of
variables grows. All distribution with finite variance form attraction basin of Gaussian. In other
words, the Gaussian pdf is an attractor in the functional space of pdfs for all the pdfs that fulfill the
requirements of the CLT. The set of such pdfs constitutes the basin of attraction of the Gaussian
pdf.
Fig. pictorial representation of the
convergence to Gaussian pdf PG(S∞)
for the sum of i.i.d. finite variance
random variables.
PG(S∞)
In Fig., we provide a pictorial representation of the motion of both the uniform and exponential
P(Sn) in the functional space of pdfs, and sketch the convergence to the Gaussian attractor of the
Random walk Page 11
two stochastic processes Sn. When n increases, both pdfs P(Sn) become progressively closer to the
Gaussian attractor PG(S∞). The number of steps required to observe the convergence of P(Sn) to
PG(S∞) provides an indication of the speed of convergence of the two families of processes.
Question: Suppose we start at zero on a number line and walk randomly, taking steps of ±1 with
equal probability. We will stop taking steps when we reach either -10 or 100. What is the
probability that we will end at 100?
Solution:
Fig. Illustration of random walk problem
We can treat this as a linear problem. Letting p be the probability of reaching 100, we find that
𝐸|𝑋∞ | = 100. 𝑝 + (−10). (1 − 𝑝)
= 100𝑝 + 10𝑝 − 10 = 0
⟹ 110𝑝 = 10
1
⟹𝑝=
11
So we reach 100 with probability 1/11 and -10 with probability 10/11
Question: Find the probability that a random walk of 8 steps with probability p=0.6 ends at a)
position x = 6, b) position x= - 4.
Solution: a) The events X8 = 6 occur with l =7 positive (+1) steps and l=1 negative (-1) steps but
they could be any order. Hence by the formula PN (m) = {N!/([0.5(N + m)]![0.5(N – m)!]}(½)N
8
𝑃(𝑋8 = 6) = ( ) 0.67 × 0.4 = 0.0896
7
b) The events X8 = - 4 occur with l=2 positive (+1) steps and l= - 6 negative (-1) steps but they
could be any order.
8
𝑃(𝑋8 = −4) = ( ) 0.62 × 0.46 = 0.0413
2
Question: A symmetric random walk starts from origin. Find the probability that the walker is at
the origin at step 8.
Solution: a) The probability that walker is at the origin at step 8 is
8
𝑃(𝑋8 = 0) = ( ) 0.54 × 0.54 = 0.273
4
Random walk Page 12
Random walk Page 13
Random walk Page 14