# STAT333 Lecture Notes - Lecture 9: Equivalence Class, Identity Matrix, Random Variable

49 views4 pages

4 Feb 2016

School

Department

Course

Professor

Discrete-time Markov Chains

Generally speaking, {X(t), t ∈T}is called a stochastic process if X(t) is a random

variable (or random vector) for any ﬁxed t∈T.Tis referred to as the “index set”, and

is often interpreted in the context of time. As such, X(t) is often called the “state of the

process at time t”.

The index set Tcan be a continuum of values (e.g., T={t:t≥0}) or can be a set of

discrete points such as T={t0, t1, t2, . . .}. Since there is a one-to-one correspondence with

the set of non-negative integers {0,1,2, . . .}, we will use such an index set for a discrete-time

process. In other words, {X(n), n = 0,1,2, . . .}(or {Xn, n = 0,1,2, . . .}) will represent a

general discrete-time stochastic process.

Deﬁnition: A stochastic process {Xn, n = 0,1,2, . . .}is said to be a discrete-time Markov

chain (MC) if the following conditions hold true:

(i) For any n= 0,1,2, . . . ,Xntakes on a ﬁnite or countably inﬁnite set of possible

values (unless otherwise stated, we assume that the general state space for Xnis

{0,1,2, . . .}).

(ii) For any n= 0,1,2, . . . ,

P(Xn+1 =xn+1|Xn=xn, Xn−1=xn−1, . . . , X0=x0) = P(Xn+1 =xn+1|Xn=xn).

The above relation implies that the conditional distribution of any future state Xn+1

given the past states X0, X1, . . . , Xn−1and the present state Xnis independent of the

past states. We refer to this relation as the Markov property.

Remark: In general, the sequence of random variables {Xn}∞

n=0 are neither independent

nor identically distributed.

Deﬁnition: For any pair of states iand j, the transition probability from state iat time n

to state jat time n+ 1 is given by Pn,i,j =P(Xn+1 =j|Xn=i) for n= 0,1,2, . . . .

Let Pn= [Pn,i,j ] be the associated matrix containing the elements Pn,i,j , referred to as the

one-step transition probability matrix (TPM) from time nto time n+ 1. It looks like:

Pn=

Pn,0,0Pn,0,1Pn,0,2· · · Pn,0,j · · ·

Pn,1,0Pn,1,1Pn,1,2· · · Pn,1,j · · ·

.

.

..

.

..

.

..

.

..

.

..

.

.

Pn,i,0Pn,i,1Pn,i,2· · · Pn,i,j · · ·

.

.

..

.

..

.

..

.

..

.

..

.

.

.