Finite-Memory Universal Prediction of Individual S

1506IEEETRANSACTIONSONINFORMATIONTHEORY,VOL.50,NO.7,JULY2004Finite-MemoryUniversalPredictionofIndividualSequencesEadoMeronandMeirFeder,Fellow,IEEEAbstract—Theproblemofpredictingthenextoutcomeofanindividualbinarysequenceundertheconstraintthattheuniversalpredictorhasafinitememory,isexplored.Inthisanalysis,thefinite-memoryuniversalpredictorsareeitherdeterministicorrandomtime-invariantfinite-state(FS)machineswithstates(-statemachines).Thepaperprovidesboundsontheasymptoticachievableregretoftheseconstraineduniversalpredictorsasafunctionof,thenumberoftheirstates,forlongenoughsequences.Thespecificresultsareasfollows.Whentheuniversalpredictorsaredeterministicmachines,thecomparisonclassconsistsofconstantpredictors,andpredictioniswithrespecttothe0–1lossfunction(Hammingdistance),wegettightboundsindicatingthattheoptimalasymptoticregretis1(2).Inthatcaseof-statedeterministicuniversalpredictors,theconstantpredictorscomparisonclass,butpredictioniswithrespecttotheself-information(codelength)andthesquare-errorlossfunctions,weshowanupperboundontheregret(codingredundancy)of(23)andalowerboundof(45).Fortheselossfunctions,ifthepredictorisallowedtobearandom-statemachine,i.e.,amachinewithrandomstatetransitions,wegetalowerboundof1ontheregret,withamatchingupperboundof1forthesquare-errorloss,andanupperboundoflog1fortheself-informationloss.Inaddition,weprovideresultsforalltheselossfunctionsinthecasewherethecomparisonclassconsistsofallpredictorsthatareorder-Markovmachines.IndexTerms—Exponentiallydecayingmemory,finite-state(FS)machines,FSprediction,imaginaryslidingwindow,saturatedcounter(SC),universalcoding,universalprediction.I.INTRODUCTIONUNIVERSALpredictionanduniversalcodingisamaturesubjectnowadays(see,e.g.,[14]foranextensivesurvey).Theimportantresultsarewidelyknown,demonstratingtheoftensurprisingphenomenathatitispossibletouniversallyManuscriptreceivedMarch31,2003;revisedMarch31,2004.TheworkofE.MeronissupportedinpartbyIntelIsrael,andbythe“YitzhakandChayaWeinsteinInstituteforResearchinSignalProcessing.”ThematerialinthispaperwaspresentedinpartattheIEEEInternationalSymposiumonInforma-tionTheory,Yokohama,Japan,June/July2003andattheDataCompressionConference,Snowbird,UT,March2004.TheauthorsarewiththeDepartmentofElectricalEngineering–Systems,Tel-AvivUniversity,Ramat-Aviv69978,Israel(e-mail:[e-mail];[e-mail]).CommunicatedbyE.-h.Yang,W.Szpankowski,andJ.C.Kieffer,GuestEd-itors.DigitalObjectIdentifier10.1109/TIT.2004.8307491Throughoutthepaperf(K)=O(g(K)))limsupf(K)g(K)constf(K)=(g(K)))limf(K)g(K)=const;logx=logx:predict(orcompress)datageneratedbyanunknownsource,orevenanindividualdeterministicdatasequenceandattainoptimalasymptoticperformance.Theuniversalpredictionproblemcanbeconsideredinbothaprobabilisticandade-terministicsetting.Intheprobabilisticsettingoftheproblem,itisassumedthatthedataisgeneratedbysome(unknown)probabilisticsource.Ifthesourcewereknown,onecoulddesignanoptimal(nonuniversal)predictorthatwouldmini-mizetheexpectedpredictionlossforthatsource.Interestingly,universalpredictiontheoryhasshownthatonecanconstructasingleuniversalpredictorthatcanworkwellforallsources,i.e.,attainasymptoticallythesameexpectedaveragelossastheoptimalpredictortunedtothesource.Theexistenceofauniversalpredictorrequiresthattheunknownsourcebelongstoaconstrainedenoughclassofsources.Also,therateofconvergencedependsonrichnessofthatclass.Yet,atleastforweakconvergence,thisclasscanbeallfinite-alphabetstationaryandergodicsources,see[10],[18].Inthedeterministicsettingoftheuniversalpredictionproblemthedataisanarbitraryindividualsequence.Ifthedatasequenceisknownupfront,onecanchoosethebestpredictorfromsomeconstrainedclassofpredictorsthatmin-imizesthepredictionlossforthatsequence.Thispredictorisnonuniversal,asitisdesignedbasedonthegivensequence.Interestingly,aswasshownbyuniversalpredictiontheory,thereexistsasingleuniversalpredictorwhoseperformanceforanysequenceisasymptoticallythesameastheperformanceofthe(nonuniversal)predictortunedtothatsequence.Theexistenceofsuchuniversalpredictorrequiresthattheclassofpredictorsfromwhichthisnonuniversalpredictorischosenisconstrainedenough.Asabove,theconvergenceratedependsontherichnessofthatclass.Yetthisclasscanbelarge,e.g.,allfinite-statemachines,see[6].Inafurtherexaminationoftheuniversalpredictorsthatattaintheoptimalperformance,itturnsoutthatthesepredictors,whileuniversalandnonanticipating,aremuchmorecomplexthanthepredictorsortheclassofsourceswhoseperformancetheyattain.Forexample,optimaluniversalpredictionanduniversalcodingofbinarysequencesformemorylesssources,orpredictorsthatcompetewiththeclassofconstantpredictors(thereisadualitybetweenthesetwoproblems,see[14])mustmaintaintheempir-icalcountofzerosandonesobservedsofarinthesequence.Thisrequiresthattheuniversalpredictorwillhaveagrowingnumberofstates(roughly,whereisthedatasize)andallthiscom-plexityisrequiredtocompetewithaconstantsingle-statepre-dictor!Followingthisobservation,anaturalquestionarises.Whatisthebestthatcanbedoneiftheuniversalpredictorhaslimitedresources?Forthi