On estimating the memory for finitarily Markovian processes

Abstract: Finitarily Markovian processes are those processes

{X_{n}}_{n = - i n f t y}^{i n f t y}

for which there is a finite

K

(

K = K ({X_{n}}_{n = - i n f t y}^{0}

) such that the conditional distribution of

X_{1}

given the entire past is equal to the conditional distribution of

X_{1}

given only

{X_{n}}_{n = 1 - K}^{0}

. The least such value of

K

is called the memory length. We give a rather complete analysis of the problems of universally estimating the least such value of

K

, both in the backward sense that we have just described and in the forward sense, where one observes successive values of

X_{n}

for

n g e q 0

and asks for the least value

K

such that the conditional distribution of

X_{n + 1}

given

{X_{i}}_{i = n - K + 1}^{n}

is the same as the conditional distribution of

X_{n + 1}

given

{X_{i}}_{i = - i n f t y}^{n}

. We allow for finite or countably infinite alphabet size.

Recommendations

Cited In (19)

This page was built for publication: On estimating the memory for finitarily Markovian processes