Math Problems Vault

Problem 8.4.1

Find the stationary distribution for

P = \begin{pmatrix} 1/4 & 0 & 0 & 3/4 \\ 3/8 & 1/4 & 3/8 & 0 \\ 1/3 & 1/6 & 1/6 & 1/3 \\ 0 & 0 & 1/2 & 1/2 \end{pmatrix}.

Does this stationary distribution represent a limiting distribution in the regular sense or only in the Cesaro sense?

?

Problem 8.4.2

A doubly-stochastic matrix is a nonnegative matrix $P_{n\times n}$ having all row sums as well as all column sums equal to $1$ . For an irreducible $n$ -state Markov chain whose transition matrix is doubly stochastic, what is the long-run proportion of time spent in each state? What form do $\lim_{k\to \infty } (I + P + \cdots + P^{k-1})/k$ and $\lim_{k\to \infty } P^k$ (if it exists) have?

?

Remark.

?

The purpose of this exercise is to show that doubly-stochastic matrices are not very interesting from a Markov-chain point of view. However, there is an interesting theoretical result (due to G. Birkhoff in 1946) that says the set of $n \times n$ doubly-stochastic matrices forms a convex polyhedron in $\mathbb {R}^{n \times n}$ with the permutation matrices as the vertices.

Problem 8.4.3

Explain why $\operatorname {rk}\left(I-P\right) = n-1$ for every irreducible stochastic matrix $P_{n\times n}$ . Give an example to show that this need not be the case for reducible stochastic matrices.

?

Problem 8.4.4

Prove that the left-hand Perron vector for an irreducible stochastic matrix $P_{n\times n}$ ( $n > 1$ ) is given by

\pi ^T = \frac{1}{\sum _{i=1}^{n} P_i}\left(P_1, P_2, \ldots , P_n\right),

where $P_i$ is the $i$ th principal minor determinant of order $n-1$ in $I-P$ .

?

Remark.

?

What is $[\operatorname {adj}(A)]A$ if $A$ is singular?

Problem 8.4.5

Let $P_{n\times n}$ be an irreducible stochastic matrix, and let $Q_{k\times k}$ be a principal submatrix of $I - P$ , where $1 \leq k < n$ . Prove that $\rho (Q) < 1$ .

?

Problem 8.4.6

Let $P_{n\times n}$ be an irreducible stochastic matrix, and let $Q_{k\times k}$ be a principal submatrix of $I - P$ , where $1 \leq k < n$ . Explain why $Q$ is an M-matrix.

?

Remark.

?

An M-matrix is a real nonsingular matrix $Q_{k\times k}$ such that $[Q]_{ij} \leq 0$ for all $i \neq j$ and $Q^{-1} \geq 0$ ; equivalently, $Q$ is an M-matrix if and only if there exists a matrix $B \geq 0$ and a real number $s > \rho (B)$ such that $Q = sI - B$ .

Problem 8.4.7

Let $P_{n\times n}$ ( $n > 1$ ) be an irreducible stochastic matrix. Explain why all principal minors of order $1 \leq k < n$ in $I - P$ are positive.

?

Problem 8.4.8

Use the same assumptions that are used for the fail-safe system described in the worked example on two independent controls (Example 8.4.5), but use three controls, $A$ , $B$ , and $C$ , instead of two. Determine the mean time to failure starting with three proven controls, two proven but one untested control, and three untested controls.

?

Remark.

?

The referenced example: a system has two independent controls that can prevent it from being destroyed, activated at discrete time points; the system is "under control" if at least one control holds, and destroyed if all controls fail simultaneously. A control that holds at one activation is $90\%$ reliable at the next; a control that fails and is replaced is only $60\%$ reliable at the next activation.

Problem 8.4.9

(a)(b)

A mouse is placed in one chamber of the box shown in the figure below, and a cat is placed in another chamber. Each minute the doors to the chambers are opened just long enough to allow movement from one chamber to an adjacent chamber. Half of the time when the doors are opened, the cat doesn't leave the chamber it occupies. The same is true for the mouse. When either the cat or mouse moves, a door is chosen at random to pass through.

Figure 8.4.1: the mouse-in-a-box floor plan (chamber # 1 is connected to both # 2 and # 3, and # 2 is connected to # 3).

?

(a)

Explain why the cat and mouse must eventually end up in the same chamber, and determine the expected number of steps for this to occur.

(b)

Determine the probability that the cat will catch the mouse in chamber $j$ for each $j = 1, 2, 3$ .