Math Problems Vault

Problem 9.1

Prove that for any stochastic matrix $P$ there exists a probability space and a sequence of random variables on it forming a Markov chain with matrix of one-step transition probabilities $P$ .

?

Problem 9.2

Can every stochastic matrix be the matrix of two-step transition probabilities of some Markov chain?

?

Problem 9.3

It is known that a Markov chain is completely determined by its initial distribution and its matrix of one-step transition probabilities. Is a Markov chain determined by its initial distribution and its matrix of two-step transition probabilities?

?

Problem 9.4

Prove that a second-order stochastic matrix is the matrix of two-step transition probabilities of some Markov chain if and only if the sum of its diagonal entries is greater than or equal to one.

?

Problem 9.5

Determine for which values of $c$ and $d$ the Markov chain is uniquely determined by its initial distribution and its matrix of two-step transition probabilities:

P^{\prime 2} =\left[\begin{smallmatrix} c & 1-c \\ 1-d & d \end{smallmatrix}\right] .

?

Problem 9.6

(a)(b)(c)

Prove that for a Markov chain $\xi_{0}, \xi_{1}, \ldots$ , for any $0 \leqslant k \leqslant n-1$ :

?

(a)

$\mathbb {P}\left( \xi_{n} = i_{n} \mid \xi_{n-1} = i_{n-1}, \ldots , \xi_{k} = i_{k} \right) = \mathbb {P}\left( \xi_{n} = i_{n} \mid \xi_{n-1} = i_{n-1} \right)$ ;

(b)

$\mathbb {P}\left( \xi_{n} = i_{n}, \ldots , \xi_{k+1} = i_{k+1} \mid \xi_{k} = i_{k}, \ldots , \xi_{0} = i_{0} \right) =$

= \mathbb {P}\left( \xi _{n} = i_{n}, \ldots , \xi _{k+1} = i_{k+1} \mid \xi _{k} = i_{k} \right) ;

(c)

$\mathbb {P}\left( \xi_{n} = i_{n} \mid \xi_{k} = i_{k}, \ldots , \xi_{0} = i_{0} \right) = \mathbb {P}\left( \xi_{n} = i_{n} \mid \xi_{k} = i_{k} \right)$ .

Problem 9.7

Let $A$ be an event depending only on the states of the Markov chain at the first $n-1$ steps, and let $B$ be an event depending on the states at steps $(n+1), \ldots , (n+m)$ . Prove that, conditional on the state at step $n$ being fixed, the events $A$ and $B$ are independent.

?

Problem 9.8

Let $\xi_{0}, \xi_{1}, \ldots$ be a Markov chain. Prove that for any $0 \leqslant n_{i} \leqslant n$

\mathbb {P}\left( \xi _{n+1} = i_{n+1} \mid \xi _{n_{1}} = i_{n_{1}}, \ldots , \xi _{n_{k}} = i_{n_{k}} \right) = \mathbb {P}\left( \xi _{n+1} = i_{n+1} \mid \xi _{n_{s}} = i_{n_{s}} \right),

where $n_{s} = \max \left\{ n_{i}\right\}$ .

?

Problem 9.9

Let the random variable $\tau$ be independent of the homogeneous Markov chain $\xi_{0}, \xi_{1}, \ldots$ and take nonnegative integer values. Prove that for any $n \geqslant 1$ and any $i_{0}, \ldots , i_{n+1}$

\mathbb {P}\left( \xi _{\tau +n+1} = i_{n+1} \mid \xi _{\tau +n} = i_{n}, \ldots , \xi _{\tau } = i_{0} \right) = \mathbb {P}\left( \xi _{\tau +n+1} = i_{n+1} \mid \xi _{\tau +n} = i_{n} \right) ;

Do these equalities still hold if the Markov chain $\xi_{0}, \xi_{1}, \ldots$ is inhomogeneous?

?

Problem 9.10

Let $\tau_{1}, \tau_{2}, \ldots$ be a sequence of independent, positive, integer-valued random variables, independent of the Markov chain $\xi_{0}, \xi_{1}, \ldots$ Prove that

\begin{aligned} \mathbb {P}\left( \xi _{\tau _{1}+\ldots +\tau _{n}} = i_{n} \mid \xi _{\tau _{1}+\ldots +\tau _{n-1}} = i_{n-1}, \ldots , \xi _{\tau _{1}} = i_{1} \right) & = \\ & = \mathbb {P}\left( \xi _{\tau _{1}+\ldots +\tau _{n}} = i_{n} \mid \xi _{\tau _{1}+\ldots +\tau _{n-1}} = i_{n-1} \right) . \end{aligned}

?

Problem 9.11

A Markov chain has matrix of one-step transition probabilities

P^{(1)} =\left[\begin{smallmatrix} 1-a & a \\ b & 1-b \end{smallmatrix}\right] .

Find the matrix of $n$ -step transition probabilities and its limit as $n \rightarrow \infty$ .

?

Problem 9.12

Let, in the matrix of one-step transition probabilities of a Markov chain with three states,

P_{i j} = \begin{cases} P_{1, i-j+1}, & i \geqslant j, \\ P_{1, j-i+1}, & j > i . \end{cases}

Find the matrix of $n$ -step transition probabilities and its limit as $n \rightarrow \infty$ .

?

Problem 9.13

In the matrix of one-step transition probabilities $P$ ,

P_{i j} = \begin{cases} P_{1, j-i+1}, & j \geqslant i, \\ P_{i-j+1,1}, & j < i . \end{cases}

Prove that analogous relations hold for the $m$ -step transition probabilities.

?

Problem 9.14

Let $P_{i j}^{(n)}$ be the probability of an $n$ -step transition from state $i$ to state $j$ of some Markov chain,

\alpha _{j}(n) = \min _{i} P_{i j}^{(n)}, \quad \beta _{j}(n) = \max _{i} P_{i j}^{(n)} .

Prove that

\alpha _{j}(1) \leqslant \alpha _{j}(2) \leqslant \ldots \leqslant \alpha _{j}(n) \leqslant \ldots \leqslant \beta _{j}(n) \leqslant \ldots \leqslant \beta _{j}(2) \leqslant \beta _{j} . \tag {1}

?

Problem 9.15

Let the sequence of random variables $\xi_{0}, \xi_{i}, \ldots$ form a Markov chain. Prove that any subsequence of the sequence $\xi_{0}, \xi_{1}, \ldots$ also forms a Markov chain.

?

Problem 9.16

Let $\xi_{0}, \xi_{1}, \ldots$ be a sequence of independent identically distributed integer-valued random variables. Prove that it forms a Markov chain. Find the matrix of $n$ -step transition probabilities.

?

Problem 9.17

Let $\xi_{0}, \xi_{1}, \ldots$ be a sequence of random variables forming a homogeneous Markov chain. Prove that for the random variables $\xi_{0}, \xi_{1}, \ldots$ to be independent, it is necessary and sufficient that all rows of the matrix of one-step transition probabilities be identical.

?

Problem 9.18

Let $\xi_{0}, \xi_{1}, \ldots$ be a sequence of pairwise independent (not necessarily mutually independent) random variables. Do $\xi_{0}, \xi_{1}, \ldots$ form a Markov chain?

?

Problem 9.19

(a)(b)(c)

Points $A_{1}, \ldots , A_{n}$ are the vertices of a regular $n$ -gon. A particle performs a random walk on the points $A_{1}, \ldots , A_{n}$ . Determine whether the sequence of positions of the particle is a Markov chain if

?

(a)

the particle moves deterministically clockwise;

(b)

at the initial moment the particle randomly chooses a direction, clockwise or counterclockwise, and thereafter always moves in the chosen direction;

(c)

from any point $A_{i}, i \neq 1$ , the particle moves with probability $p$ clockwise, and with probability $q = 1-p$ counterclockwise, to the neighboring point. Upon reaching point $A_{1}$ , the particle returns to the point from which it arrived at $A_{1}$ .

Problem 9.20

(a)(b)(c)

A particle performs a random walk in the plane on integer points $(i, j)$ such that $0 \leqslant i, j \leqslant n$ . From any interior point of the given square, the particle, independently of its previous motion, moves with equal probabilities to one of the neighboring (vertically or horizontally adjacent) points. Upon reaching the boundary of the square, the particle then:

?

(a)

moves along the boundary of the square deterministically, clockwise;

(b)

returns to the point from which it reached the boundary;

(c)

randomly chooses a direction along the boundary and moves along the boundary in the chosen direction.

For each of the indicated cases, determine whether the sequence of positions occupied by the particle is a Markov chain.

Problem 9.21

(a)(b)(c)

Under the conditions of the previous problem, the particle from each interior point can move with equal probability to one of the neighboring points (horizontally, vertically, or diagonally). Is the sequence of positions of the particle a Markov chain for each of the three motion conditions upon reaching the boundary indicated in the previous problem?

?

(a)

(b)

(c)

Problem 9.22

At the initial moment of time an urn contains $n_{0}$ white and $m_{0}$ black balls. Every unit of time, one ball is drawn from the urn according to sampling without replacement. Let $n_{k}$ be the number of white balls and $m_{k}$ the number of black balls in the urn at time $k$ . Which of the following sequences form a Markov chain and which do not:

?

(a)

$n_{k}$ ,

(b)

$n_{k}-m_{k}$ ,

(c)

$n_{k}+m_{k}$ ,

(d)

the pair ( $n_{k}, m_{k}$ ),

(e)

$n_{k}-m_{k} + 1 /\left(n_{k}+m_{k}+2\right)$ ?

Problem 9.23

Let the random variables $\xi_{0}, \ldots , \xi_{n}$ form a Markov chain. Prove that the random variables $\eta_{0}, \ldots , \eta_{n}$ , where $\eta_{i} = \xi_{n-i}$ , also form a Markov chain. Do the random variables $\zeta_{0}, \ldots , \zeta_{n}$ , where $\zeta_{0}, \ldots , \zeta_{n}$ is an arbitrary permutation of $\xi_{0}, \ldots , \xi_{n}$ , form a Markov chain?

?

Problem 9.24

Let $\xi_{0}, \xi_{1}, \ldots$ be a sequence of independent random variables. Does the sequence $\xi_{0}+\xi_{1}$ , $\xi_{1}+\xi_{2}, \xi_{2}+\xi_{3}, \ldots$ form a Markov chain?

?

Problem 9.25

Let $\xi_{0}, \xi_{1}, \ldots$ be a sequence of random variables forming a Markov chain. Is the sequence $\xi_{0}+\xi_{1}, \xi_{2}+\xi_{3}, \xi_{4}+\xi_{5}, \ldots$ a Markov chain?

?

Problem 9.26

A Markov chain with a finite number of states is given. Let $\xi_{i}$ be the state of the chain at step $i$ . Is the sequence $\eta_{0}, \eta_{1}, \ldots$ , where

\eta _{i} = \begin{cases} 1, & \text{ if } \xi _{i} = x_{1}, \\ 0, & \text{ if } \xi _{i} \neq x_{1} . \end{cases}

a Markov chain?

?

Problem 9.27

(a)(b)(c)

Let $\xi_{0}, \xi_{1}, \ldots$ be a sequence of independent identically distributed random variables taking values $-1$ and $+1$ with probabilities $p$ and $q = 1-p$ respectively. Set:

?

(a)

$\eta_{n} = \xi_{n} \xi_{n+1}$ ;

(b)

$\eta_{n} = \max_{0 \leqslant i \leqslant n} \xi_{i}$ ;

(c)

$\eta_{n} = \prod_{i = 0}^{n} \xi_{i}$ .

Is the sequence $\eta_{0}, \eta_{1}, \ldots$ a Markov chain?

Problem 9.28

Let $\xi_{0}, \xi_{1}, \ldots$ be a sequence of independent integer-valued random variables, with

\mathbb {P}\left(\xi _{n} = k\right) = p_{k}, \quad k = 0, \pm 1, \pm 2, \ldots

Set $\eta_{n} = \xi_{0}+\ldots +\xi_{n}$ . Prove that the sequence $\eta_{0}, \eta_{1}, \ldots$ forms a Markov chain. Find the corresponding matrix of one-step transition probabilities.

?

Problem 9.29

Let $\xi_{0}, \xi_{1}, \ldots$ and $\eta_{0}, \eta_{1}, \ldots$ be two Markov chains. Is the sequence $\xi_{0}+\eta_{0}, \xi_{1}+\eta_{1}, \ldots$ a Markov chain?

?

Problem 9.30

Let $\left(\xi_{1}^{(i)}, \ldots , \xi_{n}^{(i)}\right), \quad i \geqslant 1$ , be a sequence of independent identically distributed random vectors, and let $\xi_{0}$ be a random variable independent of $\left\{ \left(\xi_{1}^{(i)}, \ldots , \xi_{n}^{(i)}\right)\right\} , i = 1,2, \ldots$ . Let $\xi_{0}$ and $\xi_{j}^{(i)}$ take values $1, \ldots , n$ . Construct a sequence of random variables $\eta_{0}, \eta_{1}, \ldots$ as follows:

\eta _{0} = \xi _{0}, \quad \eta _{i} = \xi _{\eta _{i-1}}^{(i)}, \quad i \geqslant 1.

Prove that the sequence $\eta_{0}, \eta_{1}, \ldots$ forms a Markov chain.

?

Problem 9.31

For the Markov chain defined in the previous problem, find the number of states, the matrix of one-step transition probabilities, and the vector of initial probabilities, if

\mathbb {P}\left(\xi _{i}^{(1)} = j\right) = p_{i j}, \quad i = 0,1, \ldots , n ; \quad j = 1,2, \ldots , n .

?

Problem 9.32

Prove that any Markov chain with a finite number of states can be represented as a sequence of random variables $\eta_{0}, \eta_{1}, \ldots$ , as defined in problem 9.30.

?

Problem 9.33

Let $\xi_{0}, \xi_{1}, \ldots$ be independent random variables with a discrete distribution, and let $f_{0}, f_{1}, \ldots$ be some functions. Prove that the sequence of random variables $\eta_{1}, \eta_{2}, \ldots$ , where $\eta_{k+1} = f_{k}\left(\eta_{k}, \xi_{k+1}\right)$ , forms a Markov chain.

?

Problem 9.34

Let $\xi_{0}, \xi_{1}, \ldots$ be a sequence of random variables forming a Markov chain, and let $f(x)$ be some function. Is the sequence $f\left(\xi_{0}\right), f\left(\xi_{1}\right), \ldots$ a Markov chain?

?

Problem 9.35

Let $\xi_{0}, \xi_{1}, \ldots$ be a Markov chain with countable state space $\left\{ 1,2, \ldots \right\}$ and matrix of one-step transition probabilities $P$ , where the states $1,2, \ldots , N$ are recurrent. Set

\begin{gathered} v_{0} = \min \left(i: \xi _{i} \leqslant N\right), \quad v_{n} = \min \left(i > v_{n-1}: \xi _{i} \leqslant N\right), \quad n \geqslant 1, \\ \eta _{j} = \xi _{v_{j}} . \end{gathered}

Prove that the sequence $\eta_{0}, \eta_{1}, \ldots$ forms a Markov chain. Find the matrix of one-step transition probabilities.

?

Problem 9.36

For every Markov chain $\xi_{0}, \xi_{1}, \ldots$ with countable state space $\left\{ 1,2, \ldots \right\}$ , can one choose a sequence of random variables $\zeta_{0}, \zeta_{1}, \ldots$ , mutually independent and independent of $\xi_{0}, \xi_{1}, \ldots$ , with values in the set $\left\{ 1,2, \ldots , N\right\}$ , such that the sequence $\eta_{0}, \eta_{1}, \ldots$ , where

\eta _{i} = I\left(\xi _{i} \leqslant N\right) \xi _{i}+I\left(\xi _{i} > N\right) \zeta _{i},

is a Markov chain?

?

Problem 9.37

Let $\xi_{0}, \xi_{1}, \ldots$ be a sequence of digits, in which the digits appear randomly, independently of one another, and with equal probability. There is a counter which at time $n$ shows how many distinct digits have occurred among the first $n$ digits of the sequence $\xi_{0}, \xi_{1}, \ldots$ Prove that the counter's readings form a Markov chain. Find the matrix of one-step transition probabilities. Indicate the essential and inessential states.

?

Problem 9.38

A particle performs a random walk on the line over the integer points $0,1, \ldots , n$ . From any interior point the particle moves with probability $p$ one step to the right or, with probability $q = 1-p$ , one step to the left. Upon reaching points 0 and $n$ the particle remains there forever (absorbing barriers). Find the matrix of one-step transition probabilities. Indicate the essential and inessential states.

?

Problem 9.39

A particle performs a random walk on the line over the integer points $0,1, \ldots , n$ . From any interior point the particle moves with probability $p$ one step to the right or, with probability $q = 1-p$ , one step to the left. Upon reaching points 0 and $n$ , the particle at the next moment of time moves with probability 1 to points 1 or $n-1$ respectively (reflecting barriers). Find the matrix of one-step transition probabilities. Indicate the essential and inessential states.

?

Problem 9.40

Indicate the essential and inessential states of the Markov chain with matrix of one-step transition probabilities

P =\left[\begin{smallmatrix} 1 / 4 & 1 / 4 & 0 & 0 & 1 / 2 \\ 1 / 3 & 0 & 1 / 3 & 1 / 3 & 0 \\ 1 / 2 & 0 & 0 & 0 & 1 / 2 \\ 0 & 0 & 0 & 1 / 2 & 1 / 2 \\ 0 & 0 & 0 & 1 & 0 \end{smallmatrix}\right] .

?

Problem 9.41

Can all states of a Markov chain with a finite number of states be inessential?

?

Problem 9.42

Can all states of a Markov chain with a countable number of states be inessential?

?

Problem 9.43

The matrix of one-step transition probabilities of a Markov chain has the form

P =\left[\begin{smallmatrix} 1 / 4 & 1 / 4 & 1 / 4 & 1 / 4 \\ 0 & 1 / 2 & 1 / 2 & 0 \\ 0 & 1 / 2 & 1 / 2 & 0 \\ 1 & 0 & 0 & 0 \end{smallmatrix}\right] .

Indicate all pairs of communicating states.

?

Problem 9.44

(a)(b)

A Markov chain has $r$ states. Prove that:

?

(a)

if the $j$ -th state is accessible from the $i$ -th ( $i \neq j$ ), then it can be reached in fewer than $r$ steps;

(b)

if the probability of returning to state $i$ is positive, then the return can occur in $r$ or fewer steps.

Problem 9.45

(a)(b)(c)

Is the Markov chain with matrix of one-step transition probabilities $P$ periodic, if

?

(a)

$P = \left(\begin{array}{llll}0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{array}\right)$ ,

(b)

$P = \left(\begin{array}{cccccc}0 & 1 / 2 & 0 & 1 / 2 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 / 2 & 0 & 1 / 2 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0\end{array}\right)$ ,

(c)

$P = \left(\begin{array}{cccc}1 / 2 & 1 / 2 & 0 & 0 \\ 0 & 1 / 2 & 1 / 2 & 0 \\ 0 & 0 & 1 / 2 & 1 / 2 \\ 1 / 2 & 0 & 0 & 1 / 2\end{array}\right)$ .

For periodic chains, indicate the period.

Problem 9.46

(a)(b)

?

(a)

Prove that an irreducible chain, in whose matrix of transition probabilities at least one diagonal entry $P_{j j}$ is positive, cannot be periodic.

(b)

Can an irreducible chain in which all diagonal entries equal zero be aperiodic?

Problem 9.47

Prove that a finite irreducible Markov chain is aperiodic if and only if there exists $n$ such that $P_{i j}^{(n)} > 0$ for all $i$ and $j$ .

?

Problem 9.48

Indicate the recurrent and transient states of the Markov chain with matrix of one-step transition probabilities

P =\left[\begin{smallmatrix} 0 & 1 / 2 & 1 / 2 & 0 & 0 & 0 \\ 0 & 0 & 1 / 2 & 1 / 2 & 0 & 0 \\ 0 & 0 & 0 & 1 / 2 & 1 / 2 & 0 \\ 0 & 0 & 0 & 0 & 1 / 2 & 1 / 2 \\ 1 / 2 & 0 & 0 & 0 & 0 & 1 / 2 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{smallmatrix}\right] .

?

Problem 9.49

(a)(b)(c)(d)

Prove that all states of the Markov chain with matrix of transition probabilities $P$ are recurrent, if

?

(a)

$P = \left(\begin{array}{ll}1 & 0 \\ 0 & 1\end{array}\right)$ ;

(b)

$P = \left(\begin{array}{cccc}1 / 2 & 0 & 1 / 2 & 0 \\ 0 & 1 / 2 & 0 & 1 / 2 \\ 1 / 2 & 0 & 1 / 2 & 0 \\ 0 & 1 / 2 & 0 & 1 / 2\end{array}\right)$ ;

(c)

$P = \left(\begin{array}{cccc}1 / 2 & 1 / 2 & 0 & 0 \\ 1 / 2 & 1 / 2 & 0 & 0 \\ 0 & 0 & 1 / 2 & 1 / 2 \\ 0 & 0 & 1 / 2 & 1 / 2\end{array}\right)$ ;

(d)

$P = \left(\begin{array}{cccccc}1 / n & 0 & 1 / n & 0 & \ldots & \ldots \\ 0 & 1 / n & 0 & 1 / n & \ldots & \ldots \\ 1 / n & 0 & 1 / n & 0 & \ldots & \ldots \\ \ldots & \ldots & \ldots & \ldots & \ldots & .\end{array}\right)$ .

Problem 9.50

Prove that if the $j$ -th state is transient, then for all $i$ , $\sum_{n = 1}^{\infty } P_{i j}^{(n)} < \infty$ .

?

Problem 9.51

Prove that any Markov chain with a finite number of states has at least one recurrent state.

?

Problem 9.52

Can all states of a Markov chain with a countable number of states be transient?

?

Problem 9.53

Prove that for a finite Markov chain a state is recurrent if and only if it is essential. Show that this is false for chains with a countable number of states.

?

Problem 9.54

There is a Markov chain with a countable number of states and matrix of one-step transition probabilities

P =\left[\begin{smallmatrix} p_{1} & 1-p_{1} & 0 & 0 & 0 & \ldots & \ldots \\ p_{2} & 0 & 1-p_{2} & 0 & 0 & \ldots & \ldots \\ p_{3} & 0 & 0 & 1-p_{3} & 0 & \ldots & \ldots \\ & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \end{smallmatrix}\right]

Prove that if the series $\sum_{i = 1}^{\infty } p_{i}$ converges, then all states of this chain are recurrent; otherwise they are transient.

?

Problem 9.55

(a)(b)

Let all states of the Markov chains with matrices of one-step transition probabilities $A$ and $B$ be recurrent. Prove that all states of the Markov chain with matrix of transition probabilities are recurrent:

?

(a)

$\left(\begin{array}{ll}A & 0 \\ 0 & B\end{array}\right)$ ;

(b)

$\left(\begin{array}{cc}0 & A \\ B & 0\end{array}\right)$ .

Problem 9.56

Prove that for any state $i$ of a Markov chain, the probability $Q_{ii}$ of returning to it infinitely many times equals 0 or 1, and in the first case the state is transient, while in the second it is recurrent.

?

Problem 9.57

Let a Markov chain have $m < \infty$ states, and let the $k$ -th state be recurrent. Prove that there exists a positive number $q < 1$ such that for $n \geqslant m$ the probability that the return time to the $k$ -th state exceeds $n$ is less than $q^{n}$ .

?

Problem 9.58

Prove that for an irreducible chain with a countable number of states to be transient, it is necessary and sufficient that the system of equations

u_{i} = \sum _{j = 0}^{\infty } u_{j} P_{i j}, \quad i = 1,2, \ldots

have a bounded solution such that $u_{i} \not\equiv$ const, $i = 0,1, \ldots$

?

Problem 9.59

Prove that for an irreducible chain with a countable number of states to be recurrent, it suffices that there exist a sequence $u_{0}, u_{1}, \ldots$ such that $u_{i} \rightarrow \infty$ as $i \rightarrow \infty$ and for all $i \neq 0$

u_{i} \geqslant \sum _{j = 0}^{\infty } u_{j} P_{i j}

?

Problem 9.60

Prove that for an irreducible chain with a countable number of states to be positive recurrent, it is necessary and sufficient that the system of equations

u_{j} = \sum _{i = 0}^{\infty } u_{i} P_{i j}, \quad j = 0,1, \ldots

have a solution, not identically zero, for which

\sum _{i = 0}^{\infty }\left|u_{i}\right| < \infty .

?

Problem 9.61

(a)(b)(c)(d)

There is a Markov chain with a countable number of states and transition probabilities $P_{00} = r_{0}, P_{01} = p_{0} > 0$ ,

P_{i j} = \begin{cases} p_{i} > 0, & j = i+1 \\ r_{i} \geqslant 0, & j = i \\ q_{i} > 0, & j = i-1 \\ 0, & \text{ otherwise. } \end{cases}

Let

\rho _{0} = 1, \quad \rho _{m} = \frac{q_{1} \cdots q_{m}}{p_{1} \cdots p_{m}}

Prove the validity of the following statements:

?

(a)

the chain is recurrent if and only if

\sum _{m = 0}^{\infty } \rho _{m} = \infty ;

(b)

the chain is transient if and only if

\sum _{m = 0}^{\infty } \rho _{m} < \infty ;

(c)

the chain is positive recurrent if and only if

\sum _{m = 0}^{\infty } \rho _{m} = \infty , \quad \sum _{m = 0}^{\infty }\left[p_{m} \rho _{m}\right]^{-1} < \infty ;

(d)

the chain is null recurrent if and only if

\sum _{m = 0}^{\infty } \rho _{m} = \infty , \quad \sum _{m = 0}^{\infty }\left[p_{m} \rho _{m}\right]^{-1} = \infty .

Problem 9.62

Let $\xi_{0}, \xi_{1}, \ldots$ be a Markov chain,

\xi _{k+1} = \max \left\{ 0, \xi _{k}-1\right\} +\eta _{k+1}, \quad k \geqslant 0,

where $\eta_{1}, \eta_{2}, \ldots$ is a sequence of independent identically distributed random variables with $\mathbb {P}\left(\eta_{k} = j\right) = p_{j}, j = 0,1, \ldots$ Find the matrix of one-step transition probabilities and prove that if $p_{0} > 0, p_{0}+p_{1} < 1$ , then the chain is recurrent if and only if

\sum _{k} k p_{k} \leqslant 1

?

Problem 9.63

Prove that if a Markov chain has at least one inessential state, then it is not ergodic.

?

Problem 9.64

Show that a nonergodic Markov chain can have a stationary distribution, and moreover a unique one.

?

Problem 9.65

Prove that a finite Markov chain always has a stationary distribution.

?

Problem 9.66

(a)(b)

The matrix of one-step transition probabilities of a Markov chain has the form:

?

(a)

$\left(\begin{array}{cccc}1 / 3 & 1 / 3 & 1 / 3 & 0 \\ 1 / 2 & 1 / 2 & 0 & 0 \\ 1 / 4 & 1 / 4 & 0 & 1 / 2 \\ 0 & 1 / 2 & 0 & 1 / 2\end{array}\right)$ ;

(b)

$\left(\begin{array}{ccccc}0 & 1 / 2 & 0 & 0 & 1 / 2 \\ 0 & 0 & 1 & 0 & 0 \\ 1 / 5 & 1 / 5 & 1 / 5 & 1 / 5 & 1 / 5 \\ 0 & 1 / 2 & 0 & 0 & 1 / 2 \\ 0 & 1 / 2 & 1 / 2 & 0 & 0\end{array}\right)$ .

Find the stationary distribution.

Problem 9.67

Are the Markov chains with the following matrices of one-step transition probabilities ergodic:

?

(a)

$\left(\begin{array}{ll}0 & 1 \\ 1 & 0\end{array}\right)$ ,

(b)

$\left(\begin{array}{ll}1 & 0 \\ 0 & 1\end{array}\right)$ ,

(c)

$\left(\begin{array}{ll}1 & 0 \\ 1 & 0\end{array}\right)$ ,

(d)

$\left(\begin{array}{cc}1 / 2 & 1 / 2 \\ 1 & 0\end{array}\right)$ ,

(e)

$\left(\begin{array}{cc}1 / 2 & 1 / 2 \\ 0 & 1\end{array}\right)$ ,

(f)

$\left(\begin{array}{ccc}1 / 2 & 1 / 2 & 0 \\ 0 & 1 / 2 & 1 / 2 \\ 1 / 2 & 0 & 1 / 2\end{array}\right)$ ,

(g)

$\left(\begin{array}{cccc}1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 / 2 & 1 / 2 & 0 & 0 \\ 1 / 4 & 1 / 4 & 1 / 4 & 1 / 4\end{array}\right)$ .

Problem 9.68

Let a Markov chain have at least two non-communicating states. Prove that it is not ergodic.

?

Problem 9.69

(a)(b)(c)

Let a Markov chain have two states. Prove that one of the following three cases holds:

?

(a)

the chain is ergodic;

(b)

the states do not communicate;

(c)

the matrix of one-step transition probabilities has the form $\left(\begin{array}{ll}0 & 1 \\ 1 & 0\end{array}\right)$ .

Problem 9.70

An ergodic Markov chain with two states has limiting probabilities $p$ and $q = 1-p$ . Find the matrix of one-step transition probabilities.

?

Problem 9.71

Prove that if all essential states of a homogeneous Markov chain with a finite number of states form a single aperiodic class, then there exist limits, independent of $i$ ,

\lim _{n \rightarrow \infty } P_{i j}^{(n)} = \pi _{j}

?

Problem 9.72

A Markov chain has the following matrix of one-step transition probabilities:

\mathbf{P} =\left[\begin{smallmatrix} p_{0} & p_{1} & p_{2} & \ldots & p_{m-1} \\ p_{m-1} & p_{0} & p_{1} & \ldots & p_{m-2} \\ \hdashline \cdot & 0 & . & . & . \\ p_{1} & p_{2} & p_{3} & \ldots & p_{0} \end{smallmatrix}\right],

where $0 < p_{i} < 1, \sum_{i = 0}^{m-1} p_{i} = 1$ . Prove that

\lim _{n \rightarrow \infty } \mathbb {P}\left(\xi _{n} = x_{i}\right) = 1 / m, \quad i = 1,2, \ldots , m

?

Problem 9.73

Let $\xi_{0}, \xi_{1}, \ldots$ and $\eta_{0}, \eta_{1}, \ldots$ be two Markov chains with a finite number of states, the same matrix of one-step transition probabilities, and initial distributions ( $p_{1}, \ldots , p_{m}$ ) and ( $q_{1}, \ldots , q_{m}$ ) respectively. Prove that if

\min _{i, j} P_{i j} \geqslant \varepsilon > 0

then

\sum _{i = 1}^{m}\left|p_{i}^{(n)}-q_{i}^{(n)}\right| \leqslant 2(1-m \varepsilon )^{n}

where $p_{i}^{(n)} = \mathbb {P}\left(\xi_{n} = i\right), \quad q_{i}^{(n)} = \mathbb {P}\left(\eta_{n} = i\right)$ .

?

Problem 9.74

Let a finite Markov chain be ergodic and $\pi_{j} = \lim_{n \rightarrow \infty } P_{i j}^{(n)}$ . Prove that there exist $0 < \rho < 1$ and $C$ such that

\left|P_{i j}^{(n)}-\pi _{j}\right| < C \rho ^{n}

for any $i, j$ , and $n$ .

?

Problem 9.75

Prove that if the matrix of transition probabilities of a Markov chain has two eigenvalues equal in modulus to unity, then the chain is not ergodic.

?

Problem 9.76

Consider the Markov chain from problem 9.62. Prove that for $p_{0} > 0, p_{0}+p_{1} < 1, \sum k p_{k} < 1$ it is ergodic. Find the generating function of the stationary distribution.

?

Problem 9.77

Find the stationary distribution of the Markov chain from problem 9.54 in the case where the series $\sum_{i = 1}^{\infty } p_{i}$ converges.

?

Problem 9.78

Consider a Markov chain with a countable number of states and matrix of one-step transition probabilities

\left[\begin{smallmatrix} p_{0} & p_{1} & p_{2} & \ldots \\ 1 & 0 & 0 & \ldots \\ 0 & 1 & 0 & \ldots \\ 0 & 0 & 1 & \ldots \\ . & . & . & \ldots \end{smallmatrix}\right] .

Prove that for $p_{i} > 0, i = 0,1, \ldots , \sum i p_{i} < \infty$ the chain is ergodic. Find the generating function of the stationary distribution.

?

Problem 9.79

Consider a Markov chain with a countable number of states $\left\{ \ldots -k,-k+1, \ldots ,-1,0,1, \ldots , k, \ldots \right\}$ and one-step transition probabilities

P_{i j} = \begin{cases} p, & j = i+1, \\ 1-p, & j = i-1, \\ 0, & \text{ for other } j . \end{cases}

Find the generating function of the return time to state 0.

?

Problem 9.80

Let a Markov chain be given with states ( $0, \ldots , N$ ) and matrix of one-step transition probabilities

\begin{aligned} P_{i j} & = \begin{cases} p, & j = i+1 \\ 1-p, & j = i-1, \quad i = 1, \ldots , N-1, \end{cases} \\ P_{00} & = P_{N N} = 1. \end{aligned}

Find the expected time to absorption, given that the initial state is $k$ .

?

Problem 9.81

Let a Markov chain with states $0,1, \ldots , N$ have matrix of one-step transition probabilities

P_{i j} = \begin{cases} b_{i}, & j = i-1, \\ a_{i}, & j = i+1, \\ 1-\left(a_{i}+b_{i}\right), & j = i, \\ 0, & \left|j-i\right| > 1, \end{cases}

where $\quad a_{0} = b_{0} = a_{N} = b_{N} = 0, a_{i} > 0, b_{i} > 0, i = 1, \ldots , N-1$ . Find the probability of absorption at state 0, starting from state $k$ .

?

Problem 9.82

Let $\xi_{1}, \xi_{2}, \ldots$ be independent, identically distributed random variables, $\mathbb {P}\left(\xi_{1} = 1\right) = \mathbb {P}\left(\xi_{1} = -1\right) = 1 / 2, z_{0} = 0, z_{k} = z_{k-1}+\xi_{k}$ , $k = 1,2, \ldots$ Set $\tau_{N} = \min \left\{ n \geqslant 1:\left|z_{n}\right| = N\right\}$ . Find $\mathbb {E}\left[\tau_{N}\right]$ .

?

Problem 9.83

The matrix of one-step transition probabilities of a Markov chain with state space ( $0,1, \ldots , N$ ) has the form

\left[\begin{smallmatrix} 0 & 1 & 0 & 0 & \ldots & 0 & 0 & 0 \\ 1 / 2 & 0 & 1 / 2 & 0 & \ldots & 0 & 0 & 0 \\ 0 & 1 / 2 & 0 & 1 / 2 & \ldots & 0 & 0 & 0 \\ . & . & . & . & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & 0 & 0 & \ldots & 1 / 2 & 0 & 1 / 2 \\ 0 & 0 & 0 & 0 & \ldots & 0 & 1 & 0 \end{smallmatrix}\right] .

Find the matrix of $n$ -step transition probabilities.

?

Problem 9.84

Let $\xi_{0}, \xi_{1}, \ldots$ be an irreducible, positive recurrent Markov chain, $\mathbb {P}\left(\xi_{0} = i\right) = 1$ , and let $N_{n}(i)$ be the number of returns to state $i$ in the first $n$ steps. Prove that $\lim_{n \rightarrow \infty } \frac{\mathbb {E}\left[N_{n}(i)\right]}{n} = \frac{1}{\mu_{i}}$ , where $\mu_{i}$ is the mean return time to state $i$ .

?

Problem 9.85

Let, for an irreducible Markov chain with states $\left\{ 0,1,2, \ldots \right\}$ , there exist $\alpha > 0$ such that $f_{i 0} \geqslant \alpha$ for all $i \neq 0$ . Prove that all states of the chain are recurrent.

?