Math Problems Vault

Problem 28.1

Determine the number of states of the Markov chain, its equivalence classes, and the periodicity of the various states, if the matrix of transition probabilities equals:

\begin{bmatrix} 1/2 & 1/3 & 1/6 \\ 1/2 & 1/3 & 1/6 \\ 1/2 & 1/3 & 1/6 \end{bmatrix}.

?

Remark.

?

A state $x_i$ is called inessential if there exists a state $x_j \neq x_i$ and a time $n$ such that the probability of transitioning from state $x_i$ to $x_j$ in time $n$ is greater than zero, but it is impossible to transition back from state $x_j$ to $x_i$ . A state is called essential if it is not inessential. Essential states $x_i$ and $x_j$ are called communicating if the probability of transitioning from $x_i$ to $x_j$ in some amount of time is greater than zero, and simultaneously the probability of transitioning back from $x_j$ to $x_i$ in some amount of time is also greater than zero. A set $S$ of pairwise communicating states is called an equivalence class if it contains every state that communicates with the states of $S$ . If an equivalence class $S$ consists of a single state, that state is called an absorbing state. A Markov chain is called irreducible if all of its states form a single equivalence class, and reducible if its states form at least two equivalence classes. A state $x_i$ is called periodic with period $d_i$ if a return to that state with positive probability is possible only after a number of steps that is a multiple of $d_i$ , and $d_i$ is the largest number with this property; a chain is called aperiodic if all states have period equal to $1$ .

Problem 28.2

Determine the number of states of the Markov chain, its equivalence classes, and the periodicity of the various states, if the matrix of transition probabilities equals:

\begin{bmatrix} 0 & 1/2 & 1/2 \\ 1/2 & 0 & 1/2 \\ 1/2 & 1/2 & 0 \end{bmatrix}.

?

Problem 28.3

Determine the number of states of the Markov chain, its equivalence classes, and the periodicity of the various states, if the matrix of transition probabilities equals:

\begin{bmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1/2 & 1/2 & 0 \\ 1/3 & 1/3 & 1/3 & 0 \end{bmatrix}.

?

Problem 28.4

Determine the number of states of the Markov chain, its equivalence classes, and the periodicity of the various states, if the matrix of transition probabilities equals:

\begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1/3 & 0 & 2/3 & 0 \end{bmatrix}.

?

Problem 28.5

Determine the number of states of the Markov chain, its equivalence classes, and the periodicity of the various states, if the matrix of transition probabilities equals:

\begin{bmatrix} 1/3 & 2/3 & 0 & 0 & 0 & 0 \\ 2/3 & 1/3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1/4 & 3/4 & 0 \\ 0 & 0 & 1/5 & 4/5 & 0 & 0 \\ 1/4 & 0 & 1/4 & 0 & 1/4 & 1/4 \\ 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 \end{bmatrix}.

?

Problem 28.6

Determine the number of states of the Markov chain, its equivalence classes, and the periodicity of the various states, if the matrix of transition probabilities equals:

\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 3/4 & 1/4 & 0 & 0 & 0 & 0 \\ 0 & 1/8 & 7/8 & 0 & 0 & 0 \\ 0 & 1/4 & 1/4 & 0 & 1/8 & 3/8 \\ 0 & 1/3 & 0 & 1/6 & 1/6 & 1/3 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}.

?

Problem 28.7

Classify the states of the Markov chain with transition probability matrix

\begin{bmatrix} p & 1-p & 0 \\ 0 & p & 1-p \\ 1-p & 0 & p \end{bmatrix}.

?

Problem 28.8

Is the Markov chain with the following one-step transition probability matrix ergodic?

\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}.

?

Problem 28.9

Is the Markov chain with the following one-step transition probability matrix ergodic?

\begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix}.

?

Problem 28.10

Is the Markov chain with the following one-step transition probability matrix ergodic?

\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}.

?

Problem 28.11

Is the Markov chain with the following one-step transition probability matrix ergodic?

\begin{bmatrix} 1/2 & 1/2 \\ 0 & 1 \end{bmatrix}.

?

Problem 28.12

Is the Markov chain with the following one-step transition probability matrix ergodic?

\begin{bmatrix} 1/2 & 1/2 \\ 1 & 0 \end{bmatrix}.

?

Problem 28.13

Let $\{ \xi_n\}$ be a Markov chain with values in $\mathbb {Z}_+$ and transition probabilities

p_{ij} = \begin{cases} \lambda ^{j-i} e^{-\lambda }/(j-i)!, & \text{if } j \geqslant i, \\ 0, & \text{otherwise.} \end{cases}

Prove that the chain $\{ \xi_n\}$ has no invariant distribution.

?

Problem 28.14

Let $\{ \xi_n\}$ be a random walk with reflection at the points $0$ and $N$ , i.e., a Markov chain with values in $\{ 0, \ldots , N\}$ and transition probabilities $p_{i,i+1} = p_{i,i-1} = 1/2$ for $0 < i < N$ , $p_{0,1} = p_{N,N-1} = 1$ . Prove that the chain $\{ \xi_n\}$ is ergodic and find its invariant distribution.

?

Problem 28.15

Consider a random walk on the integer segment $[0, N]$ , where $p_{i,i+1} = 1 - p_{i,i-1} = p$ for $i = 1, \ldots , N-1$ and $p_{0,0} = p_{N,N} = 1$ . Find the probability of absorption at state $0$ or $N$ , given that the initial state is $k$ .

?

Problem 28.16

Let $P = \left\| p_{ij}\right\|$ be the transition probability matrix of an irreducible Markov chain. Prove that if the matrix $P$ is idempotent (i.e., $P = P^2$ ), then $p_{ij} = p_{jj}$ for all $i$ and $j$ , and the chain is aperiodic.

?

Problem 28.17

Prove that if the number $N$ of states of a Markov chain is finite and state $j$ is reachable from state $i$ , then it is reachable in at most $N-1$ steps.

?

Problem 28.18

Prove that an irreducible Markov chain in which at least one diagonal entry of the transition matrix is positive cannot be periodic.

?

Problem 28.19

Can all states of a Markov chain with finitely many states be inessential?

?

Problem 28.20

Can all states of a Markov chain with countably many states be inessential?

?

Problem 28.21

Show that a non-ergodic Markov chain can have an invariant distribution, and moreover a unique one.

?

Problem 28.22

Consider an irreducible Markov chain with state space $\{ 0, 1, 2, \ldots \}$ . Prove that a necessary and sufficient condition for the chain to be transient is that the system of equations

u_i = \sum _{j=0}^{\infty } p_{ij} u_j, \qquad i \geqslant 1,

have a bounded solution that is not identically constant.

?

Problem 28.23

Consider an irreducible Markov chain with state space $\{ 0, 1, 2, \ldots \}$ . Prove that a sufficient condition for the chain to be recurrent is the existence of a sequence $u_1, u_2, \ldots$ such that $u_i \to \infty$ as $i \to \infty$ and, for all $i \neq 0$ ,

u_i \geqslant \sum _{j=0}^{\infty } p_{ij} u_j.

?

Problem 28.24

Consider an irreducible Markov chain with state space $\{ 0, 1, 2, \ldots \}$ . Prove that a necessary and sufficient condition for the chain to be positive recurrent is that the system of equations

u_j = \sum _{i=0}^{\infty } u_i p_{ij}, \qquad j = 0, 1, \ldots ,

have a solution that is not identically constant and for which $\displaystyle \sum_{i=0}^{\infty } \left|u_i\right| < \infty$ .

?

Problem 28.25

Consider a Markov chain $\xi_n$ with values $0, 1, 2, \ldots , m-1$ and with one-step transition probability matrix

\begin{bmatrix} p_0 & p_1 & \ldots & p_{m-1} \\ p_{m-1} & p_0 & \ldots & p_{m-2} \\ \ldots & \ldots & \ldots & \ldots \\ p_1 & p_2 & \ldots & p_0 \end{bmatrix},

where $0 \leqslant p_i < 1$ , $\sum p_i = 1$ . Prove that for every $i$ the probability $\mathbb {P}\left(\xi_n = i\right)$ converges to $1/m$ as $n \to \infty$ .

?

Problem 28.26

Consider a Markov chain $\xi_n$ with values $0, 1, 2, \ldots$ and with one-step transition probability matrix

\begin{bmatrix} p_0 & p_1 & p_2 & \ldots \\ 1 & 0 & 0 & \ldots \\ 0 & 1 & 0 & \ldots \\ 0 & 0 & 1 & \ldots \\ \ldots & \ldots & \ldots & \ldots \end{bmatrix}.

Determine the conditions for recurrence and for positive recurrence of state $0$ .

?

Problem 28.27

(a)(b)

Under the conditions of Problem 28.26, determine the conditions on the probabilities $\{ p_i\}$ and the function $f: \{ 0, 1, 2, \ldots \} \to \mathbb {R}$ under which the sequence $f(\xi_n)$ satisfies:

?

(a)

the law of large numbers;

(b)

the central limit theorem.

Problem 28.28

Consider a Markov chain $\xi_n$ with values $0, 1, 2, \ldots$ and with one-step transition probability matrix

\begin{bmatrix} p_0 & 1-p_0 & 0 & 0 & \ldots \\ p_1 & 0 & 1-p_1 & 0 & \ldots \\ p_2 & 0 & 0 & 1-p_2 & \ldots \\ \ldots & \ldots & \ldots & \ldots & \ldots \end{bmatrix}.

Determine the conditions for recurrence and for positive recurrence of state $0$ .

?

Problem 28.29

(a)(b)

Under the conditions of Problem 28.28, determine the conditions on the probabilities $\{ p_i\}$ and the function $f: \{ 0, 1, 2, \ldots \} \to \mathbb {R}$ under which the sequence $f(\xi_n)$ satisfies:

?

(a)

the law of large numbers;

(b)

the central limit theorem.

Problem 28.30

Prove that if an eigenvalue $\lambda$ of a finite stochastic matrix has absolute value $1$ , then $\lambda = \sqrt[n]{1}$ for some natural number $n$ .

?

Problem 28.31

Prove that if a finite stochastic matrix has two distinct eigenvalues of absolute value $1$ , then the corresponding Markov chain is not ergodic.

?

Problem 28.32

Let $\xi_n$ be an ergodic Markov chain with values $0, 1, 2, \ldots$ and limiting probabilities $\{ \pi_i\}_{i=0}^{\infty }$ . Set

\zeta _n = \sum _{i=1}^{n} \; \mathbb {1}_{\xi _i = k}.

Prove that $\zeta_n / n \to \pi_k$ in probability.

?

Problem 28.33

Let $\xi_n$ be an ergodic Markov chain with values $0, 1, 2, \ldots$ . Prove that for any sets $A$ and $B$ , as $\left|n-m\right| \to \infty$ ,

\left|\mathbb {P}\left(\xi _n \in A, \xi _m \in B\right) - \mathbb {P}\left(\xi _n \in A\right) \mathbb {P}\left(\xi _m \in B\right)\right| \to 0.

?