Random Walk
One dimensional discrete case (One dimensional discrete
random walk):
Motion of certain object whose time evolution of position at any time is
underterministic and stochastic (random process) is called random walk.
Let us consider x
i
be the independent and identically distributed
random variable with i = 1, 2, ....n. Suppose that x
i
can randomly take
values s where s is the single step size of the random walk. ∆t be the
time of single step random walk. If the process performs n random walk
the total time taken for n random values is t = n∆t
Suppose, s
n
= x
1
+ x
2
+ ...... + x
n
is the sum of random variable.
Then the 1st moment of the random walk is
E(x
i
) =
P
x
i
n
Because x
i
can take either +s or -s with equal probability.
Econophysics, 4th Year Random Walk
Properties of 1D discrete Random walk:
Show that expectation value of final position in random walk is
zero. or
Prove that next step in Random walk cannot be predicted.
Let us consider x
i
be the independent and identically distributed
random variable which can take value ±s; s being the step size of
random walk. Let ∆t be the time taken to walk step s. Then the final
state of the random walk;
s
n
= x[n∆t] = x
1
+ x
2
+ ...... + x
n
...(1)
Now, the expectation value of final position of hte random walk is
E(s
n
) = E[x(n∆t)] = E(x
1
+ x
2
+ ...... + x
n
) ...(2)
Econophysics, 4th Year Random Walk
As x
i
’s are independent,
E(x
1
+ x
2
+ ...... + x
n
) = E(x
1
) + E(x
2
) + ....E(x
n
) =
X
i=1
nE(x
i
)
Using equation (ii) and (iii) we obtain,
E[x(n∆t)] =
X
i=1
nE(x
i
) ...(2)
But for random walk E(x
i
) = 0 where i = 1, 2, ....n.
E[x(n∆t)] =
X
i=1
nE(x
i
) = 0
Hence, the expetation value of final position of random walk is zero.
Econophysics, 4th Year Random Walk
Show that variance of random walk process grows linearly with
the no. of step n.
Letus consider x
i
be the independent and identically distributed random
variable which can take value ±s: s being the step size of random walk.
Let ∆t be the time taken to walk step s. Then the final state of the
random walk:
s
n
= x[n∆t] = x
1
+ x
2
+ ...... + x
n
...(1)
Now,
E[x(n∆t)
2
] = E[(x
1
+ x
2
+ ...... + x
n
)
2
] ...(2)
for random walk,
E(x
i
, x
j
) = δ
ij
s
2
where, δ
ij
= 1 if i = j
......(3) = 0 , otherwise
where, i = 1, 2, ....m
Econophysics, 4th Year Random Walk
As x
i
are independent (covariance = 0) random variable,
E[(x
1
+ x
2
+ ...... + x
n
)
2
] = E(x
2
1
+ x
2
2
+ x
2
3
+ ....... + x
2
n
)
= E(x
1
)
2
+ E(x
2
)
2
+ ......... + E(x
n
)
2
=
n
X
i=1
E(x
i
)
2
......(4)
Equation (4) is valid becausex
i
’s are independent and the covariance of
independent variables is zero.
using equation (3) and (4)
n
X
i=1
E(x
i
)
2
=
n
X
i=1
s
2
= ns
2
......(5)
Then from equation (2) and (5) we obtain,
E[x(n∆t)
2
] = ns
2
Econophysics, 4th Year Random Walk
Continous Random walk (Wiener Process): The continous limit
The random walk process with very large no of steps and very small
time step is called continous random walk process. The continous limit
of random walk may ne achieved by considering the limit n → ∞ and
∆t → 0 such that t = n∆t is finite; n, t and ∆t being the no. of step,
time of entire walk and time step of individual walk.
If x
i
is independent and identically distributed random variable with
i = 1, 2, ......n which can take ±s; s being the size of each of each step.
Then variance of final step x(n∆t) is,
E[x
2
(n∆t)] = ns
2
=
s
2
∆t
t ∵ t = n∆t
Let s
2
= D∆t
then D =
s
2
∆t
E[x
2
(t)] = Dt ....(1)
Econophysics, 4th Year Random Walk
where D is termed as diffusion cofficient and this linear dependence of
the variance of x
2
(t) on t is the characteristics of a diffusive process.
This type of stochastic process is called wiener process (Diffusive
Random walk)
for n → ∞ and ∆t → 0 stochastic process becomes Gaussian process.
i.e., for n → ∞ and ∆t → 0
Random walk → Gaussian walk
holds only when n → ∞ and is not generally true in the discrete case
when n is finite, since the distribution of s
n
is characterized by its
probability density function. it is mostly non-Gaussian and assumes the
Gaussian shape only asymptotically (symmetric) with n. The
probability density function of the process P [x(n∆t)] - or equivalently
P (S
n
) - is a function of n, and P (x
i
) is arbitrary.
Econophysics, 4th Year Random Walk
How does the shape of P [x(n∆t)] change with time?
Under the assumption of independence,
P [x(2∆t)] = P (x
1
) ⊗ P (x
2
),
where ⊗ denotes the convolution.
The figure 1 below shows four different probabilty density fucntions
P (x).
(i) a delta distribution with P (x) = δ(x + 1)/2 + δ(x − 1)/2
(ii) a uniform distribution with zero mean and unit standard deviation
(iii) a Gaussian distribution with zero mean and unit standard
deviation, and
(iv) a Lorentzian (or Cauchy) distribution with unit scale factor
Econophysics, 4th Year Random Walk
It is seen that for delta and uniform distribution the function P (S
n
)
change both in scale and in functional as n increases, while for Gaussian
and Cauchy distribution, the functional form is same for both P (S
n
) and
P(x). When the functional form of P (S
n
) is same as the functional form
of P (x
i
) the stochastic process is called stable. Figure below shows the
behaviour of P (S
n
) for independent and identical distributed variables
with n = 1, 2 for the probability density functions of Figure above.
Econophysics, 4th Year Random Walk
Central Limit Theorem
It states that ”if x
i
=
(
1 with probability p is independent
2 with probability q
random variables then S
n
= x
1
+ x
2
+ ..........x
n
follows normal
distribution (Gaussian distribution)”.
i.e., x
i
∼ N(0, 1) with mean zero and variance 1.
Proof:
Here x
i
; i = 1, 2, .....n are the independent random variables distributed
identically. Then,
moment generating function of x
i
= M
x
i
(t)
= E(e
tx
i
)
=
X
i
e
tx
i
(pmf)
= (e
t.1
p + e
t.0
q)
= (q + pe
t
)
Econophysics, 4th Year Random Walk
Again, moment generating function of S
n
= x
1
+ x
2
+ ...... + x
n
M
S
n
(t) = M
x
1
+x
2
+......+x
n
(t)
= M
x
1
(t).M
x
2
(t).......M
x
n
(t)
[∵ x
′
i
s are independent and identically distributed random variables]
∴ M
S
n
(t) = (q + pe
t
)
n
......(1)
The moment generating function of S
n
is exactly same as that of
Binomial distribution. Then from the principle of equivalence of
Moment generating function we can say that
S
n
∼ B(n, p)
Now, we can write,
E(S
n
) = µ = np
p
S
n
= npq
Econophysics, 4th Year Random Walk
M
z
(t) = e
−
tµ
σ
(q + pe
t/σ
)
n
= e
−
tnp
√
npq
(q + pe
t/
√
npq
)
n
[∵ µ = np & σ =
√
npq as S
n
∼ B(n.p)]
= [e
−
tp
√
npq
(q + pe
t/
√
npq
)]
n
....(2)
Now,
e
−
tp
√
npq
= 1 −
tp
√
npq
+
t
2
p
2
2npq
+ ....
and e
t/
√
npq
= 1 +
t
√
npq
+
t
2
2npq
+ ....
also, q = 1 − p
so, e
−
tp
√
npq
(q + pe
t/
√
npq
)
=
1 −
tp
√
npq
+
t
2
p
2
2npq
+ ....
1 − p + p
1 +
t
√
npq
+
t
2
2npq
+ ....
Econophysics, 4th Year Random Walk
neglecting higher terms,
=
1 −
tp
√
npq
+
t
2
p
2
2npq
1 − p + p +
tp
√
npq
+
t
2
p
2npq
= 1 −
tp
√
npq
+
t
2
p
2
2npq
+
tp
√
npq
−
t
2
p
2
npq
+
t
3
p
3
2(npq)
3/2
+
t
2
p
2npq
−
t
3
p
2
2(npq)
3/2
+
t
4
p
3
4(npq)
2
= 1 +
t
2
2nq
−
pt
2
nq
+
pt
2
2nq
+ O(n
−3/2
)
= 1 +
t
2
2nq
(1 − p) + O(n
−3/2
)
= 1 +
t
2
2n
+ O(n
−3/2
) ....(3)
where O(n
−3/2
) represents the terms contaning n
3/2
or higher power in
the denominator.
Econophysics, 4th Year Random Walk
If n is very large then O(n
−3/2
) takes a very small value which can be
neglected.
So, from equation (2) and (3)
M
z
(t) = lim
n→∞
1 +
t
2
2n
= e
t
2
/2
The above equation shows that M
z
(t) is equal to that Normal
distribution. So, by principle of equivalence, we can say that,
z ∼ N (0, 1)
i.e.,
S
n
− µ
σ
∼ N(0, 1)
That means S
n
∼ N(µ, σ
2
)
i.e., for large no. of independent random variables the sum takes
Gaussian distribution. Hence proved.
Econophysics, 4th Year Random Walk
State and Prove Central limit Theroem (Alternative Method)
Statement: Tne central limit theorem sates that ”If the variable x has
non normal distribution with mean µ and variance σ, then the variate z
is z =
¯x−µ
σ/
√
n
has Gaussian (normal) distribution when n → ∞.”
Proof:
Here x
i
, i = 1, 2, ...n are the independent random varaibles distributed
identically then
moment generating function M
x
(t) =
P
i
e
tx
i
p(x
i
) ...(1)
Here, the given variate corresponding to ¯x is,
z =
¯x − µ
σ/
√
n
where,
¯x = sample mean
µ = population mean
σ/
√
n = sample s.d.
Econophysics, 4th Year Random Walk
We know moment generating function can be expressed as
M
x
(t) = 1 + tµ
′
1
+
t
2
2!
µ
′
2
+ .... +
t
r
r!
µ
′
r
where µ
′
1
, µ
′
2
, ....µ
′
r
be the moments
Then equa (2) can be written as,
log
e
M
z
(t) = −
µt
√
n
σ
+ n log
e
1 +
t
σ
√
n
µ
′
1
+
t
2
2σ
2
n
µ
′
2
+ ....
= −
µt
√
n
σ
+ n
t
σ
√
n
µ
′
1
+
t
2
2σ
2
n
µ
′
2
+ ....
−
1
2
t
σ
√
n
µ
′
1
+
t
2
2σ
2
n
µ
′
2
+ ....
2
#
[∵ log(1 + x) = x −
x
2
2
+
x
3
3
]
Econophysics, 4th Year Random Walk
Importance of Central Limit Theorem
1
The mean of the sampling distribution will be equal to the
population mean regardless of the sample size even if the population
is not normal.
2
As the sample size increases the sampling distribution of mean will
approach normality. Regardless of the shape of the population
distribution.
3
The relationship between the shape of hte population distribution
and shape of sampling distribution on the mean is called central
limit theorem.
4
CLT is perhaps most important theorem in all statistical inference.
it assumes that the sampling distribution of the mean approaches
normal as the sampe size increases.
so that the central limit theorem is powerful in statistics.
Econophysics, 4th Year Random Walk
Central limit theorem in Random Walk Process.
Suppose that a random variable s
n
is composed of many parts x
i
i.e., s
n
=
n
X
i
x
i
...(1)
where, x
i
is independent such that
E(x
i
) = 0
and E(x
2
i
) = s
2
i
Then δ
2
n
= E(S
2
n
) =
n
X
i=1
s
2
i
Now, we define trancated random variable such that for every ε > 0.
V
i
=
(
x
i
when |x
i
| ≤ εσ
n
o otherwise
Econophysics, 4th Year Random Walk
Then for σ
n
→ ∞, the Lindeberg condition holds true
i.e.,
1
σ
2
n
n
X
i=1
E(u
2
i
) → 1
In such condition the central limit theorem sttes that,
˜
S =
S
n
σ
=
x
1
+ ....x
n
σ
′
√
n
where σ
′
sample s.d.
The
˜
S follows the normal distribution [N(0,1)] with probability density
function
p(
˜
S) =
1
√
2π
e
−
˜
S
2
/2
This can also be written as,
p(s
n
) =
1
√
2πσ
e
−S
2
n
/2σ
[∵
˜
S =
s
n
σ
]
i.e., s
n
follows Gaussian distribution with mean zero and s.d. of σ
Econophysics, 4th Year Random Walk
Speed of Convergence
For independent random variable with finite variance, the central limit
theorem entails that s
n
=
P
n
i=1
x
i
converges to stochastic process with
probability density function
p(s
n
) =
1
√
2πσ
n
e
−S
2
n
/2σ
2
n
where σ
2
n
= E(s
2
n
) with E(x
i
) = 0 and E(s
n
) = 0
then the main question everyone arise is how fast does these converges
i.e., How steep is the tail of the distribution of S
n
.
Considering S
n
=
P
i
x
i
to be a sum of independent and identically
distributed randon variables x
i
with
˜
S
n
=
S
n
σ
=
x
1
+x
2
+....x
n
n
σ
√
n
=
x
1
+ x
2
+ ....x
n
σ
√
n
=
˜x
1
+ ˜x
2
+ ....˜x
n
σ
or,
˜
S
n
=
X
i
˜x
σ
n
with ˜x =
x
i
√
n
σ
2
=
σ
2
n
n
Econophysics, 4th Year Random Walk
Then the scaled distribution function is given by
f
n
(S) =
Z
S
−∞
˜p(
˜
S
n
)d
˜
S
n
... (2) [σ
2
n
= E(S
2
n
)]
where,
˜p(
˜
S
n
) =
√
np(
˜
S
n
)
p(
˜
S
n
) =
1
√
2π
e
−
S
2
n
2
...(3)
According to Gnedenko and Kolmogorov, the scaled distribution
function f
n
(s) differs from asymptotic scaled normal distribution
function Φ(s) by an amount
|f
n
(s) − Φ(s)| ≈
e
−s
2
/2
√
2π
Q
1
(s)
n
1/2
+
Q
2
(s)
n
2/2
+ ...... +
Q
j
(s)
n
j/2
...(4)
where, Q
j
(s) are polynomials in s, the coefficients of which depends on
the first (j + 2) momentum of the random variables x
i
. Larger the value
of s, or smaller the value of difference in LHS in equation (4) faster will
the scaled distribution converge to corresponding normal distribution
and vice versa.
Econophysics, 4th Year Random Walk
So equation (4) represents the rate of convergence of scaled distribution
function to the normal (Gausiian) distribution. This is known as the
Chebysheve’s solution to the problem of rate of convergance with s being
the maximum epoch (time series data points) i.e., s = (s
n
)
max
Berry-Essen Theorem
It provides simplier inequality controlling the absolute difference
between the scaled distribution function of the given random process
and the asympotic scaled normal distribution function i.e., it gives rate
of convergence of scaled distribution function to standard normal
distribution function in more easy and computatble form.
Berry - Essen Theorem - 1:
Let x
i
be independent random variable with a common distribution F
such that
E(x
i
) = 0; E(x
2
i
) = σ
2
> 0 .....(1)
and E(|x
i
|
3
) = δ < ∞
Econophysics, 4th Year Random Walk
and set f
n
stands for the distribution of normalized sum
x
1
+x
2
+....x
n
σ
√
n
=
P
i
x
i
σ
then for all s and n
|f
n
(s) − Φ(s)| ≤
3δ
σ
3
√
n
....(2)
[as n increases diff decreases, whenn → ∞, diff = 0]
where s = max(s
n
), Φ(s) is asymptotic scaled normal distribution
function.
The striking feature of the inequality (2) is is depends only on the first
three moment. The statement canbe verified with he use of smooth
inequality.
Inequality (2) tells us that the convergence speed of the distribution
function of ˜s
n
to its asympototic Gaussian shape is essentially controlled
by the rate of the third moment of the absolute value of x
i
. It is also
seen that the real distribution function (observed) emerges to ideal
normal if n → ∞
Econophysics, 4th Year Random Walk
Berry - Essen Theorem - 2:
Let the x
i
be any random variable such that,
E(x
i
) = 0; E(x
2
i
) = σ
2
i
; E(|x
i
|
3
) = r
i
and define
s
2
n
= σ
2
1
+ σ
2
2
+ ..... + σ
2
n
= σ
2
and
δ
n
= r
1
+ r
2
+ ....... + r
n
We use f
n
to denote the distribution of the normalized sum
x
1
+x
2
+......+x
n
σ
=
P
i
x
i
σ
Then for all s and n
|f
n
(s) − Φ(s)| ≤
6δ
s
3
n
=
6
P
i
r
i
(
P
i
σ
2
i
)
3/2
This also shows that the rate convergence of f
n
(s) to the scaled
normalized distribution Φ(s) depends upon the first three moments.
This is a generalization for random variables that might not be
identically distributed.
Econophysics, 4th Year Random Walk
Attractor
A point or set of point in any defined functional space such as phase
space is said to be attractor if any process with different initial
conditions converge into that point as the process evolve with time.
Mathematically, on attractor is a subset A of the phase space
characterized by the following three conditions.
1
A is forward invariant under f (a, t) if a is an element of A then so is
a(t) = f(a, t) for all t > 0.
2
There exists a neighbourhood of A, called the basin of attraction
B(A), which consists of all points b that enter A in the limit t → ∞.
3
There is no proper (non-empty) subset of A having first two
property.
[Phase space - 6N dimensional space spanned by position and moment]
There are different types of attractor and the different basins pertaining
to different real process. Gaussian distribution play role of attractor for
probability density function of any random statistical process.
Econophysics, 4th Year Random Walk
Basin of Attraction
An attractor basin of attraction isthe region of phase space, over which
iterations are defined, such that the point inthat region will eventually be
iterated into that attractor. For example the Gaussian probability density
function is an attractor in the functional space of probability density function
for all the probability density functions that fulfill the requirements of the
central limit theorem. The set of such probability density functions constitutes
tha basin of attraction of Gaussian probability density function.
The functional form of p(s
n
) change with n and , if the hypothesis of the CLT
are verified, assumes the Gaussian functional form for an asymptotically large
value of n when n increases, probability density function p(s
n
) becomes
progressively closer and closer to the Gaussian attractor P
G
(s
∞
). The number
of steps required to observe the convergence of P (S
n
) to P
G
(s
∞
) provides an
indication of the speed of convergence of the probability density function and
coresponding process.
i.e., P (S
n
)
lim n→∞
−−−−−−→ P
G
(s
∞
)
↑ ↑
Basin attractor
Econophysics, 4th Year Random Walk
Numericals
Q. If f(x) has probability density kx
2
, 0 < x, 1, determine k and
find the probability that
1
3
< x <
1
2
Solution:
Since f(x) has probability density kx
2
, therefore
f(x) = kx
2
; 0 < x < 1
Total probability density is 1
Z
1
0
f(x)dx = 1
i.e., kx
2
dx = 1
=⇒ k
x
3
3
o
= 1
or, k = 3
Then probability density function f(x) = 3a
2
Econophysics, 4th Year Random Walk
Numericals
Q. If a function f(x) of x is defined as follows:
f(x) =
0 for x < 2
1
18
(3 + 2x) for 2 ≤ x ≤ 4
0 for x > 4
find the probability within interval 2 ≤ x ≤ 3 and show that it is
density function.
Solution:
Z
∞
−∞
f()x)dx =
Z
2
−∞
f(x)dx +
Z
4
2
f(x)dx +
Z
∞
4
f(x)dx
=
Z
2
−∞
adx +
Z
4
2
3 + 2x
18
dx +
Z
∞
4
0dx
=
1
18
[3(4 − 2) + (16 − 4)]
= 1
Econophysics, 4th Year Random Walk
Numericals
Q. A bomb plane carrying three bombs flies directly above the
Nail road tract. If a bomb fall within 40 feet of the traffic
within a certain bomb sight the density of the points of impact
of a bombs is
f(x) =
100+x
10000
for 100 ≤ x ≤ 0
100−x
10000
for 0 ≤ x ≤ 100
0 else where
If all three bombs are used what is the probability that the
track will be damanged where
′
x
′
represent the vertical
deviation from the aiming points which is the track in this case.
solution:
Since a bomb tail within 40 feet of the track if the track will be damaged
when the bombs fall within 40 feet either side;
Econophysics, 4th Year Random Walk
