🚀 go-pugleaf

I wrote:

> Thus, any partition of the states of an ERGODIC markov chain (with a
> finite number of states) induces a well defined quotient erogdic
> Markov chain.

That's completely wrong.  I had failed to check that the quotients I was
defining are in fact Markov chains, and they are not.  Indeed, as Toni
said, factors (quotients) of Markov chains are almost never Markov
chains.  I ought to have known better than to have said what I did,
because I know that factors of sfts (the topological analog of Markov
chains) are usually not sfts but rather sofic shifts.  (See the book by
Lind and Marcus, Introduction to Symbolic Dynamics and Coding, Cambridge
University Press, 1995.)

To recapitulate, I was looking at the example of a Markov chain with
three states A,B,C and (unique) invariant probability measure and
transition frequencies given by

                                         A     B    C
      A      B      C               A [ 1/2   1/2    0  ]
   [ 8/15  6/15  1/15 ]             B [ 1/2   1/3   1/6 ]
                                    C [  1      0    0  ]

This chain permits six two-letter words AA, AB, BA, BB, BC, CA
with frequencies

    p(AA) = P(A)p_A(A) = 4/15, p(AB) = 4/15,
    p(BA) = 3/15, p(BB) = 2/15, P(BC) = 1/15,
    p(CA) = 1/15

Now by lumping or amalgamating or identifying the two states {A,B}
to form a new state U, we obtain a new stochastic process with states U
and C.   This process (as we are about to see, it is NOT a Markov chain)
permits three two-letter words, arising from the original words as
follows:

   AA, AB, BA, BB --->  UU   p(UU) = 13/15
   BC             --->  UC   p(UC) = 1/15
   CA             --->  CU   p(CU) = 1/15

The quotient process would be a Markov chain only if for every triple of
states P, Q, R we had  p_{PQ}(R) = P_Q(R).  These are the conditional
probabilities defined by

    p(PQR) = p(PQ) p_{PQ}(R)
    p(QR) = p(Q) p_Q(R)

In the first of the, for a Markov chain we can write

    p(PQR) = p(PQ) p_Q(R)

However, it is easy to see that this fails for the quotient process in
question!   For instance, the quotient word CUU can arise from
either CAA or CAB, each of which occurs with frequency 1/30, so

   p(CUU) = 1/15

But

   p(CU) p_U(U) = (1/15) (13/14)  =/= 1/15

So, the quotients of Markov chains are not neccesarily Markov chains,
as Toni said.

However, the Markov chains I defined -are- related to the actual
quotients: they are the unique first order chains which capture the
``first-order statistical structure'' of the actual quotients, which are
more complicated processes.   That is, the chain I defined with
the unique invariant probability measure and transition frequencies

        U     C               U      C
    [ 14/15  1/15 ]     U [ 13/14  1/14 ]
                        C [   1      0  ]

is the unique first order Markov chain sharing the correct letter
frequencies (zero-th order structure) p(Q) and digram frequencies
(first-order structure) p(QR) with the actual quotient process.   This
Markov chain was called the "first order approximation" to a process by
Shannon in his 1948 paper founding information theory (see the book by
Shannon & Weaver, Mathematical Theory of Communication, University of
Illinois Press, 1949).   Shannon was considering natural language
production as a stochastic process which can be modeled by a sequence of
k-th order Markov chains; this idea applies to any stochastic process;
in particular, to the quotient process under discussion here.

Now, as Shannon realized, this sequence of k-th order Markov
approximations X_k to X has the property that 

   h(X) = lim_k h(X_k)

where

   h(X_0) >= h(X_1) >= ... h(X)

so with regard to Toni's original question, we can say that the
source entropies of the quotient processes (NOT "quotient chains"!) are
bounded above by the entropies of the first order approximations defined
in the way I explained.

Chris Hillman