Exploring a strongly non-Markovian behavior

Is there some simplicity or universality underlying the complexities of natural animal behavior?~Using the walking fruit fly as a model system, we have shown that unconstrained behaviors can be categorized into roughly one hundred discrete states, which all individuals from a single species visit repeatedly. In each state, the fly executes stereotyped movements, and the transitions between states are organized hierarchically. The sequences of states, however, are strongly non-Markovian: correlations persist for orders of magnitude longer than expected from the state-to-state transition probabilities, and there are hints of power law decay. But with 100 states, further analysis is difficult. Here we develop a generalization of the information bottleneck method to compress these states into a more compact description that preserves as much of the temporal correlations as possible. We find that, even on compressing down to just two states, this coarse grained description of behavior captures the long ranged correlations. Power law decays are clearer in this reduced representation, which opens the way for more quantitative analysis.