Markov Chains

Question 1

Define a state and state-space.

Answer 1

Question 2

When do we call a transition matrix a stochastic matrix?

Answer 2

Question 3

What does the entry p_ij represent?

Answer 3

The probabilitiy of transitioning from state i to state j after one time step.

Question 4

Define a Markov chain.

Answer 4

Question 5

What do we say as a shortened version of a Markov Chain?

Answer 5

Question 6

What is one way to think of a Markov Chain?

Answer 6

Intuitively a Markov chain is a random process where only the current state of the process influences where the chain goes next.

Question 7

What is another way to write property 1 in the following?

Answer 7

X₀ has probability distribution defined by λ where λ = (λ_i : i ∈ I)

Question 8

What is another way to write property 2 in the following?

Answer 8

Probability of a future event conditioned on the past and present is equal to the probability of the future event conditioned on the past.

Question 9

Finish the following theorem.

Answer 9

Question 10

Prove the following theorem.

Answer 10

Question 11

What is another way to write: the future state of a Markov chain is only dependent on its current state?

Answer 11

Question 12

What is the Markov Property theorem?

Answer 12

Question 13

Prove the following theoem.

Answer 13

Question 14

What is a stochastic matrix?

Answer 14

One where the rows sums are equal to 1 and has non-negative entires.

Question 15

What do the following probabilities equal when P is a stochastic matrix that generates a Markov chain with entries: [[1-α, α], [β, 1-β]]?

Answer 15

Question 16

Finish the following theorem.

Answer 16

Question 17

Prove the following theorem.

Answer 17

Question 18

What does p_ij⁽ⁿ⁾ stand for?

Answer 18

The n^th transition probability from i to j.

Question 19

What is Chapman Kolmogorov Equatiosn theorem?

Answer 19

Question 20

Prove the following theorem.

Answer 20

Question 21

If a Markov chain naturally breaks up into separate pieces what are the pieces called?

Answer 21

Communicating classes

Question 22

Define i leads to j.

Answer 22

Question 23

Define i communicates with j.

Answer 23

Question 24

Finish the following theorem.

Answer 24

Question 25

Prove the following theorem.

Answer 25

Question 26

Define when a communicating class is closed.

Answer 26

Question 27

Define when a state i is absorbing.

Answer 27

Question 28

Define when a class is called irreducible.

Answer 28

Question 29

Define hitting time.

Answer 29

Question 30

What does H^A stand for?

Answer 30

The first time that the Markov chain hits the set A.

Question 31

When A is a closed class, what is h_i(A) called?

Answer 31

The absorption property

Question 32

Define the mean time take for (X_n)_n≥0 to reach A.

Answer 32

Question 33

What is the theorem about the vector of hitting probabilites?

Answer 33

Question 34

What is the theorem about the vector of mean hitting times?

Answer 34

Question 35

Prove the following theorem.

Answer 35

Question 36

Define f_ij⁽ⁿ⁾.

Answer 36

Question 37

Define when a state i is recurrent.

Answer 37

Question 38

What is another way to interpret this definition?

Answer 38

Question 39

What is the lemma about the probability, starting from i, of eventually hitting j at least k times?

Answer 39

Question 40

Prove the following Lemma.

Answer 40

Question 41

What is the theorem about i being transient or recurrent?

Answer 41

Question 42

Prove the following theorem.

Answer 42

Question 43

Finish the following thereom.

Answer 43

Question 44

Prove the following theorem.

Answer 44

Question 45

Finish the following Lemma: Every recurrent class is … ?

Answer 45

Every recurrent class is closed.

Question 46

Prove the following Lemma.

Answer 46