Forgetting properties of finite-state reciprocal processes

Abstract

Reciprocal chains (RC) are a class of discrete-index, finite-state stochastic process having the non-causal generalisation of the Markov property, where rather than the future being conditionally independent of the past given the present, intervals are conditionally independent of their complement given their endpoints. RCs are more powerful models than Markov chains (MC) but are n times more complex to process with their associated smoothing algorithm for number of states n, that is O(n³T) for fixed interval smoothing an interval of length T. In this thesis it was established that RCs have a forgetting property - geometric decay in dependence between separated variables: it was found that the dependence matrix between two variables in an RC has a form expressible in terms of element-wise product of matrix products. The theory of forgetting in matrix products using Birkhoff's contraction coefficient, was extended to this case. It was shown that because MCs are a special case of RCs, arising under particular boundary conditions, forgetting property means the distributions of the RC that are far from the boundary condition are well approximated by those of MC models. It was shown that the forgetting property extends to the RC fixed interval smoothing algorithm so that close approximation occurs by estimates from the MC interval smoother for variables far from the boundary. These results would imply that RCs were not computationally efficient models for intervals that are long with respect to the forgetting rate, however an approximate interval smoothing algorithm was developed for RCs which is a modified form of the MC algorithm (the forward-backward algorithm) and is of comparable complexity to it. The forgetting theory was used to bound the error in the approximation, which is small on the long intervals for which the RC was inefficient for exact estimation.