Predictive complexity and generalized entropy rate of stationary ergodic processes
From MaRDI portal
Stationary stochastic processes (60G10) Statistical aspects of information-theoretic topics (62B10) Inference from stochastic processes and prediction (62M20) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational learning theory (68Q32) Other game-theoretic models (91A40) Applications of game theory (91A80) Measures of information, entropy (94A17)
Abstract: In the online prediction framework, we use generalized entropy of to study the loss rate of predictors when outcomes are drawn according to stationary ergodic distributions over the binary alphabet. We show that the notion of generalized entropy of a regular game cite{KVV04} is well-defined for stationary ergodic distributions. In proving this, we obtain new game-theoretic proofs of some classical information theoretic inequalities. Using Birkhoff's ergodic theorem and convergence properties of conditional distributions, we prove that a classical Shannon-McMillan-Breiman theorem holds for a restricted class of regular games, when no computational constraints are imposed on the prediction strategies. If a game is mixable, then there is an optimal aggregating strategy which loses at most an additive constant when compared to any other lower semicomputable strategy. The loss incurred by this algorithm on an infinite sequence of outcomes is called its predictive complexity. We use our version of Shannon-McMillan-Breiman theorem to prove that when a restriced regular game has a predictive complexity, the predictive complexity converges to the generalized entropy of the game almost everywhere with respect to the stationary ergodic distribution.
Recommendations
Cited in
(4)
This page was built for publication: Predictive complexity and generalized entropy rate of stationary ergodic processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3164833)
