Invariant Half-Lines of Nonexpansive Piecewise-Linear Transformations

It is shown that if f is a nonexpansive piecewise-linear mapping of R^m into itself, there exists a unique half-line that f maps into itself and such that restriction of f thereto is a translation. One easy consequence of this result is that there exists a unique m-vector α such that for every m-vector x, the sequence fⁿ(x) − nα remains bounded. In particular, fⁿ(x)/n converges to the same limit α, for all x. Also, f has a fixed point if and only if α = 0. These results are applied to give alternative proofs of several known facts concerning the maximum expected n-period reward in a finite Markov decision process.