Fiber entropy and algorithmic complexity of random orbits

Abstract

Let $\Theta$ be a finite alphabet. We consider a bundle of measure preserving transformations $(T_{\theta }{)}_{\theta \in \Theta }$ acting on a probability space $(X,\mu )$, which are chosen randomly according to an ergodic stochastic process $(\Xi ,\nu ,\sigma )$ with state space $\Theta$. This describes a paradigmatic case of a random dynamical system (RDS). Considering a finite partition $\mathcal{P}$ of $X$ we show that the conditional algorithmic complexity of a random orbit $x,T_{{\alpha }_0}(x),T_{{\alpha }_1}\circ T_{{\alpha }_0}(x),...$ in $X$ along a sequence $\alpha ={\alpha }_0{\alpha }_1{\alpha }_2...$ in $\Xi$ equals almost surely the fiber entropy of the RDS with respect to $\mathcal{P}$, whenever the latter is ergodic. This extends a classical result of A. A. Brudno connecting algorithmic complexity and entropy in deterministic dynamical systems.