Cutting and stacking: a method for constructing stationary processes

Abstract

Cutting and stacking, a general method for constructing examples of stationary, ergodic, finite-alphabet processes with desired properties, is described. It has been used to construct counterexamples in ergodic theory. Recently, it has also been used to construct examples of interest in information theory and probability theory. The method builds a stationary ergodic process by describing sample paths as concatenations of nonoverlapping blocks of varying lengths. Induction is used to show how these blocks are concatenated to form longer and longer blocks, and a geometric model is used to guarantee stationarity. The basic ideas of the method and some recent applications to information theory problems are described.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>