Markov Chains

Question 1

How do you find two-step probabilities?

Answer 1

P*P

Question 2

What is an accesible state?

Answer 2

State j is said to be accessible from state i if, when being in state i there is a positive probability of going to state j in a finite number of steps. We write i → j.

Question 3

What is a class?

Answer 3

The state space S can be divided into classes of states where all states in a class communicate with each other and not with any state in any other class.

Question 4

What is an irreducble markov chain?

Answer 4

If there is only on class, i.e. all states communicate, the Markov chain is called irreducible.
i.e. you are able to return to any state.

Question 5

What is an absorbing state?

Answer 5

States that are impossible to get out of

Question 6

What is a recurrent and transient states?

Answer 6

For a Markov chain let Ri denote the probability that starting from state i, the process will ever return to state i. We say that state i is
* Recurrent if Ri = 1 (guaranteed to return)
* Transient if Ri < 1 (not guaranteed to return)
If a state is recurrent, in the long run the process will return to the state infinitely many times. For a transient state the process will only return a finite number of times.

• Transient states are only visited a finite number of times.
• A finite-state Markov chain has at least one recurrent state.
• If one state in a class is recurrent, all states in the class are.
• If one state in a class is transient, all states in the class are.
• In an irreducible Markov chain all states are either recurrent or transient.
• In a finite irreducible Markov chain, all states are recurrent.
• Once a Markov chain enters a recurrent class, it will remain in that class forever.

Question 7

What is a positive recurrent markov chain?

Answer 7

For a Markov chain with finite state space, all recurrent states are positive recurrent.

Question 8

What is the period in a markov chain?

Answer 8

The period of a state i in a Markov chain is the greatest common divisor. If the period is 1, the state is called aperiodic. All states in a class have the same period.

Question 9

What characteristics does a markov chain need to have steady state probabilities?

Answer 9

• Irreducible (one state)
• Positive recurrent (recurrent, will return)
• Aperiodic (gdc = 1)

For finite space we only need irreducible and aperiodic

Question 10

How do we find steady state probabilities?

Answer 10

Π = P^T* Π

Question 11

Continious markov chains

Question 12

How do you prove some process is a markov chain?

Answer 12

Does not need previous info.
X_n+1depends only on Xn.

Question 13

What is a birth and death process?

Answer 13

• Only able to move up in steps of one
• Only move down in steps of one.