Santa Fe Institute Working Paper 17-07-XXX
arXiv:1707.XXXX

Prediction and Generation of Binary Markov Processes:
Can a Finite-State Fox Catch a Markov Mouse?
Joshua Ruebeck∗
Department of Physics and Astronomy, Carleton College,
One North College Street, Northfield, MN 55057

arXiv:1708.00113v1 [cond-mat.stat-mech] 1 Aug 2017

Ryan G. James,† John R. Mahoney,‡ and James P. Crutchfield§
Complexity Sciences Center and Physics Department,
University of California at Davis, One Shields Avenue, Davis, CA 95616
(Dated: August 2, 2017)
Understanding the generative mechanism of a natural system is a vital component of the scientific
method. Here, we investigate one of the fundamental steps toward this goal by presenting the minimal
generator of an arbitrary binary Markov process. This is a class of processes whose predictive model
is well known. Surprisingly, the generative model requires three distinct topologies for different
regions of parameter space. We show that a previously proposed generator for a particular set of
binary Markov processes is, in fact, not minimal. Our results shed the first quantitative light on
the relative (minimal) costs of prediction and generation. We find, for instance, that the difference
between prediction and generation is maximized when the process is approximately independently,
identically distributed.
Keywords: stochastic process, hidden Markov model, -machine, causal states, mutual information.
PACS numbers: 89.75.Kd 89.70.+c 05.45.Tp 02.50.Ey 02.50.-r 02.50.Ga

I.

INTRODUCTION

Imagine a mouse being chased by a fox. Survival suggests
that the mouse should generate a path that is difficult
for the fox to predict. We might imagine that the mouse
brain is designed or trained to maximize the fox’s difficulty
and, similarly, that the fox somehow has optimized the
task of predicting the mouse’s path. Are these two tasks
actually distinct? If so, do there exist escape paths that
are easier to generate than predict? Every animal has
limited computational resources and we might reasonably
suppose that the mouse has fewer than the fox. Given that
mice clearly continue to survive, we can ask whether this
disparity in resources exists in tension with the disparity in
task-complexity—path-generation versus path-prediction.
In lieu of mouse paths, we consider the space of discrete stationary stochastic processes—objects consisting
of temporal sequences that span the range from perfectly
ordered to completely random. We then frame resource
questions quantitatively via hidden Markov model (HMM)
representations of these processes. We focus on two particular HMM representations of any given process: the
minimal predictive HMM—its computational mechanics’ -machine [1]—and its minimal generative HMM. We

∗

†
‡
§

ruebeckj@carleton.edu
rgjames@ucdavis.edu
jrmahoney@ucdavis.edu
chaos@ucdavis.edu

then find two primary measures of memory resource: Cµ —
defined as the -machine’s state-entropy—quantifies the
cost of prediction, while Cg —the state entropy of the
generative machine—quantifies the cost of generation. Introduced over two and a half decades ago, the -machine
predictive representation is well studied and can be constructed for arbitrary processes [2]. The generative machine offers more challenges, as it involves a nonconvex
constrained minimization over high-dimensional spaces.
While there are several known bounds on Cg and restrictions on the construction of generative HMMs [3–6], they
have received significantly less attention than the predictive case and, as a consequence, are markedly less well
understood.
The following presents the first construction of the minimal generators for an arbitrary stationary binary Markov
process. This allows for the analytic calculation of Cg ,
as well as other properties of generative models. These
models elucidate the differences between the tasks of generation and prediction. The techniques introduced here
should also lead to minimal generators for other process
classes.

II.

MODELS

We represent stochastic processes using edge-emitting
(Mealy) hidden Markov models (HMMs). Such a representation is specified by a set of states, a set of output
symbols, a set of labeled transition matrices, and a sta-

2
exact conditional probability distribution Pr(X0:` |x:0 ) for
any length `.

R
ϕ

X:0
χ

X0:
A.

ζ
E

FIG. 1. I-diagram [7] of the X:0 − R0 − X0: Markov chain [8].
The state of a generating model shields the past and future,
rendering them conditionally independent. This is reflected
by the overlap E between the past and future being entirely
captured (contained within) the system state entropy H [R].
The past and future further segment R into the crypticity χ,
gauge information ϕ, and oracular information ζ; quantities
whose interpretation is explored further in Ref. [9].

tionary distribution over states. We consider stationary
processes so, assuming the state transition structure is
mixing, the invariant state distribution is unique and is
therefore redundantly determined from the labeled transition matrices.
Clearly, not every HMM corresponds to any given process. If a model is to correspond to a particular process, its states must yield conditional independence between the past and future. That is, the past X−∞:0
and future X0:∞ random variable chains yielded by a
model must be rendered independent by the model’s
current state R0 ; information-theoretically, we have:
I [X−∞:0 : X0:∞ |R0 ] = 0. The (unconditioned) mutual information E = I [X−∞:0 : X0:∞ ] between past and future
is called the excess entropy. Among other uses, it is the
amount of uncertainty about the future one may reduce
through knowledge of the past. Intuitively then, the state
of a correct model must “capture” E bits of information;
see Fig. 1. (For brevity, the following suppresses infinite
variable indexes.)
There are an infinity of models for a given stochastic
process. Depending on context, certain models will have
merits above those of others. The ability to predict is one
such context.

The minimal predictive model of a process P is known
as its -machine and its construction is straightforward.
The theory of computational mechanics provides a framework for the detailed characterization of -machines in
topological and information-theoretic terms [1].
The kernel underlying this construction is the causal equivalence relation ∼ . This is a relation over the set {x:0 }
of semi-infinite pasts such that two pasts, x:0 and x:0 0 ,
belong to the same equivalence class if their conditional
futures agree:
x:0 ∼ x:0 0 ⇐⇒ Pr(X0: |x:0 ) = Pr(X0: |x:0 0 ) .
Each equivalence class is a state of the system, encapsulating in minimal form the degree to which the past
influences the future. Thus, we refer to the classes as
causal states and denote by St the causal state at time t.
The memory required by the -machine to implement the
act of prediction is Cµ = H [S]—the statistical complexity.
1

Then, transitions between these states follow directly from
the equivalence relation:
k
Ti,j
= Pr(X0 = k, S1 = j|S0 = i) .

As previously stated, the excess entropy E is the amount
of information shared between past and future. The
causal equivalence relation induces a particular random
variable S that “captures” E. Importantly, E is not itself
the entropy of a random variable. Thus, the causal-state
random variable cannot generally be of size E bits. We
might then think of the difference χ = Cµ −E, also known
as the crypticity, as the predictive overhead [10]. It is an
interesting fact that a nonzero predictive overhead χ is
generic in the space of all processes.
B.

III.

PREDICTIVE MODELS

What is prediction? Loosely speaking, prediction has to
do with a relation between two variables, one which we
think of as input and the other as output. In our context
of stochastic processes, the input is the past X:0 and the
output is the future X0: . By prediction we mean: Given
some instance of the past x:0 , the task is to yield the

-Machine Construction

Binary Markov Processes

Let us now narrow our focus and construct the predictive
models for the particular class of binary Markov processes.

1

This notion of memory applies in the ensemble setting. Singleshot or single-instance memory is also of interest and is studied
in .

3

A

0:q

B

1:1 − q

B

ia
s

q

More specifically, we consider all stationary stochastic
processes over the symbol set {0, 1} with the Markov
property:

Its stationary state distribution is:


1−q
1−p
π=
,
.
2−p−q 2−p−q
The informational properties of this class of processes—
entropy rate, excess entropy, and statistical complexity—
can be stated in closed form:
hµ = πA H (p) + πB H (q) ,
E = H [π] − hµ ,

Cµ = E + hµ ,

where H (p) = −(p log p) + −((1 − p) log (1 − p)) denotes
Shannon’s binary entropy function [8]. The simple relation among these measures follows from the fact that any
(nontrivial) binary Markov process is also equivalent to a
spin chain—a restricted class of Markov chains [10].
This class of binary Markov processes spans a variety
of structured processes, summarized in Fig. 3. At the
extremes of either p = 0 or q = 0, we have a period1 (constant) process. If either p = 1 or q = 1, we have
Golden Mean Processes, where 0s or 1s, respectively, occur
in isolation. If p = 1 − q, the process loses its dependence
on the prior symbol and it becomes a biased coin.

IV.

GENERATIVE MODELS

Let’s now return to our original topic and describe the
second type of process representation—generative models.
The only requirement of a generative model is that it be
able to correctly sample from the distribution Pr(X0: )

N-E
0

P-2

Fair
Coin

C

rb

u
rt
Pe

Pr(X0 |X−∞:0 ) = Pr(X0 |X−1 ) .
Applying the causal equivalence relation, we find that
the causal state is completely determined by the previous single symbol, a simple consequence of the process’
Markovity. This leads directly to the -machine in Fig. 2.

ed

Golden Mean

oi
n

Period-1

FIG. 2. -Machine for all binary Markov processes. Cases with
p = 1 − q or p = 0 or q = 0 are single-state -machines that
are minimal in all respects: predictive or generative, entropic
or dimensional.

1

Golden Mean

1:p
0:1 − p

ed

n
oi

C

hr

Lo

Period-1
p

1

FIG. 3. Process space spanned by binary Markov processes.
When either p = 0 or q = 0, the process is constant, repeating
0s or 1s, respectively. In the limit p = q = 0 the process is
nonergodic, realizing only one or the other of the two constant
processes. When either p = 1 or q = 1, the expressed processes
are known as Golden Mean Processes, characterized by isolated
0s or 1s, respectively. Along the line p = 1 − q the process
is a biased coin. Along the line p = q, the process is known
as a perturbed coin, where states A and B each represent an
oppositely biased coin and the process switches between the
two biases based on the symbols just emitted.

over futures. More specifically, we require that, given any
instance x:0 of the past, the generative model yields a
next symbol X0 with the same probability distribution
Pr(X0 |X:0 = x:0 ) as specified by the process.
Note that, on the one hand, it may seem obvious that
prediction subsumes generation. On the other, it is not
so obvious how these two tasks might prefer different
mechanisms.
Like the -machine causal state, a generative state R
must also render past and future conditionally independent. Importantly, as a consequence of the causal equivalence relation -machines are unifilar which, when paired
with their minimality, implies that the causal states are
functions of the prior observables. Generative models,
however, need not have this restriction. Consequently, a
given sequence of past symbols (finite or semi-infinite)
may induce more than one generative state.
Generative models are much less well understood than
their predictive cousins. This is due in large part to
the lack of constructive methods for working with and
otherwise constructing them. This is why our results here,
though addressing only on a relatively simple class of
processes, mark a substantial step forward.

4
0:p

0 : 1 − 2p

C

0 : 12 − p
0 : 2p

D

1 : 12 − p
1 : 2p

E

1 : 1 − 2p

1:p

FIG. 4. Löhr model: A three-state HMM that generates the
same process as that in Fig. 2 when 0 ≤ p = q ≤ 1/2. Its
principle interest arises since it has a smaller state entropy
than the -machine for a range of p values: H [R] ≤ Cµ .
V.

LÖHR EXAMPLE

Let us now focus on a subclass of binary Markov processes,
those for which 0 < p = q < 1/2; refer to the orange line
in Fig. 3. Reference [4] offers up a three-state HMM generator for this class, which we refer to as the Löhr model;
see Fig. 4. We see from the HMM that when probability
p is near 1/2, the process is nearly independent, identically
distributed (IID). An IID process has only a single causal
state and therefore zero statistical complexity, Cµ = 0.
However, for any deviation from p = 1/2, the statistical
complexity is a full bit, Cµ = 1. Why is it that a generator of a nearly IID process—that is, a nearly memoryless
process—still needs a full bit of memory?
The motivation for constructing this three-state model is
that it might concentrate the IID behavior into a single
state and use the other states only for those infrequent
deviations that “make up the difference”. And so, the
state-entropy may be reduced even though there are three
states instead of two. A priori it is not obvious that it is
possible to yield the correct process in this construction.
It is, however, straightforward to check that the Löhr
model produces the correct conditional statistics. It is
a generator of the processes. Note that in general it
is sufficient to check these probabilities for all words of
length 2N − 1 where N = max(|S|, |R|) [11, Corollary
4.3.9].
We find that the Löhr model has the stationary state
distribution:
π = [1/2 − p, 2p, 1/2 − p] .
As noted, the statistical complexity Cµ = 1 for p’s entire range. The state entropy H [R] = H [π] of the Löhr
model is smaller than Cµ = 1 for the range of values
p ∈ (0.38645 . . . , 0.5). Importantly, this is sufficient to
show that prediction and generation are generally different tasks—they have different optimal solutions. This
was previously shown in Ref. [4]. However, the question remained whether or not the Löhr model is minimal.
Surprisingly, though subsequent works on generative com-

1 : (1−α)(q−α)
β−α

1 : (1−α)(β−q)
β−α

A
0 : α(β+p−1)
β−α

0 : α(1−p−α)
β−α
1:

(1−β)(β−q)
β−α

1 : (1−β)(q−α)
β−α

B
0 : β(1−p−α)
β−α

0 : β(β+p−1)
β−α

FIG. 5. Parametrized HMM for the complete set of 2-state
machines that generate the space of binary Markov chain
processes when α ≤ min {q, 1 − p} and β ≥ max {q, 1 − p}
and we assume α < β. A second isomorphic class follows from
the assumption β < α.

plexity have appeared, to the best of our knowledge this
example is the only HMM published that is entropically
smaller than the (finite-state) -machine.
We will now construct the provably minimal generator
for these processes. Further, we extend our analysis, not
only to the range p > 1/2, but to the entire (p, q) domain
of Fig. 3.
A.

Bounds

Recall that, for some p, the Löhr model is entropically
smaller than the -machine and it achieves this while
having three states instead of two. The important point
is that minimization of entropy in the generative context
does not limit the number of states in the same way
as in the predictive one. (Recall that among predictive
models, the -machine is minimal in both entropy and
state number [2].)
A recent result shows that the maximum number of
states
 in an entropically minimal channel Z is |Z| ≤
min |X||Y |, 2min{|X|,|Y |} − 1 , where X and Y are the
channel input and output processes [12]. Since a generative model is a form of communication channel from
the past to the future, we find that the number of
states of the
model is bounded by
 minimal generative
min{|X:0 |,|X0: |}
|R| ≤ min |X:0 ||X0: |, 2
− 1 . Of course,
this result is useless on its own: |X:0 | and |X0: | are generically infinite.
This bound can be made practical by combining the
data processing inequality for exact common information
G [X : Y ] [12] with the existence of the following two
Markov chains [13]:
X:0 − S + − S − − X0: , and

S + − X:0 − X0: − S − .

We denote forward- and reverse-time causal states S +

5

1:p + q − 1

A

A

0:1

0:1 − p
p
0 : 1−q

0:

q(1−p−q)
1−q

1

B

β

1:1 − q

pq
0 : 1−q

1:1 − q

0.8
0

1

0.1 0.2
α

A

B
0:p + q − 1

q

0 : 1−p−q
1−q

1
β

0.9

1:1

B

0.9

0:1 − p

0.8
0.2 0.4
α
β

0

0

1

1:1 − q

1

p

pq
1 : 1−p

q
1 : 1−p

0.8
1:

0.6
0

0.1 0.2
α

(1−p−q)
1−p

A

B
1:

p(1−p−q)
1−p

0:1 − p

FIG. 6. Two-parameter process space of binary Markov processes: Consider three points within this space. For each, there is a
two-parameter model space. Within each model space we examine the model’s state entropy and identify the global minima. We
exhibit the corresponding HMMs. Topological changes in these minimal HMMs induce a three-region partition on process space.

and S − , respectively. Combined, these tell us that
G [X:0 : X0: ] = G [S + : S −n]. Therefore, the bound can be
o
+
−
tightened to |R| ≤ min |S + ||S − |, 2min{|S |,|S |} − 1 .

This is a particularly helpful application of causal states.
B.

Binary Markov Chains

In the particular case of processes represented by binary
Markov chains, the reverse process is also represented
by a binary Markov chain. And so, both |S + | = 2 and
|S − | = 2. From the above bounds, we find that |R| ≤ 3.
Closely following the proof in Ref. [12], one can then show
that no three-state representation is minimal. And, since
a single state model can only represent IID processes,
this leaves only models with two-states as the possible
minimal representations.
We begin with the assumption that an observation X0
maps stochastically to a state R0 , which then stochastically maps to a symbol X1 . Constraining this pair of

channels to produce observations X0 and X1 consistent
with the binary Markov chain yields the parametrized
hidden Markov model found in Fig. 5. (Appendix III
gives the background calculations.)
For each point (p, q) in the binary Markov process-space,
we now have a two-parameter model-space of HMMs,
specified by (α, β). The constraint that conditional probabilities be between zero and one restricts our modelspace parameters to a rectangle α ≤ min {q, 1 − p} and
β ≥ max {q, 1 − p}. One can now compute the state entropy within this constrained model-space and identify
the minima.
Since the entropy is concave in α and β and the allowable regions in (α, β)-space are convex (rectangles), it is
sufficient to search for local minima along the boundary.
Figure 6 illustrates this for three different points in process
space. We find that at each of the points (p = 1/4, q = 1/2)
and (p = 1/2, q = 1/4), there is a single global minimum.
For the point (p = 3/4, q = 3/4), we find that there are
two minima equivalent in value, but corresponding to

6
nonisomorphic HMMs. Both representations are biased
toward producing a periodic sequence, with fluctuations
interjected at different phases of the period.
In this way, one can discover the minimal generator for any
binary Markov chain. Examining these minimal topologies at each point, we find that process-space is divided
into three triangular regions with topologically-distinct
generators. This is a somewhat surprising contrast with
the fact that this model class requires only one predictive
topology.
Let us briefly return to the restricted process previously
considered—the perturbed coin. We may now quantitatively compare the three state-entropies of interest. In
Fig. 7 we see that the statistical complexity Cµ = 1 everywhere, but at p = 1/2, where it vanishes, Cµ = 0. The
Löhr model’s state-entropy CL falls below Cµ , but only
for a subset of p values. However, the generative complexity Cg (a smooth function) is everywhere less than
both Cµ and CL . (The generative models for p < 1/2 and
p > 1/2 are shown above.) This shows that the proposed
Löhr model is not the generative model for any value of
p.
As implied by the conditional independence requirement,
the excess entropy E remains a lower bound on each of
these state-entropies. Löhr [4] constructed a tighter lower
bound, denoted L, on any model of the perturbed coin.
We see that Cg is slightly larger than this bound. It
may be useful to generalize this lower bound for other
processes.
The minimal generators are defined over all of (p, q)-space.
We can compare the cost Cµ of prediction with the cost
Cg of generation and the information necessarily captured
by a model—the excess entropy E. This comparison is
seen in Fig. 8.
Focusing on the upper two panels of Fig. 8, we see that
both Cµ and Cg display p ↔ q symmetry. Furthermore,
Cg has a discontinuous derivative along this line of symmetry, but only in the southwest (SW).
For Cµ , the line p + q = 1 is special in that this lines
marks a causal-state collapse—two causal states merge
into one under the equivalence relation. For Cg , however,
this line marks a qualitative change in behavior (SW
versus NE). Since the generative complexity is lower semicontinuous [3], we know that a predictive gap Cµ − Cg
must exist around this line.
The lower two panels of Fig. 8 suggest that the costs of
generation and of prediction may have different causes.
The parameters for which Cg − E is high are disjoint from
those where Cµ − Cg is high. Cg is high when p and q
are correlated (near the p-q symmetry line), but only for
p q < 1/2. In the other half of parameter space, Cg is
high when p and q are anti-correlated and away from the

2

p
1 : 1−p

p
1 : 1−p

1 : (1−2p)
1−p

A

1:1 − p

A

B
1 : p(1−2p)
1−p

0:1 − p

0:1 − p

1 : 2p − 1

B

0:1

Cµ
Cg
CL
E
L

1.5

1

0.5

0

0

0.2

0.4

0.6

0.8

1

FIG. 7. State entropy of various models of the perturbed coin:
The excess entropy E is the amount of information any model
of a process must possess. A stronger lower bound L claimed
by Löhr is also plotted. Entropies of the three models: Cµ for
the -machine, CL for Löhr’s model, and Cg for the generative
model. While CL is less than Cµ for some values of p, Cg is
less than both Cµ and CL everywhere.

causal collapse. In contrast, Cµ is high exclusively near
the line of causal collapse.

VI.

CONCLUSION

We presented the minimal generators of binary Markov
stochastic processes. Curiously, the literature appears
to contain no other examples of generative models, for
processes with finite-state -machines. And so, our contribution here is a substantial step forward. It allows us to
begin to understand the difference between prediction and
generation through direct calculation. It also opens these
new models to analysis by a host of previously developed
techniques including the information diagrams presented
here.
To put the results in a larger setting, we note that HMMs
have found application in many diverse settings, ranging
from speech recognition to bioinformatics. And so, there
are many reasons to care about the states and informationtheoretic properties of these models, some obvious and
some not. It is common to imbue a state with greater
explanatory power than, say, a random variable that
merely exhibits the correct correlations for the observables
at hand. For instance, we may seek independent means of

7
1

Cµ

Cg

Cµ − Cg

Cg − E

lecting one model over another is through application
of a penalty related to the number of states (or entropy
thereof) [14]. Since the predictive model will never have a
lower entropy than the corresponding generative one, an
entropic penalty should never yield the predictive model,
however a state-number penalty might. Similarly, in
model parameter inference, if one distinguishes between
the predictive and generative classes, the maximum likelihood estimated parameters will differ between the two
classes.

0.8

q

0.6
0.4
0.2
0
1
0.8

q

0.6
0.4
0.2
0

0

0.2

0.4

0.6

0.8

1

0.2

p
0

0.2

0.4

0.6

0.8

1

p
0.4

0.6

0.8

1

FIG. 8. State complexity of the two canonical models:
-machine and generative machine. The predictive overhead,
Cµ − Cg , quantifies the information required to enable prediction above and beyond generation. The generative overhead,
Cg − E, quantifies the amount of information a model of a process requires beyond that minimally required by the observable
correlations.

determining the state. Whether or not this is appropriate,
the fact remains that the different tasks of prediction and
generation are associated with different kinds of state,
each with different kinds of explanatory usefulness. This
distinction seems to us to be rarely if ever made in HMM
applications.
The concept of model state is central, for example, in
model selection. A simple and common method for se-

[1] J. P. Crutchfield. Between order and chaos. Nature
Physics, 8(1):17–24, 2012.
[2] C. R. Shalizi and J. P. Crutchfield. Computational mechanics: Pattern and prediction, structure and simplicity.
J. Stat. Phys., 104:817–879, 2001.
[3] W. Löhr. Predictive models and generative complexity.
J. Systems Sci. Complexity, 25(1):30–45, 2012.
[4] W. Löhr and N. Ay. Non-sufficient memories that are
sufficient for prediction. In International Conference on
Complex Sciences, pages 265–276. Springer, 2009.

Finally, we close by drawing out the consequences for
fundamental physics. Understanding states bears directly
on thermodynamics. Landauer’s Principle states that
erasing memory comes at a minimum, unavoidable cost—
a heat dissipation proportional to the size of the memory
erased [15]. One can consider HMMs as abstract representations of processes with memory (the state) that must
be modified or erased as time progresses. Applying Landauer’s Principle assigns thermodynamic consequences
to the HMM time evolution. Which HMM (and corresponding states) is appropriate, though? We now see
that prediction and generation, two very natural tasks
for a thermodynamic system to perform, actually deliver
two different answers. It is important to understand how
physical circumstances relate to this choice of task—it
will be expressed in terms of heat.

ACKNOWLEDGMENTS

We thank the Santa Fe Institute for its hospitality during
visits, where JPC is an External Faculty member. This
material is based upon work supported by, or in part by,
John Templeton Foundation grant 52095, Foundational
Questions Institute grant FQXi-RFP-1609, and the U. S.
Army Research Laboratory and the U. S. Army Research
Office under contracts W911NF-13-1-0390 and W911NF13-1-0340. JR was funded by the 2016 NSF Research
Experience for Undergraduates program.

[5] W. Löhr and N. Ay. On the generative nature of prediction.
Adv. Complex Sys., 12(02):169–194, 2009.
[6] A. Heller. On stochastic processes derived from markov
chains. Ann. Mat. Stat., 36:1286–1291, 1965.
[7] R. W. Yeung. A new outlook on Shannon’s information
measures. IEEE Trans. Info. Th., 37(3):466–474, 1991.
[8] T. M. Cover and J. A. Thomas. Elements of Information
Theory. Wiley-Interscience, New York, second edition,
2006.
[9] J. P. Crutchfield, C. J. Ellison, J. R. Mahoney, and R. G.
James. Synchronization and control in intrinsic and de-

8

[10]

[11]

[12]
[13]

[14]
[15]
[16]

signed computation: An information-theoretic analysis of
competing models of stochastic computation. CHAOS,
20(3):037105, 2010.
J. R. Mahoney, C. J. Ellison, R. G. James, and J. P.
Crutchfield. How hidden are hidden processes? A
primer on crypticity and entropy convergence. CHAOS,
21(3):037112, 2011.
D. R. Upper. Theory and Algorithms for Hidden Markov
Models and Generalized Hidden Markov Models. PhD
thesis, University of California, Berkeley, 1997. Published
by University Microfilms Intl, Ann Arbor, Michigan.
G. R. Kumar, C. T. Li, and A. El Gamal. Exact common
information. In Information Theory (ISIT), 2014 IEEE
International Symposium on, pages 161–165. IEEE, 2014.
Ryan G James, John R Mahoney, and James P Crutchfield. Information trimming: Sufficient statistics, mutual
information, and predictability from effective channel
states. Physical Review E, 95(6):060102, 2017.
H. Akaike. Ann. Inst. Statist. Math., 29A:9, 1977.
R. Landauer. Irreversibility and heat generation in the
computing process. IBM J. Res. Develop., 5(3):183–191,
1961.
S. Kamath and V. Anantharam. A new dual to the GácsKörner common information defined via the Gray-Wyner
system. In Communication, Control, and Computing
(Allerton), 2010 48th Annual Allerton Conference on,
pages 1340–1346. IEEE, 2010.

1

Supplementary Materials
Prediction and Generation of Binary Markov
Processes:
Can a Finite-State Fox Catch a Markov Mouse?
Joshua Ruebeck, Ryan G. James, John R.
Mahoney, and James P. Crutchfield
These supplementary materials give additional information on the processes and models analyzed in the main
body. They cover the relationship between causal states
and Löhr states, process information diagram analysis,
including crypticity and oracular information, and the
derivation of the general, parametrized binary Markov
process model itself.
I.

CAUSAL STATES AND LÖHR STATES

Since the process considered in the main article is Markov
order R = 1 and its causal states are in one-to-one correspondence with the symbol last seen, we can compactly
represent the relation between pasts, causal states, and
Löhr states. The mapping from causal states A and B
(or observation symbols 0 and 1) to states C, D, and E
of the Löhr presentation is given by:

Pr(R|S) =

A/0
B/1

C

D

E

1 − 2p

2p

0

2p

1 − 2p

0

!

(S1)

For example, if the last symbol was x = 0, this induces
causal state A. The corresponding Löhr states occur with
respective probabilities Pr(C, D, E) = (1 − 2p, 2p, 0).
II.

INFORMATION DIAGRAM ANALYSIS

The information diagram [7] is a tool that has become
increasingly useful for analyzing and characterizing the information content of process presentations [13]. It gives a
visual representation of multivariate information-theoretic
dependencies. It arises from a duality between information measures and set theory: set-intersection corresponds
to mutual information and set-union corresponds to joining distributions. Here, we analyze several information
measures introduced in Ref. [9] for the processes considered in the main article; the associated I-diagram is
depicted in Fig. 9.
A generic model state R has nonzero intersection (mutual
information) with both the process’ past X:0 and future
X0: : I [R : X:0 ] > 0 and I [R : X0: ] > 0. Importantly, the

R
X:0

ϕ
S

χ

X0:
ζ

E

FIG. 9. I-diagram depicting how different kinds of information
are shared among a process’ past X:0 , future X0: , (forward)
causal states S, and generative states R. Several information
atoms are labeled: the process’ past-future mutual information
or excess entropy E, the crypticity χ, the oracular information
ζ, and the gauge information ϕ.

state information of a model that correctly generates a
process—a process presentation—must intersect the pastfuture union, which completely contains the past-future
intersection. We might say that the state of the model
“captures” this atom—the excess entropy E = I [X:0 : X0: ].
Any model that does not capture at least E of the past
and future cannot correctly generate the process. (Recall
that if a model is predictive, then it is also generative.)
The -machine is simple not only in the sense that it is
constructible, but it is informationally simple as it appears in the information diagram as well. This simplicity
follows from the fact that causal states are functions
of the past. As a result, -machine state information
has no intersection with the future beyond that of that
past’s—it contains no, what we call, oracular information
ζ = I [R : X0: |X:0 ]. It also contains no information outside the past-future union—it contains not gauge information ϕ = H [R|X:0 , X0: ]. Beyond the excess entropy atom,
it has only one potential region—what we call the process’
crypticity χ-machine = Cµ − E, where Cµ = H [S] is the
process’ statistical complexity.
The situation is richer for general representations, including generative ones; denote them g. The more general
definition of crypticity is χg = I [R : X:0 |X0: ]. A general
representation may have oracular and gauge information.
And, it may have a crypticity greater than, equal to, or
less than the -machine crypticity.
Generative models are restricted in two ways. First, their
crypticity is never greater than the -machine’s crypticity: χg ≤ χeM . This follows straightforwardly since if it
were greater, then the -machine would necessarily have
smaller state entropy, leading to a contradiction. Further,
the sum of the generative model’s crypticity, gauge information, and oracular information must be less than the

2

E

1

χ

0.8

χ

ϕ

ζ

q=p

q = 1/4

q = 1/2

q = 3/4

0.8

0.6
q

0.6

0.4

0.4

0.2

0.2

0

ζ

1

1

ϕ

0.8

0.8

0.6

0.6
q

0.4

0.4

0.2

0.2
0

E

1

0
0

0.2

0.4

0.6

0.8

1

0.2

0.4

p
0

0.2

0.6

0.8

1

0

0.2

0.4

0.6

0.8

1

0.2

0.4

p

0.6

0.8

1

p

p
0.4

0.6

0.8

1

FIG. 10. Decomposition of the generative state information
Cg into excess entropy E, crypticity χ, oracular information
ζ, and gauge information ϕ over process space (p, q).

-machine’s crypticity:
χg + ϕg + ζg ≤ χeM

(S2)

Second, appealing to our newly introduced generative
models for binary Markov chains, we can compare the
generative-model crypticity to that of the -machine. A
generative model distinct from the -machine must have
nonzero oracular information [16]. Also, a generative
model may only have nonzero gauge information if it has
both crypticity and oracular information [16]:
ϕg > 0 =⇒

(

χg > 0
ζg > 0

,

(S3)

while still satisfying Eq. (S2). Effectively, this means
that gauge information can be “minimized” away, unless
it supports the existence of both cryptic and oracular
information.
For our parametrized generative models of binary Markov
chains we find that Cg decomposes as shown in the two
mosaics in Figs. 10 and 11. The gauge information ϕg
is, generally, a rather small portion of Cg , though it is
largest in the same regions as Cg − E. Both the crypticity
χg and the oracular information ζg are large along the

FIG. 11. Decomposition of Cg for several slices of process
space, revealing more directly their functional dependencies.

q = 1 and p = 1 edges, respectively. This implies that
R “leans left” when q ≈ 1 and “leans right” when p ≈ 1.
This relationship flips if we use the alternative, equivalent
model in the p > 1 − q half of the process space.
Note that while gauge information is not required of generative models, it is present in all of the binary Markov
chain generators, except along boundary and causal collapse lines. Surveys of other processes suggest that the
presence of gauge information may be somewhat rare.

III.

PARAMETRIZED BINARY MARKOV
PROCESS HMM: DERIVATION

We derive the most generic parametrized, two-state HMM
of binary Markov processes. The target binary Markov
process is represented by the conditional probability matrix:

Pr(Xt |Xt−1 ) =

0
1

0

1

1−p

p

q

1−q

!

(S4)

As an intermediate step to deriving the full HMM, we
find the conditional probabilities involving the machine
states relative to the symbols emitted on the transitions to
and from a state. We write down two template matrices,
denoting the states A and B and the random variable

3
1 : ᾱ − u

1:u

A
0:s

(a) being generated by this incomplete HMM:

1:t

0:α − s

Pr(01) = Pr(01|A) Pr(A) + Pr(01|B) Pr(B)

B

1 : β̄ − t

= [s(1 − α) + (α − s)(1 − β)] Pr(A)

+ [(β − r)(1 − α) + r(1 − β)] Pr(B)

0:r

0:β − r

FIG. 12. As an intermediate step, we construct a skeleton
for the fully general HMM. r, s, t, u are temporary variables
to be solved for eventually. The other transitions are labeled
using the fact that, for example, the probabilities of the paths
coming from state A and emitting a 0 must sum to α in order
to agree with Eq. S5.

over them R:
Pr(Xt |R) =

0

1

A

α

B

β

1−α

and (b) being generated by the Markov process described
in Eq. (S4):
Pr(01) = Pr(1|0) Pr(0)
= p Pr(0) .

We used the string 01 as our first case. And, Pr(0), Pr(1),
Pr(A), and Pr(B) are given by the stationary distributions
over the symbols and states, respectively:
q
p+q
p
Pr(1) =
p+q
qγ + pδ
Pr(A) =
p+q
q(1 − γ) + p(1 − δ)
Pr(B) =
.
p+q

!

(S5)

and:

Pr(R|Xt−1 ) =

B

0

γ

1

δ

1−γ

(S9)

Pr(0) =

1−β

A

(S8)

!

1−δ

.

(S6)

there is ambiguity here in labeling the states. If we switch
the rows of Eq. (S5) with each other and the columns
of Eq. (S6) with each other, then we obtain different
matrices that describe the same model. Only the the
state labels have been swapped. To avoid double-counting
such machines, we restrict α ≤ β.
Multiplying out this factorization and requiring it to be
consistent with the target provides two constraints:
γ=

β+p−1
β−α

,

δ=

β−q
.
β−α

(S7)

(We keep the denominators as β − α so that both the
numerator and denominator are positive.) We ask that
all these be valid probabilities. Requiring 0 ≤ γ, δ ≤ 1
and substituting Eq. (S7) yields the constraints:

Setting Eqs. (S8) and Eq. (S9) equal to one another
constrains r, s, t, u. To fully specify all four, though, we
need three more independent equations. We obtain these
by evaluating the probabilities of the strings 11, 110, and
000 in a similar fashion. Respectively, these yield:
(1 − q) Pr(1) = [u(1 − α) + (1 − α − u)(1 − β)] Pr(A)

+ [t(1 − β) + (1 − β − t)(1 − α)] Pr(B) ,

q(1 − q) Pr(1) = [u((1 − α − u)β + uα)

+ (1 − α − u)(tβ + (1 − β − t)α)] Pr(A)

α ≤ min{q, 1 − p},

β ≥ max{q, 1 − p} .

Now, consider the incomplete HMM that defines the
helper variables r, s, t, u in Fig. 12. To determine the
latter’s values, we evaluate the probabilities of a string

+ [t(tβ + (1 − β − t)α)

2

+ (1 − β − t)((1 − α − u)β + uα)] Pr(B), and

(1 − p) Pr(0) = [s((α − s)β + sα)

+ (α − s)(rβ + (β − r)α)] Pr(A)
+ [r((β − r)α + rβ)

+ (β − r)((α − s)β + sα)] Pr(B) .

4
Solving this system yields:
β(1 − p − α)
,
β−α
α(β + p − 1)
s=
,
β−α
(1 − β)(q − α)
, and
t=
β−α
(1 − α)(β − q)
u=
.
β−α
r=

Finally, we substitute these into Fig. 12 to recover the
parametrized HMM the main article introduced in Fig.
5.

