Let me respond to Dan's thoughtful response with a clarified restatement of the problem: We say a stochastic matrix A is irreducible and aperiodic if some power of A has all its entries positive. For each positive integer n > 0, what is the maximum value of N for which there exists an n-by-n aperiodic stochastic matrix A and a probability vector v such that A^N v has all its entries positive but v , A v , A^2 v , ... , A^(N-1) v do not not? This can be recast as a purely combinatorial question. Suppose a finite directed graph with n vertices has the property that for every ordered pair of vertices (v,w), there is a way to get from v to w in exactly N moves. Define the "inconvenience" of such a digraph as the smallest N that works for all v,w. How large can the inconvenience of an n-vertex directed graph be? Example: Consider the direct graph on 4 vertices {A,B,C,D} with edges A->B, B->C, C->D, D->A, and D->B. Then, starting from A, the vertices that are reachable in a specified number of moves are as follows: In 1 move: B In 2 moves: C In 3 moves: D In 4 moves: A,B In 5 moves: B,C In 6 moves: C,D In 7 moves: A,B,D In 8 moves: A,B,C In 9 moves: B,C,D In 10 moves: A,B,C,D So we have shown that the inconvenience of this digraph is at least 10. Correspondingly, consider the matrix and vector ( 0 1 0 0 ) ( 1 ) ( ) ( ) ( 0 0 1 0 ) ( 0 ) A = ( ) , v = ( ) ; ( 0 0 0 1 ) ( 0 ) ( ) ( ) (1/2 1/2 0 0 ) ( 0 ) A^10 v has all its entries positive, but A^9 v does not. Here is a proof that the inconvenience can be at most 2^n-2: Each probability vector can be represented by an n-tuple of 0's and +'s, where 0 stands for 0 and + stands for any positive number. Call this the signature of the vector. It is easy to see that the signature of a vector v determines the signature of its image A v. If the 2^n - 1 vectors v , A v , A^2 v , ... , A^(2^n-2) v all have signatures different from (0,0,...,0) and (+,+,...,+), then by the pigeonhole principle two of the vectors must have the same signature. But then the sequence of signatures must cycle forever and never hit (+,+,...,+), which contradicts our assumptions. So either (0,0,...,0) must occur (which is impossible since all our vectors are probability vectors) or (+,+,...,+) must occur (in which case that signature recurs forever after). Hence, for every v, A^(2^n-2) v has all its entries positive. Clearly one can do better than the upper bound N(n) leq 2^n - 2. My question is, how much better can one do? My example for n=4 shows that N(4) geq 10. Suitably generalized, this example gives a quadratic lower bound on N(n). I suspect that the true behavior of the inconvenience function is quadratic. But is O(n^2) the "inconvenient truth"? :-) I'd be grateful for a proof, disproof, or reference. In any case, thanks Dan! Jim Propp