Week 3.2: Matrix representation of a Markov chain. Transition matrix. Chapman-Kolmogorov equation

Loading...

En provenance du cours de National Research University Higher School of Economics

Stochastic processes

27 notes

National Research University Higher School of Economics

Stochastic processes

27 notes

The purpose of this course is to equip students with theoretical knowledge and practical skills, which are necessary for the analysis of stochastic dynamical systems in economics, engineering and other fields. More precisely, the objectives are 1. study of the basic concepts of the theory of stochastic processes; 2. introduction of the most important types of stochastic processes; 3. study of various properties and characteristics of processes; 4. study of the methods for describing and analyzing complex stochastic models. Practical skills, acquired during the study process: 1. understanding the most important types of stochastic processes (Poisson, Markov, Gaussian, Wiener processes and others) and ability of finding the most appropriate process for modelling in particular situations arising in economics, engineering and other fields; 2. understanding the notions of ergodicity, stationarity, stochastic integration; application of these terms in context of financial mathematics; It is assumed that the students are familiar with the basics of probability theory. Knowledge of the basics of mathematical statistics is not required, but it simplifies the understanding of this course. The course provides a necessary theoretical basis for studying other courses in stochastics, such as financial mathematics, quantitative finance, stochastic modeling and the theory of jump - type processes.

À partir de la leçon

Week 3: Markov Chains

Upon completing this week, the learner will be able to identify whether the process is a Markov chain and characterize it; classify the states of a Markov chain and apply ergodic theorem for finding limiting distributions on states

Week 3.1: Definition of a Markov chain. Some examples17:16

Week 3.2: Matrix representation of a Markov chain. Transition matrix. Chapman-Kolmogorov equation11:30

Week 3.3: Graphic representation. Classification of states-110:36

Week 3.4: Graphic representation. Classification of states-24:43

Week 3.5: Graphic representation. Classification of states-37:14

Week 3.6: Ergodic chains. Ergodic theorem-16:11

Week 3.7: Ergodic chains. Ergodic theorem-215:21

Rencontrer les enseignants

Vladimir Panov
Assistant Professor
Faculty of economic sciences, HSE

This subsection will be about

matrix representation for Markov chains.

Starting from now, we will consider all the Markov chains which

have a finite number of elements in the state space.

That is S, consists

only some finite amount of elements and let me just count these elements,

numbering them by one, two,

and so on capital M. One more assumption we should introduce now is the probability

that X_n is equal to j given

that X_n-1 is equal to i is equal to P_ij.

And we will assume that this P_ij does not depend on n at all.

Markov chains with this property are known as homogeneous Markov chains.

Starting from now we will consider only Markov chains of this type.

And since we have this to our assumptions,

we can substitute the various P_ij into one matrix.

This matrix will be denoted by capital P,

so it consists of the elements P_ij where i and j are from

1 to capital M. And this matrix is known as transition matrix.

What are the main properties of this matrix?

First of all, if we just sum of elements of this matrix by one for all.

We get one.

This follows directly from the definition of the various P_ij.

So if for sum by j from 1 to capital M,

then we get one for any i.

And another property which is very three will

that all those elements P_ij are not negative.

So, matrices of this type are known in this matrix as stochastic matrices.

So, according to this definition there is

a transition matrix or this type and this metric

characterizes all of conditional probabilities of this type.

On the other hand,

we can introduce M-step transition matrix.

So, let me denote P_ij of m is a probability

that X_n+m is equal

to j given that X_n is equal to i.

The matrix which consists of the elements,

I will denote by P_(m).

Once more, this is M-Step Transition Matrix.

An interesting question is how to calculate

M-step Transition Matrix from Transition matrix.

And the answer is given by the following theorem.

This is theorem stands that

P_(m) is equal to the P_m.

So, you should multiply the matrix P by

itself m times and you will get exactly the Transition Matrix.

This is a rather beautiful mathematical result and let me show why this result is true.

Let me provide a proof of it.

So, let me consider the elements number ij of this matrix.

So, it is written actually here.

And let me apply for this probability,

the Law of Total Probability.

So, this, I will rewrite it as the sum,

the probability is that X_n+m is equal to j given that

X_n+m-1 is equal to some value of

k. And X_n and is equal to i.

Multiplied by the probability that

X_n+m-1 is equal to k given that X_n is equal to i.

And we shall sum of all k from one to M. Now,

let me apply the Markov property to the first conditional probability.

We know that if we consider the conditional probability here of

the whole history that is completed the term mines by is the most recent past event.

So, actually this conditional probability is equal to

conditional probability X_n+m is equal to j given that X_n+m-1 is equal thia and this.

I can simply cross the last event.

And this term, I will leave it as it is and

now I would like to write all those objects in terms of matrices P,

M, P. So, actually what is the first probability.

This does not seem more than a transition,

probability of transition from the state number k to the state number j.

So is P_kj and as for the second probability,

this is nothing more than P_(m-1)_ik.

So, we get the matrix P(m)

is equal to P multiplied by P_(m-1).

Now, according to this same logic it is equal to P-squared P and minus two and so on.

Finally, we get P in the power m. So,

this observation completes the proof.

So, once more in the matrix of presentation,

we have a transition matrix and in M step transition matrix

which are related to each other according to the following rather beautiful formula,

let me now continue.

You know that in any time moment,

the system is in one of the states forms the state space.

Let me now consider the probability with a stake number k,

the system is a state number j.

Let me denote this probability by Pi_j_(k).

This is of course probability distribution.

So, for now consider Pi_1_(k) and so on, Pi_M_(k).

This is exactly discrete probability distribution,

the sum of numbers is equal to one and all of them are negative

and let me denote this by Pi vector Pi_(k).

Major question is to ask whether it is possible to compute Pi_(k) from Pi_(k-1).

This is of course possible,

and here we should employ nothing more than the law of total probability.

In fact, if you take Pi_j_(k),

this is the probability that X_k is equal to j,

you can rewrite this as a probability that X_k is equal to

j given said X_k-1 is equal to some specific value.

I multiplied by the probability that X_k-1 is equal to i.

And then we sum these products by

i from 1 to M. Okay let me continue.

This is of course the sum from 1 to M. Here

is a transition from a state number i to state number j, that is Pi_ij.

And here we have vector,

element of the vector Pi_(k-1) and element number i.

So, this is from here we conclude,

that actually vector Pi_k is equal to

the product of the vector of Pi_(k-1) and the matrix P. Also we can,

apply this argument many times and finally get the this is

vector Pi_0 multiplied by the matrix P n times.

We say that vector Pi* gives

a stationary distribution for a given Markov chain.

If product of Pi* and matrix P is equal to Pi*.

This is a very point notion and a little bit later I will show why it is so important.

But, the moment let me mention that if Pi_0

is equal to Pi* then Pi_k is also equal to Pi* for any k. So,

this is a system it starts from the station of distribution.

It has a station distribution any time moment.

This is all that you should know at this stage about matrix presentation.

And in the next subsection we will consider graphical representation.

This is another very useful tool for describing a Markov Chain.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play