Chapter 3

Question 1

A markov chain (X_n) started in a particular fixed state i

Returns to i

Answer 1

Returns to i form a renewal process

Markov property and time homogeneity the future behaviour will be as if process started at i again

Question 2

Renewal process and markov chains:

u_n = p_ii ^(n)

Answer 2

Where p_ii ^(n) denoted the (i,i) element of the n-step transition matrix P^(n) = P^n

Although the matrices equal we don’t say that the elements to the power of n are equal.

Question 3

Renewal process and markov chains:

f_n

Answer 3

f_n of this renewal process will be the probability starting in i of the FIRST return to the state i of the first return to state i being at time n.

P( X₁≉ i, X₂≉ i,…, X_n-1 ≉i, X_n =i | X₀ = i )

Also denoted as f_ii ^(n).

f_ii = sum from n=1 to infinity of f_ii ^(n)

The probability ,, starting in state i, of ever returning to state i.

Question 4

Renewal process and markov chains:
f_ii

When is it recurrent transient

Answer 4

f_ii = sum from n=1 to infinity of f_ii ^(n)

The renewal process is recurrent this will be 1 and the process will keep returning to i

The renewal process is transient then it will be less than 1 (strictly) and eventually with probability 1 the process will visit state i for the last time and never return .

Question 5

Renewal process and markov chains

Transient or recurrent STATES

Period of STATE

RECURRENCE PROPERTIES OF STATES

Answer 5

Any state i of a markov chain is transient or recurrent if it’s corresponding renewal process is

The PERIOD of that state i as the same as the period of the corresponding renewal process

Aperiodic if state with period 1

Question 6

Chapter 3- simple random walk on the integers

+1 -1 etc

Answer 6

Returns to 0 form a renewal process. Shown as transient so renewals got any a in the integers are transient.

We have shown each state is null recurrent if p=0.5. (And symmetric)

If p not 0.5 the random walk is transient and we at some point leave and never come back.

Question 7

Example 17 : c3 mean recurrence time. For the wet dry example

Answer 7

For the wet dry example

P=
[ 1-α α]
[β 1-β]

If chain starts in state 1 wet then with prob 1-α the first return to state 1 happens at time 1:

f₁₁ (¹) = 1-α

And for the first return to state 1 to happen at time n we need to move to state 2 at time t=1 remain until they move back to state 1 at t=n (only 2 states)

f_n ^ (n) = α•(1-β)^n-2 •β
For n bigger than or equal to 2

Follow through

Hence GF of this sequence is

F(s) = (1-α)s + Σ from n=2 to infinity of ( α(1-β)βs^n)

= (1-α)s + (αβs²)/(1-(1-β)^s)

We can check that state is recurrent

F(1)=1

And by finding the mean

F’(1) = (α+β)/β which is finite so the state is POSITIVE RECURRENT and we keep returning

Question 8

Chapter 3:
Delayed renewal process

Delay

Answer 8

For two different states i and j we consider visits state j having started in state i and the DELAY for this DELAYED renewal process is the time until the first visit to j.

Question 9

Chapter 3:
Delayed renewal process

b_n and v_n

Answer 9

Of this renewal process

b_n = f_ij ^(n)

=
P( X₁≉ j, X₂≉ j,…, X_n-1 ≉j, X_n =j | X₀ = i )
(The probability that the first visit to state j happens at time n starting from state i)

v_n = p_ij ^(n)

The (I,j) the element of the Mateo transition matrix.

Question 10

Chapter 3:
Delayed renewal process

Defective delay distribution

First passage probabilities

Answer 10

When starting in state i to never visit state j m, the delay distribution is then defective.

In fact

f_ij = sum from n=1 to infinity
Of f_ij ^(n)

The probability of starting in state i of ever visiting state j.

The probabilities f_ij ^(n) are called first passage probabilities

Question 11

Theorem 8 chapter 3 finite state spaces

Answer 11

If the state space is finite then some of the states must be positive recurrent and the rest, if any, transient.

Proof:

First the finite state spaces cannot all be transient because after process had left each states once nowhere to go. If a state is recurrent….

Question 12

Communication

Answer 12

Two states I and j of a markov chain communicate with each other if it is possible starting in i to get to j (not necessarily next step)

There exist positive integers m and n
Such that
p_ij ^(m) bigger than 0 and p_ij^(n) is bigger than 0

• Symmetric and if I and j communicate j and I do etc
• transitivity: by the chapman kolmogorov we can find m and r st RH is posible then LH is positive. p_ik ^(m+r) ≥ p_ij ^(m) • p_jk ^(r)
• reflexive: states communicate with themselves

Question 13

Communication: equivalence relation

Communicating classes

Answer 13

If a class t is reflexive symmetric and transitive then we have an equivalence class

Communicating classes

Question 14

Irreducible

Answer 14

A markov chain is irreducible if all it’s states communicate with each other

Ie form a single large class

Question 15

Example 18: irreducible markov chains

Answer 15

Ehrenfest model for diffusion all states communicate or a simple random walk on the integers or a CONNECTED graph all vertices allow to get to each other

Not irreducible: gamblers ruin: {0} and {N} don’t communicate so three equivalence classes

Question 16

Solidarity theorem:9

Answer 16

All states within a communicating class share the same recurrence properties

Ie recurrence transience and period
Proof: long

Question 17

Corollary 10: irreducible chain with a finite state space

Answer 17

An irreducible chain with finite state space has all its states positive recurrent.

Question 18

Closed classes

Answer 18

A class is CLOSED if once entered the probability of leaving is 0

Absorbing class

C is classed if p_ij =0 for all i in C and j not in C.

Hence in the irreducible case there is a single class C=S which is automatically closed.

Question 19

If a class is NOT closed

Answer 19

Then once it has been left there is no possibility of returning to it :

If there were such a possibility then there would be at least once state outside the class which communicates with it, a contradiction.

Question 20

Finite state space recurrent class and closed class

Answer 20

If the state spaceS is finite then the concept of a closed class is equivalent to that of a recurrent class and that of a class which is not closed is equivalent of a transient class.

Because if a class is recurrent then impossible to leave it, if it were possible returns wouldn’t happen and contradicts recurrence.

If a class is transient then each state of the class is only visited finitely many times and so the class must eventually be left.?

If state space infinite there are more possibilities. For example in the simple random walk with p not equal to 0.5 all states are transient but they form a single closed class.

Question 21

Example 20?finding classes and recurrence properties

Answer 21

Markov chain has state space {1,2,..,7}

Transition matrix P
= 
[  0 1/2 1/2 0   0   0    0 ]
[  0   0  1/2 0 1/6 1/3  0]
[  0   0    1   0  0   0    0]
[  0   0    0  0 0 0 1]
[1/7  0    0  6/7 0 0 0]
[1/3  0    0.  0 0 0 2/3 ]
[  0   0    0   1 0 0 0]

We can sketch how the states communicate to find that:
•3 can't be left once reached so doesn't communicate with any others and is closed absorbing and aperiodic {3}
• we can check paths (1 -2-6-1 and 1-2-5-1) and so these communicate  {1,2,5,6} closed and period ( 3 moves for both so hcf =3 ) is 3 by solidarity theorem.
•{4,7} don't communicate with others, closed class and can't be left. Even returns only so period 2 by solidarity theorem.

Question 22

Theorem 11: irreducible markov chains and stationary distribution

Answer 22

We have a Markov chain (X_n) which is irreducible and transient (which means state space S is infinite)

then for each state i in S,

P(X_n =i) tends to 0 as n tends to infinity.

furthermore there is no stationary distribution
Proof:

Question 23

Theorem 12/. Markov chain irreducible and aperiodic and has a stat dist then

Answer 23

If a Markov chain (X_n) is irreducible and aperiodic and has a stationary distribution pi,

then the distribution of the state of the Markov chain at time n converges to pi

Vector(π) ^(n) converges to vector(π) as n tends to infinity

Proof: coupling arguement

Question 24

Corollary 13:

Markov chain irreducible and aperiodic with stationary distribution

Answer 24

F a Markov chain is irreducible and a periodic and has a stationary distribution pi than that stationary distribution is unique

Proof: contradiction

Question 25

Theorem 14: with an irreducible and positive recurrent mark off chain we can construct a stationary distribution

Answer 25

For each state j let μ_j be the expected time until the first return to state j given the gain starts there . Vecror(π) is row vector with entry j 1/μ_j for j in the sample space.

Assume The markov Chain is irreducible aperiodic and positive recurrent then

a) The distribution is a stationary distribution and is unique
b) The distribution of the state of the Markov chain at time and converges to pi

Ie Vector(π) ^(n) converges to vector(π) as n tends to infinity

(
Theorem 12 and corollary 13)

Because pi is unique we can find it by solving equilibrium equations and apply the above results

Question 26

Example 21: modelling a game of monopoly.

Answer 26

NOTES…

Question 27

To summarise: 3 pages left

Answer 27

H