We define bi-infinite versions of four well-studied discrete integrable models, namely the ultra-discrete KdV equation, the discrete KdV equation, the ultra-discrete Toda equation, and the discrete Toda equation. For each equation, we show that there exists a unique solution to the initial value problem when the given data lies within a certain class, which includes the support of many shift ergodic measures. Our unified approach, which is also applicable to other integrable systems defined locally via lattice maps, involves the introduction of a path encoding (that is, a certain antiderivative) of the model configuration, for which we are able to describe the dynamics more generally than in previous work on finite size systems, periodic systems and semi-infinite systems. In particular, in each case we show that the behaviour of the system is characterized by a generalization of the classical 'Pitman's transformation' of reflection in the past maximum, which is well-known to probabilists. The picture presented here also provides a means to identify a natural 'carrier process' for configurations within the given class, and is convenient for checking that the systems we discuss are all-time reversible. Finally, we investigate links between the different systems, such as showing that bi-infinite all-time solutions for the ultra-discrete KdV (resp. Toda) equation may appear as ultra-discretizations of corresponding solutions for the discrete KdV (resp. Toda) equation.