Transcript Introduction to Stochastic Processes and Markov Chain

Introduction to Stochastic Processes
and Markov Chain
Prof. Dr. Md. Asaduzzaman Shah
Department of Statistics
University of Rajshahi
1
Variable

2
Values varies from individual to
individual
Stochastic Variable

3
Families of random variable
One dimensional process

Classified into four types of processes

(i)
Discrete time, discrete state space

(ii)
(iii)
(iv)
Discrete time, continuous state space
Continuous time, discrete state space
Continuous time, continuous state space


4
Discrete time Discrete state space
5
Examples

A fair coin is tossed n times and the outcomes represented
by Xn. Here, Toss No. treated as ‘time’ and the
result/outcome considered as ‘space’ of the experiment.
Both time and space are discrete.
Toss No.
Outcomes
6
1
T
2
H
3
H
…
…
n-1
H
n
T
Experiment and Its Outcomes

Suppose a fair coin is tossed twice. Sample
space and four simple events are
  HH , HT , TH , TT   1 , 2 , 3 ,  4 

1  HH , 2  HT , 3  TH  and 4  TT 
7
Counting Heads
X (1 )  X ( HH )  2
X ( 2 )  X ( HT )  1
X ( 3 )  X (TH )  1
X ( 4 )  X (TT )  0
8
Probability

9
Now the values 0,1 and 2 have probabilities
¼, 2/4=1/2 and ¼. So, X(t) = X(ω) = 0,1,2
are stochastic variable with t=0,1,2.
Discrete time Continuous state space
(Velocity of a car in a time interval (0,t)
10
DC

In a stochastic process {X(t), t€T} in which time parameter, t is
discrete, however, the state space, velocity X(t), which is
increasing or decreasing is continuous.
Time(Road) 10:00:00 12:30:00 18:45:00 24:00:00
Velocity
11
60m/h
45m/h
26m/h
70m/h
Continuous time, discrete state space
12
CD

13
The number of passengers waiting at Dhaka Bus
Terminal, Rajshahi on Friday, August 09, 2011 from
(10-11 AM).Time and tide wait for none(Continuous).
Time
10:00
10:15
10:20
11:00
Passengers
waiting
460
345
220
370
More examples



14
Long Route Buses: Hanif, National , Green Line, etc.
that’s are started in a particular time.
Patients are admitted at Rajshahi Medical College
Hospital (RMCH) in a particular day.
Customer’s are waiting in a super-market for getting
Eid Fashion
Continuous time Continuous state space
15
CC

16
If we measure the temperature of a certain
place in a time interval (0,t) for each day is
an example of CTCSS, because time interval
is continuous as well as temperature which is
not fixed, it is rising/falling following a day
follows morning to noon, noon to evening,
evening to night, so state space is also
continuous.
Loss variables character


17
** Making Laugh to see the teeth (^^^^^^)
instead of monitoring the defective teeth
** Slapping to see the number of eye drops
(weeping),
Notations



18
Discrete random variable represented by Xn
or X(n).
Continuous random variable indicated by Xt
or X(t).
Stochastic processes are defined by the
notations { Xn} and {X(t)}
Differences
Discrete
Continuous
Family represented Family represented by {Xt, t€T} or
by {Xn, n=0,1,2,…,} {X(t), t€T}, T is finite/infinite.
Parameter ‘n’
Parameter ‘t’ interpreted as time,
some times it represents characters
like as, (i) distance, (ii) length, (iii)
thickness and so on.
Stochastic sequence Stochastic process
19
At a Glance

Xn

X(t)
X
Outcomes of
Experiment
Or Space
Thrown/
Toss No.
n
Time
X(t)
20
Distance/
Length/
Thickness.
Relationship

In some of the cases, the r.v Xn, i.e. members of the family {Xn,
n>=0} are mutually independent, but more often they are not
independent. We generally come across Processes whose
members are mutually dependent.

Throwing a fair coin 20 times by 20 peoples, outcomes will be
different instead of, a person will throw the coin 20 times. The
relationship among them is often of great importance.
The nature of dependence could be infinitely varied.
Dependence of such special types, which occurs quite often and is
of great importance.
According to the nature of dependence relationship existing among
the members of the family, we may describe or mathematically
formulate them by some Stochastic Processes.



21
Stationary Processes
stochastic process { Xn, n>=1 } is time independent (not
necessary hours, months, years) i.e. covariance stationary.

Let Xn, n>=1 be uncorrelated random
variables with mean 0 and variance 1.
C n, m   covX n , X m   E ( X n , X m )  E ( X n ) .E ( X m )
 E( X n , X m )

22

0
1
if m  n
if m  n
1. Poisson Process

Consider the process {X(t), t€T} with
e  t ( t ) n
PrX (t )  n 
,   0, n  0,1,2,3;...;
n!
23
(i)
the mean function and (ii) the variance
m(t )  EX (t )   t
varX (t )   t
24
Non-Stationary

25
Both are functions of t. Therefore, the
stochastic process {Xn, n>=1} is nonstationary/evolutionary.
The
distribution
(Poisson) of the stochastic process {Xn,
n>=1} is functionally dependent on t.
2. Mean and Co-variance
m(t )  EX (t )  ED1  D2 t  d1  d 2 t
EX (t ) X ( s )  E( D1  D2 t )( D1  D2 s )
 E ( D12 )  ( s  t ) E ( D1 D2 )  t s E ( D22 )
  12  d12  ( s  t ) d 1 d 2  t s ( 22  d 22 )
 Var ( D1 )  ( E ( D1 )) 2  ( sum of times) d 1 d 2

 ( product of times) Var ( D2 )  ( E ( D2 )) 2
26

Variance
var X (t )  EX (t )  E ( X (t ))
2
2
EX (t )  var X (t )  E ( X (t ))
2
2
  12  t 2 22  d1  d 2 t    12  d12  2 td1d 2  t 2 ( 22  d 22 )
2
27
The Process is non-stationary, i.e.
evolutionary
C ( s, t )  covX (t ), X ( s)    ts
2
1
28
2
2
3. Expection
X (t )  D0  D1t  D2 t 2
E[ X (t )]  E ( D0 )  t E ( D1 )  t E ( D2 )  0  t.0  0.t  0
2
29
2
Covariance
CovX (t ), X ( s)  E{ X (t ) X ( s)}  E ( X (t )).E ( X ( s))
 E{( D0  D1t  D2 t 2 )( D0  D1 s  D2 s 2 )}  E ( D0  D1t  D2 t 2 ) E ( D0  D1 s  D2 s 2 )
 1  ts  t 2 s 2
30
Variance
Var{ X (t )}  var{ D0  D1t  D2 t 2 )  v( D0 )  t 2 v( D1 )  t 4 v( D2 )  1  t 2  t 4
31
Mean stationary but Process nonstationary


32
Therefore, the stochastic process,
X(t)=D0 + D1 t + D2 t2, where Di, i=0,1,2 are
uncorrelated random variables with mean 0
and variance 1, is dependent on the time
parameter t and s, so it is non-stationary. But
the mean of the process is stationary.
Briefly: Time, also treated as distance, length,
thickness etc.
Stationary
TimeIndependent
Non-Stationary
TimeDependent
33
Problem



34
Manufacturers A and B are competing with each other in a
restricted market. Over the year, A’s customers have
exhibited a high degree of loyalty as measured by the fact
that customers using A’s product 80 percent of the time. Also
former customers purchasing the product from B have
switched back to A’s 60 percent of the time.
(a) Construct and interpret the state transition matrix terms of
(i) retention and loss, (ii) retention and gain.
(b) Calculate the probability of a customer purchasing A’s
product at the end of the second period, Draw the transition
probability diagrams and the transition trees.
State Transition P
Next Purchase (n=1)
Current
Purchase
(n=0)
35
A
B
A
0.8
0.2
B
0.6
0.4
Interpretation of Conditional
Probability

36
The probability of a customer’s purchase at
the next step (n=1) depends upon the
product that he bought previously (n=0), i.e.,
current purchase.
Retention and Loss (Rows of P),


37
P11= 0.80
means that a customer now using A’s product will again
purchase A’s product at the next purchase in 8 of 10
times. This implies retention to A’s product.
P12= 0.20
means that the customer now using A’s product will
switch over to B’s product at the next purchase in 2 pot
of 10 times. This implies loss of A’s product.
Retention and Gain (Columns of P),

P11= 0.80
means that the customer now using A’s product
will again purchase A’s product next time in 8 out
of 10 times. This implies retention of A’s product.

P12= 0.60
shows that the customer now using B’s product
will purchase A’s product next time in 6 out of 10
times. This implies gain to A’s product.
38
Second Row and Column
39

A similar interpretation holds for the second
row of P

The second column of P can be interpreted
similarly.
Transition Probability Diagram
0.80
40
A
B
0.40
Transition Trees
A
A
B
0.80
A
A
0.20
B
B
41
QUESTIONNAIRE ON PROFESSIONS
(Research Project & Field Studies)
•Agriculture
Business
Service
Others
42
Generations and their professions

(Please put tick () mark on the Boxes)
Great Grand Father
Grand Father
Father
43
Service
Raw data table
Great Grand Father
A


X
X

44
B
X
X

X
X
S
X
X
X
X
X
O
X
X
X

X
Professions
Grand Father
A B S O

X
X
X
X

X

X
X
X
X
X

X
X

X
X
X
A


X

X
Father
B S
X
X
X
X
X
X
X
X
X

O
X
X

X
X
NUMERICAL FIGURES IN DIFFERENT
STATES OF CLASSES
Professions
G Father
Total
Professions
G G Father
45
A
B
S
O
A
138
7
15
0
160
B
6
11
0
1
18
S
1
0
5
0
6
O
4
3
4
5
16
Total
149
21
24
6
200
ESTIMATED TRANSITION
PROBABILITY
Professions
G Father
Professions
G G Father
46
A
B
S
O
A
0.8625
0.0437
0.0937
0.0000
B
0.3333
0.6111
0.0000
0.0555
S
0.1666
0.0000
0.8333
0.0000
O
0.2500
0.1875
0.2500
0.3125
EXPECTED STAY IN EACH SOCIAL CLASS AND
PRAISE MEASURE OF SOCIAL MOBILITY
Class
Agriculture
Business
Service
Others
47
E ( j ) 
1
(1  pij )
2.8003
2.7503
5.0000
1.4999
E ( j ) 
1
(1  p j )
1.2253
1.2115
2.7390
1.0064
 

j
E ( j )
E ( j )
2.2854
2.2702
1.8255
1.4904
COMMENT

48
Last column of the above Table states that the
generation of Great Grand Father of Grand Father,
the agriculture community has most tendency to
adjust their children to agriculture. Then comes the
Business community and third after Agriculture and
Business community comes the Service community.
Finally comes the others community.
Bartholomew Model
k
k
f
p
i

j
 i ij
j 1 i 1
49

This measure depends on which generation we
choose as our base. Replace fi by pj we get
measure of social mobility given by
k
k
D   p j pij i  j , 0  D  1
j 1 i 1
50
Conditions


51
D = 0,
the society is perfectly stable i.e, no mobility
takes place
D = 1,
the society is perfectly mobile.
Application Bartholomew Method

D = p1 [ p12+ 2p13 + 3p14 ] + p2 [ p21+ p23 + 2p24 ] +
p3 [ 2p31+ p32 + p34 ] + p4 [ 3p41+ 2p42 + p43 ]
= 0.2242
From the Bartholomew co-efficient of mobility we see that the
society of that time was quite stable one.
Indicates that the society in the generation of Great Father to Grand Father had a very good deg of
mobility which is an indicator of the economic and social progress the society is going through in this
generation.
52
Chi-Square Test

53
Simplest and most commonly used nonparametric test in statistical work. The
quantity describes the magnitude of
discrepancy theory and observation.
Hypothesis

54
The transition probability matrix (t.p.m) in
internal is completely independent of the
lithology at the immediate underlying point.
Under this hypothesis the expected t.p.m
would consist of rows that are all identical to
the fixed probability vector.
Theory
4
 
2
j 1
(O j  E j )
Ej
2
,
O  observed , E  exp ected
55
Values
  14.39 (calculated )
2

56
2
4 , 0.05
 9.48 (talculated )
Decision

57
So the null hypothesis is rejected as the
tabulated value is lower than the calculated
value.
NUMERICAL FIGURES IN DIFFERENT
STATES OF CLASSES
Professions
Father
Professions
G Father
58
Total
A
B
S
O
A
75
31
40
3
149
B
0
15
6
0
21
S
5
3
15
1
24
O
3
0
1
2
6
Total
149
21
24
6
200
EXPECTED STAY IN EACH SOCIAL CLASS AND
PRAISE MEASURE OF SOCIAL MOBILITY
Class
59
 

j
E ( j )
E ( j )
Agriculture
1.8923
Business
1.2845
Service
2.3233
Others
1.3529
COMMENT

60
From the above Table, the generation from Grand
Father to Father, the service community has most
tendency to adjust their son to service. Second
comes to agriculture community and third comes the
business.
D-index & Chi-square


61
Using the measure of mobility as given by
Bartholomew, D = 0.6031, A good degree of
mobility, indicates fast social and economic
progress.
Null hypothesis accepted, generations have
independence in profession selections
Occupational Mobility : Markov Approach
Human Societies
Stratified
Income
Occupation
Social
Status
Residence Place
62
societies move on class
• In our society children do not always follow their
fathers’ footsteps.
• In a free society a person has some degree of
choice about changing his job or moving house.
• The inherent uncertainty of individual behavior in these
situations means that the future development of the
mobility process cannot be predicted with certainty but
only in terms of probability.
63
MODELS FOR SOCIAL MOBILITY
• A very simple model for the development
of a single family line and then, investigate
the consequences of unrealistic features.
The fundamental requirement in a model
is that it must specify the way in which
changes in social occur.
64
Assumption of model
• Chance of moving depends only on the
• present class
• but not on the
• past class/remote past
•
If the movement can be regarded as taking place at
discrete points in time the appropriate model becomes a
simple
• Markov chain
•
Changes are governed by transition
are independent of time.
probabilities
which
65
Markov
•
•
•
•
•
Andrei Andreivich Markov
Alive 67 years
From1856 to 1922
Russian Mathematician
Idea first occurred to him when he was
watching an opera of the famous Russian
writer Pushkin’s.
66
Notations
• Pij, the probability that the son of a father in
class i is in class j
•
k
P
j 1
ij
(since the system is closed)
1
k is the number of classes and P, the matrix of transition probabilities.
P(T )  p(0) P
T
67
Day-to-Day Inventory
Problem : The number of units of an item that are
withdrawn from inventory on a day-to-day basis is a
Markov chain in which requirements for tomorrow
depend on today’s requirements. A one day transition
matrix is given below :
68
Number Units Withdrawn from Inventory
Tomorrow
5
5
0 .6
10
0 .4
12
0 .0
Today 10
0 .3
0 .3
0 .4
12
0 .1
0 .3
0 .6
69
Target
• (a) Tree diagram showing inventory
requirements on two consecutive days.
• (b) A two-day transition matrix
• (c) How a two-day transition matrix help
manager for inventory management.
70
Transition Tree
5
5
0.4
10
12
5
5
0.4
10
0.3
10
12
5
12
0.3
10
12
71
Transition Probabilities
p  (0.6)(0.6)  (0.4)(0.3)  (0.0)(0.1)  0.48
2
11
p  (0.6)(0.4)  (0.4)(0.3)  (0.0)(0.3)  0.36
2
12
p  (0.6)(0.0)  (0.4)(0.4)  (0.0)(0.6)  0.16
2
13
72
Transition Probabilities
p  (0.3)(0.6)  (0.3)(0.3)  (0.4)(0.1)  0.31
2
21
p  (0.3)(0.4)  (0.3)(0.3)  (0.4)(0.3)  0.33
2
22
p  (0.3)(0.0)  (0.3)(0.4)  (0.4)(0.6)  0.36
2
23
73
Transition Probabilities
2
p31
 (0.1)(0.6)  (0.3)(0.3)  (0.6)(0.1)  0.21
2
p32
 (0.1)(0.4)  (0.3)(0.3)  (0.6)(0.3)  0.31
p  (0.3)(0.0)  (0.3)(0.4)  (0.6)(0.6)  0.48
2
33
74