Markov Chains in Discrete Time

Question 1

Define a stochastic chain

Answer 1

Let Xn with n∈N0 denote random variables defined on probability space (Ω, F, P) taking values in a discrete space S.
Then the stochastic process X = (Xn : n∈N0) is called a stochastic chain (with time domain N0 and state space S).
If Xn = i, we say that the process is in state i at time n

Question 2

Give the Markov property

Answer 2

P(X_(n+1) = j | X0=i0, …, Xn= in) = P(X_(n+1) = j | Xn= in)

Question 3

When is a Markov chain time homogenous?

Answer 3

If conditional probabilities do not depend on time index n

Question 4

What should the row sum of a transition matrix equal?

Answer 4

1

Question 5

Derive the Chapman-Kolmogorov equations of an m-step transition

Answer 5

P( X_(m+n) ) = pij^(m+n)
= P(i,j)^(m+n)
= sum(k in S) P(i,k)^(m) * P(k,j) ^(n)
= sum(k in S) P(Xm = k | X0 = i)*P(Xn = j | X0 = k)

Question 6

When is a communication class closed?

Answer 6

If it doesn’t allow access to states outside of itself

Question 7

When is a communication class absorbing?

Answer 7

If the communication class consists only of one state

Question 8

When is a Markov chain irreducible?

Answer 8

All states communicate with each other

Question 9

Give the distribution of stopping time of first visit to a state

Answer 9

Fk(i,j) = pij if k=1
Fk(i,j) = sum(h≠j) pih * F(k-1)(h,j) if k≥2

Question 10

Give the probability of ever visiting a state

Answer 10

fij = pij + sum(h≠j) pih * fhj for all i,j in S

Question 11

Give P(Nj = m | x0 = i), where Nj is the number of visits to state j

Answer 11

P(Nj = m | x0 = i) = 1 - fjj, m=0

= fij * fij^(m-1) (1 - fjj), m≥1

Question 12

When is a state called recurrent?

Answer 12

fjj = 1

Question 13

What can be said about other states in a communication class if one state is recurrent?

Answer 13

All states in the communication class are recurrent

Question 14

What is P( Xn = j | x0 = i) as n goes to infinity if j is a transient state?

Answer 14

P( Xn = j | x0 = i) = 0 as n goes to infinity

Question 15

When is π a stationary distribution?

Answer 15

When πP = π

Question 16

Does a transient Markov chain have a stationary distribution?

Answer 16

No

Question 17

Give mean time of return for a recurrent state

Answer 17

mi = E( τi | x0 = i)

where τi = min{ n≥1 : Xn = i }

Question 18

When is a state positive recurrent?

Answer 18

mi < infinity

Question 19

How can you jump to the conclusion of positive recurrence?

Answer 19

If a Markov chain is irreducible and has finite state space S, the chain is positive recurrent

Question 20

How can you obtain the stationary distribution from the mean time of return?

Answer 20

πi = 1/mi

Question 21

How can you show aperiodicity?

Answer 21

If the j-th column of P^m is all positive, the Markov chain is aperiodic

Question 22

When is a Markov chain called ergodic?

Answer 22

If it is aperiodic, irreducible and positive recurrent