On Asymptotically Optimal Methods of Prediction and Adaptive Coding for Markov Sources

✍ Scribed by Boris Ya. Ryabko; Flemming Topsøe

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 143 KB
• Volume: 18
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1006/jcom.2001.0611

✦ Synopsis

The problem of predicting a sequence x 1 , x 2 , ... generated by a discrete source with unknown statistics is considered. Each letter x t+1 is predicted using information on the word x 1 x 2 • • • x t only. In fact, this problem is a classical problem which has received much attention. Its history can be traced back to Laplace. To estimate the efficiency of a method of prediction, three quantities are considered: the precision as given by the Kullback-Leibler divergence, the memory size of the program needed to implement the method on a computer, and the time required, measured by the number of binary operations needed at each time instant. A method is presented for which the memory size and the average time are close to the minimum. The results can readily be translated to results about adaptive coding.