Long range dependent models in information theory
Barlas Oğuz · eScholarship (California Digital Library) · 2012
Long range dependence refers to stochastic processes for which correlations persistat much longer time scales as compared to traditional models. For such processes thecentral limit theorem does not in general hold, and the smoothing effect of the law oflarge numbers takes more time to settle in. Such phenomena have been observed inmany different fields including financial time series, DNA sequences, network trafficand variable bit-rate video. The bursty nature and persistent correlation structure oflong range dependent processes make them tough to control and predict in practice,and tough to analyze in theory. In this thesis we look at the origins of long rangedependence through the use of Markov models.We first introduce a model of long range dependence using countable state Markovchains. A positive recurrent, aperiodic Markov chain is said to be long range dependent (LRD) when the indicator function of a particular state is LRD. This happens if and only if the return time distribution for that state has infinite variance.We investigate the question of whether other instantaneous functions of the Markovchain also inherit this property. We provide conditions under which the functionhas the same degree of long range dependence as the chain itself. We illustrateour results through three examples in diverse fields: queuing networks, source compression, and finance. We then prove information-theoretic pointwise lossless sourcecoding theorems for a class of sources constructed from this model. We are ableto show that the code length process at the output of an encoder inherits the longrange dependent nature of the source irrespective of the coding algorithm chosen.We extend our results to lossy source coding under suitable conditions, demonstrating quite generally the information-theoretic relevance of long range dependence.