3
$\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

11

$\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, ...$$

  • 2
    @Tim: this is a different question. In finite dimensions there are several reasonable ways to define the limit of a sequence of matrices, all of which turn out to be equivalent, but in infinite dimensions they are almost all different, so considerable care has to be taken about which notion you're using. This is the subject of functional analysis: http://en.wikipedia.org/wiki/Functional_analysis2011-05-01
  • 0
    @Qiaochu: Thanks! Considering my third part, how would you define the the limit distribution of a discrete-time Markov chain with A as its transition matrix?2011-05-01
  • 0
    @Tim: I don't know what conventions are used in the Markov chain literature, so I can't say.2011-05-01
  • 0
    The last paragraph in Qiaochu's answer is spot on. As regards Tim's last comment, the *limit distributions* are defined as *the limits in distribution* of $(X_n)$ when $n\to+\infty$ (plural because different initial distributions $\nu$ may yield different limits). In the finite case the distribution of $X_n$ is $\nu A^n$ so... Tim, what is the question really?2011-05-01
  • 0
    @Didier: Thanks! From several books/posts I have read, 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. So limit distribution such defined does not depend on initial distribution and is unique if it exists. According to this definition, the limit distribution can be a zero measure as in the counterexample in my Part 2, and it is thus not a probability measure. So are the definitions I saw wrong?2011-05-01
  • 0
    Can you give specific references?2011-05-01
  • 0
    @Didier: Just a side note, without @ only the author of the reply, here Qiaochu, will be notified. Source 1: http://books.google.com/books?id=YGjTl8iX-HsC&pg=PA126&dq=were+easy+to+obtain+by+means+other+than+evaluating+limits,+they+could+serve+as+approximations+to+the+hard-to-obtain+entries&hl=en&ei=RaK9TYW6DPCD0QHht9zhBQ&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCoQ6AEwAA Source 2: http://math.stackexchange.com/questions/9325/equilibrium-distribution-steady-state-distribution-stationary-distribution-and/32987#32987;2011-05-01
  • 0
    Source 3: Definition 6 in http://docs.google.com/viewer?a=v&q=cache:YgCCXaBX0jQJ:www.ieor.berkeley.edu/~ieor263a/lecture11-14.pdf+solidarity+property+positive+recurrence&hl=en&gl=us&pid=bl&srcid=ADGEESi1EB2efCEp2hsgvD06sJi1VZAC4jfhbdOJJEzFmggBGg083mgqOEiE_YEqhhH6PQF-5urLhlOgtFo33078ke9H4bnT2jHHXTmNs8ftIBJ5LW9ocSBHUCDJvDQ0iTFgVaQ27fGo&sig=AHIEtbTS_g2JMqmcaRp_ITygCVCTbov-dA2011-05-01
  • 0
    Tim: You said yourself what is odd with defining *limit distribution* in a way such that (1) this object may not be a distribution at all and (2) situations where the distribution of $X_n$ converges to a probability distribution $\nu$ may happen without $\nu$ being called a limit distribution... I would go as far as saying that point (1) alone makes this convention/definition unacceptable. (About the @ thing: are you sure? http://meta.stackexchange.com/questions/43019 explains that the first author of the question or answer will always be notified of any new comment.)2011-05-01
  • 0
    @Didier: about @ , I am sure. I have read that link, and I was not notified by your comments to me under this Qiaochu's reply because of lacking "@Tim".2011-05-01
  • 0
    @Didier: Thanks! If interpreting the limiting distribution as limit of the distribution of $X_n$, in what sense does the sequence of distribution measures converge?2011-05-01
  • 1
    @Tim: Weak convergence of measures http://en.wikipedia.org/w/index.php?title=Convergence_of_measures&action=edit§ion=2. Note that the limit *must* be a probability measure.2011-05-01
  • 0
    @Didier: Thanks! "the limit must be a probability measure", even when all the elements in $\lim_{n \rightarrow \infty} A^n$ are zero?2011-05-01
  • 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
    Thanks! I was wondering what is the definition of the the limit distribution of a discrete-time Markov chain with A as its transition matrix?2011-05-01
  • 0
    Passing to the limit works only if the state space is finite.2011-05-02