Skip to main content
eScholarship
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Electronic Theses and Dissertations bannerUC Berkeley

Long range dependent models in information theory

Abstract

Long range dependence refers to stochastic processes for which correlations persist

at much longer time scales as compared to traditional models. For such processes the

central limit theorem does not in general hold, and the smoothing effect of the law of

large numbers takes more time to settle in. Such phenomena have been observed in

many different fields including financial time series, DNA sequences, network traffic

and variable bit-rate video. The bursty nature and persistent correlation structure of

long 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 range

dependence through the use of Markov models.

We first introduce a model of long range dependence using countable state Markov

chains. 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 Markov

chain also inherit this property. We provide conditions under which the function

has the same degree of long range dependence as the chain itself. We illustrate

our results through three examples in diverse fields: queuing networks, source

compression, and finance. We then prove information-theoretic pointwise lossless source

coding theorems for a class of sources constructed from this model. We are able

to show that the code length process at the output of an encoder inherits the long

range 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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View