Characterisation of ergodic upper transition operators

We study ergodicity for upper transition operators: bounded, sub-additive and non-negatively homogeneous transformations of finite-dimensional linear spaces. Ergodicity provides a necessary and sufficient condition for Perron–Frobenius-like convergence behaviour for upper transition operators. It can also be characterised alternatively: (i) using a coefficient of ergodicity, and (ii) using accessibility relations. The latter characterisation states that ergodicity is equivalent with there being a single maximal communication (or top) class that is moreover regular and absorbing. We present an algorithm for checking these conditions that is linear in the dimension of the state space for the number of evaluations of the upper transition operator.