You are receiving a time series whose elements belong to a finite set. Assume the time series is distributed as a Discrete-Time Markov Chain. You receive one element at each time step.


For each time step, your goal is to produce the best possible approximation of the underlying Markov Chain, ideally through a minimal-computation update algorithm.


Has this problem ever been formulated? Does an algorithm for this problem exist? Any little bit of help is very welcome.


Thanks a lot.


P.S.: The update algorithm could include a prediction phase (as Kalman filtering does).


P.S. 2: Bonus points if the solution includes a way to discard the null hypothesis (i.e. to detect it isn't likely to be a Markov chain, after all).



How to detect, track and map a Markov chain
For a given state $i$, row $i$ of the transition matrix gives the transition probabilities $P\_{ij}$ from $i$ to $j$, $j=1..n$ (the number of states). This
is a probability distribution, and the minimum variance unbiased estimator of it is
the empirical distribution $\hat{P}\_{ij} = N\_{ij}/N\_i$, where $N\_i$ is the number
of times state $i$ was observed before the latest time and $N\_{ij}$ is the number of
times state $i$ was directly followed by $j$.


