Convergence and loss bounds for Bayesian sequence prediction

The probability of observing x_t at time t, given past observations x₁ ⋯ x_t-1 can be computed if the true generating distribution μ of the sequences x₁x₂x₃ ⋯ is known. If μ is unknown, but known to belong to a class M one can base one's prediction on the Bayes mix ξ defined as a weighted sum of distributions ν ε M. Various convergence results of the mixture posterior ξ_t to the true posterior μ_t, are presented. In particular, a new (elementary) derivation of the convergence ξ_t / μ_t → 1 is provided, which additionally gives the rate of convergence. A general sequence predictor is allowed to choose an action y_t based on x₁ ⋯ x_t-1 and receives loss ℓ_xtyt if x_t is the next symbol of the sequence. No assumptions are made on the structure of ℓ (apart from being bounded) and M. The Bayes-optimal prediction scheme Λ_ξ based on mixture ξ and the Bayes-optimal informed prediction scheme Λ_μ are defined and the total loss L_ξ of Λ_ξ is bounded in terms of the total loss L_μ of Λ_μ. It is shown that L_ξ is bounded for bounded L_μ and L_ξ/L_μ → 1 for L_μ → ∞. Convergence of the instantaneous losses is also proven.