Thomas Kaijser's contribution to Hidden Markov Models

I plan to give two seminars on the contribution Thomas Kaijser (14th August 1942 - 28th August 2018), one of my colleagues from my time in Sweden, to the subject of Hidden Markov Models.

Consider a hidden process X_n and an observed process Y_n = g(X_n), the hidden process has a finite state space. Let  \alpha_{ni} = P(X_n=i|Y_n,Y_{n-1},\ldots, Y_0)

the so-called alpha-process. In 1957, Blackwell conjectured that if X was ergodic, then the alpha-process had a unique invariant measure, which did not depend on the distribution of X_0.

In 1975, Thomas Kaijser produced a 4-state counter example, where the \alpha-process is a 4-state Markov chain and the 4 states depend on the initial distribution.

He also gave a simple sufficient condition for the uniqueness of the invariant measure of the so-called $\alpha$-chain, which he proved using a clever adaptation of the Furstenberg-Kesten theory of random matrices.

In 2006, Kochman and Reed revisited the problem. They used a different approach, based on Meyn and Tweedie. They developed the one-rank condition, gave a simpler proof and showed that it was more general than the sufficient condition of Thomas Kaijser.

When Thomas Kaijser returned to the subject in 2011, he based his work, generalising to Markov chains on Polish spaces, on the Kochman-Reed rank-one condition. The rank-one condition can, however, be difficult to verify, even in seemingly straightforward examples. He shows this in his note on the rechargeable Polya urn scheme, where the observed process is the colour of the last ball taken from the urn. He shows that there is a unique invariant measure for the $\alpha$-process in this example, but verifying the rank-one condition is not straightforward.

In the first talk, I intend to give the counterexamples of Kaijser. which illustrates that the conjecture by Blackwell is false, and Harry Kesten (unpublished private communication to Kaijser from 1994) where he is able to obtain an a pha process on 8 states, which is a periodic} chain of period 2. Also, I'll outline the Kochman-Reed rank-one condition and the line of proof.

In the second talk, I'll describe the rechargeable Polya urn scheme (where, at each step, there is a probability that we start again with an empty urn) and show that rank-one condition can be verified in this case.

Blackwell, D; [1957]{\em The Entropy of Functions of Finite-state Markov chains} in Transactions of the First Prague Conference on Information Theory, Statistical Decision Functions, and Random Processes 13-20. Publishing House of the Czechoslovak Academy of Sciences Furstenberg, H.; Kesten H. [1960]{\em Products of Random Matrices} Ann. Math. Statist. {\bf 31} 457-469

 Kaijser, T. [1975]{\em A Limit Theorem for Partially Observed Markov Chains} Ann. Probab. {\bf 3} 677 - 696

Kaijser, T. [2011] {\em On Markov Chains Induced by Partitioned Transition Probability Matrices} Acta Math. Sinica {\bf 20} 441-476

Kaijser, T. [2016]{\em On Convergence in Distribution of the Markov Chain generated by the Filter Kernel induced by a Fully Dominated Hidden Markov Model} Dissertationes Mathematicae {\bf 514} 1-67

Kaijser T. [2018]{\em A Note on the Rechargeable Polya Urn Scheme} unpublished

Kochman, F.; Reeds, J. [2006]{\em A Simple Proof of Kaijser's Unique Ergodicity Result for Hidden Markov $\alpha$-Chains}

Meyn, S.P.; Tweedie, R.L. [1993]{\em Markov Chains and Stochastic Stability} Springer, London