4
$\begingroup$

Suppose $A$ is a right stochastic matrix, which is defined as a square matrix each of whose rows consists of nonnegative real numbers, with each row summing to 1.

  1. If $\lim_{n \rightarrow \infty} A^n$ exists, is the limit also a right stochastic matrix?
  2. If not, then if $\lim_{n \rightarrow \infty} A^n$ exists and the rows in the limit are identical, is the limit still a right stochastic matrix?

    I am considering the first part of this theorem from Ross as a counterexample where every element in the limit is 0, and thus the sum in each row is not 1. But I guess in that case the dimension of the matrix $A$ must be countably infinite (although not written out explicitly there and my guess can be wrong) and wonder if a stochastic matrix can be defined for infinite dimension?

  3. if not to the first question in Part 2, is it wrong to say that the limit distribution of a discrete-time Markov chain with $A$ as its transition matrix is defined as the identical rows of $\lim_{n \rightarrow \infty} A^n$ if the limit exists and its rows are identical? If yes, what is the proper definition for the limit distribution considering the counterexample in Part 2?

Thanks and regards!

2 Answers 2

12

$\lim_{n \to \infty} A^n$ clearly has non-negative real entries if it exists, so the question is about the stochastic condition. This is equivalent to the condition that $A 1 = 1$ where $1$ is the all-ones vector, and this implies $A^n 1 = 1$, so all the $A^n$ are right stochastic; finally, this condition is (linear, hence) continuous, so is preserved by limits.

The above is for the finite-dimensional case. Here is an example which shows what can go wrong in the infinite-dimensional case. Let $e_1, e_2, ... $ be the "standard basis" and consider the "stochastic" operator $A$ sending $e_i$ to $\frac{1}{2} e_{\lfloor i/2 \rfloor}$. The matrix of $A$ has all rows summing to $1$, but

$\lim_{n \to \infty} A^n e_i = 0$

for all $i$, so the pointwise limit of the sequence $A^n$ is the zero operator. This shows that in the infinite-dimensional case the stochastic condition $A 1 = 1$ is not preserved by pointwise limits: one needs something stronger, such as a limit with respect to a norm.

The basic problem is that the pointwise limit of a sequence of numbers summing to $1$ need not be a sequence of numbers summing to $1$. The simplest example is probably the sequence of sequences

$1, 0, 0, 0, 0, ...$ $\frac{1}{2}, \frac{1}{2}, 0, 0, 0 ...$ $\frac{1}{3}, \frac{1}{3}, \frac{1}{3}, 0, 0...$ $\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, 0, ...$

whose pointwise limit is everywhere $0$; this is essentially the same phenomenon as above. To fix this problem you need to introduce a stronger notion than pointwise limit: for example, since the sum is essentially an $L^1$-norm, convergence in the $L^1$-norm (which is not satisfied in the above example) is enough.

Note that the above sequence of sequences, as integrable functions on $\mathbb{N}$ with the counting measure, does not satisfy the hypotheses of the dominated convergence theorem. Dominated convergence describes a very general situation in which one can guarantee that pointwise limits preserve sums and integrals: the idea is that without the dominating function, "mass can escape to infinity," which is one way to conceptualize what's going on in the above example.

Edit: Actually, I guess the very simplest example of mass escaping to infinity is the sequence of sequences

$1, 0, 0, 0, ...$ $0, 1, 0, 0, ...$ $0, 0, 1, 0, ...$ $0, 0, 0, 1, ...$

  • 0
    @Tim: This is exactly one of my points in my previous comments: when the elements of the limit of $A^n$ are zero, to talk of a limiting distribution is odd.2011-05-01
1

Yes. Note that $A^n$ is stochastic for each $n$. (Show that the product of two stochastic matrices is stochastic, then use induction.) Now pass to the limit (addition is continuous).

  • 0
    Passing to the limit works only if the state space is finite.2011-05-02