Universal prediction over large alphabets

Abstract

We consider the universal prediction problem in the context of an insurance game. Imagine the natural frame work of an insurance company where we assume only two players are in the insurance game: insurer and insured. In each round, the insurer sets a premium scheme to be paid by the insured to pay for the losses incurred to the insured. Losses are assumed to be integer valued i.i.d random variables. The setup and framework of this thesis are from [1]. There is no information about the underlying distribution of the losses but the underlying distribution is assumed to belong to a known class of distributions P. Losses can be unbounded as well and the game proceeds for an in nite number of rounds. The insurer can observe the losses without setting premiums for a nite time, but is required to enter the game with probability 1 no matter what the (unknown) source is. The objective is to set premium scheme such that the probability that the loss exceeds the premium can be made arbitrarily small over the in nite time window. Collections of distributions which allow such premium schemes are called insurable, and were completely characterized in [1]. Using their characterization, we show the insurability of the collection MH of distributions that are monotone and whose entropy is bounded by a given H > 0. For the collection MH, we propose an insurance scheme that grows super exponentially in the number of rounds the game has gone on thus far and show that it is essentially the best we can do.