Trajectories of random walks on Markov sources reveal the structure of complex sequences

We highlight a hierarchical property that is found in many sequences, the property of subunit structure, in which sequence symbols are joined together in tightly knit groups to create new subunits at higher levels of organization. Many sequences have strong connections both between the subunits and within the subunits. We propose an information-theoretic method that reveals hierarchical subunit structure in sequences. We use the probability flow of random walks on the Markov source encompassing transitions from subunit to subunit as a proxy for information flow in the sequence. We decompose the sequence into subunits by compressing the description of the information flow within the Markov source that generates the sequence. We illustrate the method by partitioning several real-world sequences whose subunit structure is already known and find that the method detects this known structure with high sensitivity and reliability. We show the relative complexity of different types of sequences in terms of bits per transition step. Finally, we show relative information flow between levels of the sequence within a revealed hierarchy.