THE ENTROPY OF MARKOV TRAJECTORIES

The idea of thermodynamic depth put forth by Lloyd and Pagels requires the computation of the entropy of Markov trajectories. Toward this en d we consider an irreducible finite state Markov chain with transition matrix P and associated entropy rate H(X) = -SIGMA(i,j) mu(i)P(ij) lo g P(ij), where mu is the stationary distribution given by the solution of mu = muP. A trajectory T(ij) of the Markov chain is a path with in itial state i, final state j, and no intervening states equal to j. We show that the entropy H(T(ii)) of the random trajectory originating a nd terminating in state i is given by H(T(ii)) = H(X)/mu(i). Thus the entropy of the random trajectory T(ii) is the product of the expected number of steps 1/mu(i) to return to state i and the entropy rate H(X) per step for the stationary Markov chain. A general closed form solut ion for the entropies H(T(ij)) is given by H = K - K + H(DELTA), where H is the matrix of trajectory entropies H(ij) = H(T(ij)); K (I - P A)-1 (H - H(DELTA)); K is a matrix in which the ijth element K(ij) eq uals the diagonal element K(jj) of K; A is the matrix of stationary pr obabilities with entries A(ij) = mu(j); H is the matrix of single-ste p entropies with entries H(ij) = H(P(i)) = -SIGMA(k) P(ik) log P(ik); and H(DELTA) is a diagonal matrix with entries (H(DELTA))ii = H(X)/mu (i).