On the Relationship between Complexity and Entropy for Markov Chains and Regular Languages
Wentian Li
Current address: Physics Department, Rockefeller University, 1230 York Avenue, New York, NY 10021.
Santa Fe Institute, 1660 Old Pecos Trail, Suite A,
Santa Fe, NM 87501, USA
Abstract
Using the past-future mutual information as a measure of complexity, the relation between the complexity and the Shannon entropy is determined analytically for sequences generated by Markov chains and regular languages. It is emphasized that, given an entropy value, there are many possible complexity values, and vice versa; that is, the relationship between complexity and entropy is not one-to-one, but rather many-to-one or one-to-many. It is also emphasized that there are structures in the complexity-versus-entropy plots, and these structures depend on the details of a Markov chain or a regular language grammar.
