The Setting
Consider a random walk on finitely many nodes, numbered by natural numbers, that only moves forward: from a node it steps to a node with probability or stops, so each row of sums to at most , as for a walk on the configuration graph of a clocked machine. The entries of are at most a scale . A correction matrix is built from by iterating a fixed correction map, starting from the zero matrix. The question is how far one round of this iteration moves an entry, and after how many rounds, independent of , that movement falls to a small fixed fraction of .
Forward Matrices and the Corrected Iteration
A domain is a finite set of nodes.✦ A matrix assigns a real number to each pair of nodes✦, a vector assigns a real number to each node✦, and matrices are compared entry by entry. For a domain , the row weight of at a node over is ✦, and the product over of two matrices and is the matrix with entries (1)✦
Given domains and and reals and , a matrix is a bounded support matrix on with active set , scale and bound when, for all nodes and , (2)✦ Write for the set of these matrices. A step matrix on at scale is a matrix in .✦
Fix a domain , a scale , a vector and a matrix , and let be the correction at scale with weights , a map on matrices that acts entry by entry. The iterated correction of is the sequence of matrices given by and (3)✦ with the product taken over . The successive differences of the iterated correction are the matrices .✦
The cutoff scale is the constant .✦
The Claim
Theorem 1. Let and be domains, a scale, a vector with values in and a matrix, and let be the iterated correction of , with products over , and its successive differences.
If is a bounded support matrix on with active set , scale and bound , then (4)✦ and (5)✦ If is a step matrix on at scale , then for every (6)✦ and for every and all nodes and (7)✦ There is a positive integer , an admissible iteration count, with (8)✦
In the paper, the result reads: for every fixed column multiplier there is a unique strictly forward nonnegative solution of , the iterates satisfy and , and so a fixed makes the right side at most , uniformly in , , and , with , standing for , and , , and the paper’s own quantities. The statement above bounds the step from round to round of the increasing iterates, where the paper bounds their distance to the fixed point.
What Is Checked
The claim is stated over domains and , a scale , a vector with values in , a bounded support matrix on with active set , scale and bound (a step matrix on in (6) and (7)), the iterated correction of with its products over , its successive differences , and the cutoff scale in the admissible iteration count.