Discrete-time Markov chains

Question 1

Define what it means that state j is accessible from state i (for i, j ∈ E)

Answer 1

We say that state j is accessible from state i, written i → j, if the chain may ever
visit state j, with positive probability, starting from i. In other words, i → j if there
exist m ≥ 0 such that pij (m) > 0

Question 2

Define what it means that states i and j communicate (for i, j ∈ E)

Answer 2

States i and j communicate if i → j and j → i, written i ↔ j, i.e. if there exists
n, m ≥ 0 such that pij (n) > 0 and pji(m) > 0.

Question 3

State the Markov condition

Answer 3

P(Xn = j|Xn−1 = i, Xn−2 = xn−2, . . . , X0 = x0) = P(Xn = j|Xn−1 = i)

Question 4

Define what it means for P to be a stochastic matrix and prove that the transition matrix is a stochastic matrix.

Answer 4

1. P has non-negative entries, pij ≥ 0 for all i, j.
2. P has row sums equal to 1; sum of pij = 1 for all i.

pg 16 for proof (law of total probability)

Question 5

Define the n step transition matrix

Answer 5

pij (n) = P(Xm+n = j|Xm = i)

Question 6

State the the Chapman-Kolmogorov equations

Answer 6

pij (m + n) = sum_l (pil(m)plj (n) )
that is
P_{m+n} = P_mP_n,
and
P_n = P^n
pg 18

Question 7

Write the marginal distribution of the chain at time n ∈ N_0

Answer 7

ν^(n)_i = P(Xn = i)

ν^(n) = ν^(0)P_n = ν^(0)P^n

Question 8

Closed / Not closed
Finite / Infinite
Write out the class properties

Answer 8

pg 38

Question 9

What is the value of the elements of a stationary distribution corresponding to transient states?

Answer 9

0

pg 53

Question 10

Define what it means for a vector λ to be a distribution on E

Answer 10

∀ j ∈ E, λj ≥ 0, and Sum_j∈E (λj) = 1

Question 11

What does it mean for λ to be invariant for P?

Answer 11

λP = λ

Question 12

What is the stationary distribution of a Markov chain?

Answer 12

definition for stationary and invariant

Question 13

Stationary distribution of a doubly stochastic matrix

Answer 13

pi_i = 1/n for n=|E|

Question 14

When is X time reversible?

Answer 14

Set Y_n = X_{N-n}
If transition matrices of X and Y are the same.
Iff the detailed balance equations hold (pi_i p_ij = pi_j p_ji)

Question 15

Show by induction that for a discrete Markov chain (Xn)n∈N0, we have
P(Xn+m = xn+m|Xn = xn, . . . , X0 = x0) = P(Xn+m = xn+m|Xn = xn)

Answer 15

PS1 (1)

Question 16

What’s an effective way to compute p_ij(n) ?

Answer 16

Diagonalize P through eigenvalue decomposition (PS1 e7)

Question 17

what is f_00(n)?

Answer 17

The probability that the first return to 0 after starting from 0 is after n steps

Question 18

Define what it means for a state to be recurrent

Answer 18

P(Xn = j for some n ∈ N|X0 = j) = 1

j ∈ E is recurrent if and only if Sum_n^∞ pjj (n) = ∞
fjj = 1

Question 19

Define what it means for a state to be transient

Answer 19

j ∈ E is transient if and only if Sum_n^∞ pjj (n) < ∞
fjj < 1
pij (n) → 0 as n → ∞

Question 20

What is a null and what is a positive recurrent state

Answer 20

A recurrent state i ∈ E is called null if µi = ∞ and positive (or non-null) if µi < ∞.

Question 21

Define the period of a state

Answer 21

d(i) = gcd{ n : p_ii(n) > 0 }

Question 22

Define the first passage time

Answer 22

T_j = min{n : X_n = j}

Question 23

What is the return probability?

Answer 23

f_jj = P(T_j < inf | X_0=j) = sum_{n=1}^inf f_jj(n)

Question 24

Consider a discrete-time homogeneous Markov chain on a countable state space E. Suppose that the Markov chain is irreducible, has a stationary distribution denoted by π and all states are recurrent. What are the values of the stationary distribution?

Answer 24

πi = µ_i ^{−1}

for all i ∈ E, where µ_i denotes the mean recurrence time for state i

Question 25

Define the first passage probability

Answer 25

f_ij(n) = P(T_j = n | X_0=i)

Question 26

What is the mean recurrence time for state i?

Answer 26

µ_i = E[T_i | X_0 = i] = sum_{n=1}^{inf} nf_ii(n)

for i recurrent and inf otherwise

Question 27

Define ergodic state

Answer 27

Positive recurrent and aperiodic

Question 28

What does it mean to say a class is closed? And irreducible?

Answer 28

Closed: impossible to leave the class
Irreducible: all states communicate

Question 29

What does it mean for a state to be aperiodic?

Answer 29

d(i) = 1 or doesn’t exist