# Information dynamics and the arrow of time

Aram Ebtekar<EMAIL_ADDRESS>Vancouver, BC, Canada

###### Abstract

Why does time appear to pass irreversibly? To investigate, we introduce a
class of partitioned cellular automata (PCAs) whose cellwise evolution is
based on the chaotic baker’s map. After imposing a suitable initial condition
and restricting to a macroscopic view, we are left with a stochastic PCA
(SPCA). When the underlying PCA’s dynamics are reversible, the corresponding
SPCA serves as a model of emergent time-reversal asymmetry. Specifically, we
prove that its transition probabilities are homogeneous in space and time, as
well as Markov relative to a Pearlean causal graph with timelike future-
directed edges. Consequently, SPCAs satisfy generalizations of the second law
of thermodynamics, which we term the Resource and Memory Laws. By subjecting
information-processing agents (e.g., human experimenters) to these laws, we
clarify issues regarding the Past Hypothesis, Landauer’s principle, Boltzmann
brains, scientific induction, and the so-called psychological arrow of time.
Finally, by describing a theoretical agent powered by data compression, we
argue that the algorithmic entropy takes conceptual precedence over both the
Shannon-Gibbs and Boltzmann entropies.

##  I Introduction

The complete trajectory of a dynamical system can be specified in two parts:
(1) an initial condition that specifies its configuration at the initial time,
and (2) dynamics that specify how the configuration evolves over time. It’s
widely believed that the Universe exhibits CPT symmetry: under a simultaneous
reversal in charge (C) and parity (P), its dynamics are symmetric in time (T).
In other words, every video recording remains physically valid when played in
rewind 111With minor caveats: the fact that it’s CPT instead of just T means
that every particle in the rewinded video behaves like the mirror image of its
respective antiparticle.. CPT is a rigorous theorem in axiomatic quantum field
theory [1], standing in stark contrast to our everyday experience with
irreversible phenomena. Indeed, fragile items drop and shatter, but don’t
unshatter and undrop; we _remember_ yesterday’s events, but _plan_ tomorrow’s
agenda; causes precede effects. If the dynamics are truly symmetric, then, by
a process of elimination, only a special choice of initial condition can break
the symmetry.

In particular, the initial condition must be set in such a way as to imply the
second law of thermodynamics: a general principle of physics that forbids the
entropy of any closed system from decreasing. Much work has gone into
justifying various formal definitions of entropy, along with conditions that
would imply the second law. Even if the second law is taken for granted,
relating it to causal and decision-theoretic concepts remains a challenge.

From Maxwell’s demon to Poincaré recurrence to Landauer’s principle, the
subject of irreversibility has a history fraught with debates and
misunderstandings [2]. To increase confidence in our main results, we take a
mathematically rigorous approach in which all modeling assumptions are laid
bare. Modeling choices are made in an effort to balance conceptual clarity,
generality, and applicability to real physics. We abstract away what we can
from physical field theories, substituting a generic class of cellular
automata in their place.

Like our Universe, these automata have dynamics that are reversible
microscopically, but not macroscopically; as such, they model the emergence of
asymmetries with respect to time reversal, i.e., arrows of time. Despite
deterministic dynamics, we discover precisely how Markovian probabilities
emerge as a macroscopic behavior. By applying ideas from information theory
and Pearlean causality to these automata, we collect insights on how the arrow
of time operates. In particular, we learn why memories only inform us about
the past, and why causes precede effects.

Following the traditional sequence of physics pedagogy, this article only
models classical information, leaving extensions to the quantum setting for
future work. Our classical approach stands as a rebuttal against suggestions
that the psychological arrow of time is a distinctly quantum phenomenon [3,
4]. The remainder of this introduction develops the background, motivation,
and general structure of our approach.

###  I.1 Discrete-State Entropy

Our models are inspired by classical mechanics, which operates on a continuous
phase space. Before addressing the latter, we start with the discrete setting,
where entropy has a clearer meaning. Even there, entropy can be understood in
a number of ways. Intuitively, it’s often thought of as a measure of
combinatorial complexity, or “disorder”. Conversely, a _lack_ of entropy is
often thought of as a resource, akin to free energy; or as knowledge,
narrowing down the set of possible states. Loosely speaking, if the object $s$
is a “typical” element of some finite set $\mathcal{S}$, then we’d like to say
its entropy is $\log|\mathcal{S}|$.

To make this precise, we can define entropy as a function of a probability
measure $\mu$ on some countable set $\mathcal{S}$. The Shannon entropy of
$\mu$ (also known as its Gibbs entropy) is given by

$\displaystyle H(\mu):=\sum_{s\in\mathcal{S}}\mu(s)\log\frac{1}{\mu(s)}.$ (1)

The base of the logarithm is not important: since it only changes the entropy
by a constant factor, a change of base is effectively just a change of units.
For example, when the base is $2$, the entropy is given in bits. Note that
when $\mu$ is uniformly distributed over some subset $A\subset\mathcal{S}$, we
indeed have $H(\mu)=\sum_{s\in A}\frac{1}{|A|}\log|A|=\log|A|$.

For non-uniform $\mu$, the Shannon entropy is motivated by supposing that
$\mu$ is the joint distribution over a long sequence $s=(s_{1},\ldots,s_{n})$
from a stationary ergodic process. As a special case, the sequence can be
i.i.d. (independent and identically distributed), representing, for instance,
the state of $n$ particles in an ideal gas. As $n$ gets large, there is a
sense in which $\mu$ approximates the uniform distribution on a “typical set”
$\mathcal{S}_{\mathrm{typ}}$ of about $2^{H(\mu)}$ elements (where $H$ is
given in bits). In particular,
$H(\mu)\approx\log|\mathcal{S}_{\mathrm{typ}}|\approx nh$, where $h$ is the
entropy rate of the process [5, §16.8].

Note that $H$ is a function of $\mu$, not of $s$. In other words, the Shannon
entropy appears to depend on some subjective measure of our knowledge about
$s$, but not on its actual realization. Since we do not yet have the tools to
reason about subjective knowledge (see Section VI.3), we need a notion that’s
a direct function of $s$.

In statistical mechanics, the most common approach is to _coarse-grain_ the
state space into a union of Boltzmann macrostates:
$\mathcal{S}=\cup_{i}\mathcal{S}_{i}$. The macrostates $\mathcal{S}_{i}$ are
typically chosen to be disjoint; if not, identify each Boltzmann microstate
$s\in\mathcal{S}$ with the smallest macrostate containing it. The Boltzmann
entropy of $s$ is given by

$\displaystyle B(s):=\min\\{\log\mathcal{|}\mathcal{S}_{i}|:\mathcal{S}_{i}\ni
s\\}.$ (2)

Typically, the partition index $i$ corresponds to a collection of macroscopic
parameters, such as temperature, pressure, and chemical composition, specified
to a reasonable degree of precision. There is debate over the validity of the
coarse-graining procedure, since the Boltzmann entropy is very sensitive to
the choice of partition.

The theory of computation offers a third definition, which unifies and yields
additional insights into the preceding approaches. To apply it, we must fix a
universal Turing machine $U$, as well as a digital encoding $\langle s\rangle$
for each element $s\in\mathcal{S}$. The algorithmic $U$-entropy of
$s\in\mathcal{S}$ (also known as its Kolmogorov complexity) is then defined to
be the length of the shortest program $p$ 222In the literature, $p$ is usually
restricted to a prefix-free language. Li and Vitányi [6, §2-3] discuss in
depth the relationship between plain and prefix-free versions of the
algorithmic entropy. For the purposes of this article, the two notions are
close enough that we can ignore the distinction., whose output is $\langle
s\rangle$:

$\displaystyle K(s):=\min\\{|p|:U(p)=\langle s\rangle\\}.$ (3)

If $p$ is written in binary, then $K$ is given in units of bits. Once again,
there is some room to fudge the definition, by changing either the universal
machine or the encoding. Fortunately, for “reasonable” choices, the changes
would be very small. For instance, let’s see if some other machine $T$ can
yield substantially smaller complexities than $U$. The universality of $U$
means that it encodes $T$ as some string $\langle T\rangle$, satisfying
$U(\langle T\rangle,p)=T(p)$ for all programs $p$. Thus, the $U$-entropy of a
system cannot exceed its $T$-entropy by more than the constant $|\langle
T\rangle|$.

For a Universe with an effective minimum length scale (i.e., the Planck
length), it’s plausible that there would only exist finitely many functionally
distinct CPU designs (or Turing machine heads) with diameter smaller than,
say, a millimeter. Thus, $U$ can be chosen in such a way that every machine
$T$ with a small physical implementation also has a short encoding $\langle
T\rangle$ 333If a small physical implementation is discovered for such a $U$,
then all candidates for $U$ would have short encodings for one another, so $K$
would be determined to within a small additive term.. For large complex
systems described by very large $|p|$, the contribution $|\langle T\rangle|$
of any small machine becomes negligible in comparison. As for smaller systems,
in practice they are always embedded within a larger context: _conditional_
forms of the algorithmic entropy or universal prior can be used to quantify a
subsystem’s contribution to a larger system’s entropy [6, §3.8 and §5.2].

Thus, we argue that $K$ is the most objective and fundamental definition of
entropy. This perspective finds additional support in Section VI.4, where
compressible strings are shown to serve as a resource. In practice, $H$ and
$B$ are often easier to estimate; we now review conditions under which they
closely approximate $K$. Obviously, as long as such conditions hold, $H$ and
$B$ are approximately invariant to specific details of the chosen distribution
or coarse-graining partition.

Let’s first look at the Boltzmann entropy $B$. Any coarse-graining yields a
two-part code $p$ for each $s\in\mathcal{S}$, consisting of (1) the macrostate
$\mathcal{S}_{i}$’s description, and (2) an index of length
$B(s)=\log|\mathcal{S}_{i}|$, identifying $s$ within $\mathcal{S}_{i}$.
Suppose that (1) macrostates have short descriptions 444The number of
macrostates with short descriptions is necessarily limited. This suggests an
interesting coarse-graining: we can admit as macrostates _all_ subsets of
$\mathcal{S}$ whose descriptions are shorter than some fixed bound. If we do,
the Boltzmann entropy becomes the Kolmogorov structure function [6, §5.5]. In
practice, macrostates are usually specified in terms of a handful of
parameters such as temperature, pressure, and chemical composition. Describing
these to a satisfactory degree of precision takes on the order of $10^{3}$
bits. This is negligible in comparison to the entropy of a macroscopic system,
which typically exceeds Avogadro’s number ($>10^{23}$ bits). Thus, the code’s
second part indeed dominates. , and (2) $s$ is algorithmically typical (i.e.,
Martin-Löf random [6, §2.4]) with respect to the uniform distribution on
$\mathcal{S}_{i}$. Then, the two-part code is approximately optimal, and its
length is dominated by the index part [6, §5.5]. Therefore, $K(s)\approx
B(s)$.

Now, let’s look at the Shannon entropy $H$. As we saw previously, when $\mu$
describes a sufficiently long sequence from a stationary ergodic process,
$H(\mu)\approx\log|\mathcal{S}_{\mathrm{typ}}|$. This looks like a Boltzmann
entropy with macrostate $\mathcal{S}_{\mathrm{typ}}$, this set being
determined by the measure $\mu$, which in turn is a function of the underlying
process and sample size. To satisfy condition (1) from the previous paragraph,
the process should have a short description. With high probability, samples
$s$ drawn from $\mu$ satisfy condition (2). When both conditions hold, it
follows that $K(s)\approx H(\mu)$. Intuitively, this works because $H$
measures the length of an encoding that’s designed to be shortest _on
expectation_ and, by the law of large numbers, empirical averages converge to
expectations. For analyses of the rate of convergence between $H$ and $K$, see
Austern and Maleki [7].

Depending on which entropy is considered, the second law of thermodynamics may
be formulated to say that a decrease in entropy is strictly forbidden, or
merely unlikely. The Poincaré recurrence theorem says that ergodic dynamical
systems must visit every state $s\in\mathcal{S}$ infinitely often. Thus, $B$
and $K$ will eventually be high, and then low again. In contrast, for many of
the same systems, $H$ can never decrease [5, §4.4]. To reconcile this
difference, recall that Shannon entropy concerns a probability distribution
$\mu$, and increases as $\mu$ becomes more uniform. Typical draws from $\mu$
have Boltzmann and algorithmic entropies close to $H(\mu)$. However, on rare
occasions, a distribution of high (Shannon) entropy produces a lucky draw of
low (Boltzmann or algorithmic) entropy.

Aside from these overwhelmingly unlikely draws, we’ve seen that in realistic
physical settings, the entropies approximate one another. Therefore, we’re
free to choose whichever we find convenient, with the assurance that our
results will transfer. In this article, we choose the Shannon entropy (and the
KL divergence that generalizes it; see Section III.2), because it offers the
conveniences of probability theory. Nonetheless, whenever we formally discuss
collections of random variables, the reader is encouraged to informally think
of algorithmically typical draws from their distributions. In this manner, we
can make sense of such modeling choices as random initial conditions, despite
the observable Universe only having one initial state.

To mimic a symmetry of classical mechanics, our model Universe should apply a
deterministic and reversible state transition at each time step. This amounts
to a fixed permutation on $\mathcal{S}$. Clearly, the Shannon entropy is
invariant to such permutations. Similarly, the algorithmic entropy changes
extremely slowly under repeated permutations, since any future state can be
computed as a function of the initial state, the permutation, and the number
of repetitions. _Substantial_ changes in entropy only arise by restricting
attention to an incomplete view of $\mathcal{S}$, allowing entropy to pop in
or out of our view. For example, views may be limited in any of the following:

  1. 1.

Numerical precision. The entropy would then be insensitive to microscopic
variations, until they are expanded by _chaotic_ dynamics.

  2. 2.

Spatial extent. Interactions between systems may induce correlations, so that
each individual system’s entropy increases even if the aggregate entropy does
not.

  3. 3.

Computational resources. If repetitions of the dynamics are slow to compute,
they may increase a system’s _time-bounded_ algorithmic entropy, defined by
restricting Equation 3 to programs $p$ that terminate within a specified time
limit.

We mention the third mechanism only for completeness, leaving its rigorous
study to future work. The second mechanism is related to locality, and will be
quantified in Equation 36. However, we focus our modeling efforts on the first
mechanism, in which chaos draws out the entropy hidden within microscopic
variations, gradually pushing it into the macroscopic world. To ensure a
limitless supply of hidden entropy, we now extend the state space to a
continuum.

###  I.2 Continuous-State Entropy

In classical Hamiltonian mechanics, the discrete state space $\mathcal{S}$ is
replaced by a continuous phase space. For example, a system of $n$ free
particles has its state described by a point in $\mathbb{R}^{6n}$,
representing their 3D positions and momenta. Given a probability measure $\mu$
over phase space, the Shannon (or Gibbs) differential entropy is defined by
replacing the sum in Equation 1 by an integral. A defining characteristic of
Hamiltonian evolution is Liouville’s theorem: it states that phase volumes,
and hence the differential entropy, do not change with time [8].

On the other hand, the continuous setting is conducive to views with limited
numerical precision. For concreteness, fix a resolution $\varepsilon>0$. To
each point in $\mathbb{R}^{6n}$, apply the coordinate-wise discretization
$x\mapsto\lfloor\frac{x}{\varepsilon}\rfloor\varepsilon$. It partitions the
phase space into axis-aligned hypercubes of width $\varepsilon$, identified
with elements of a discretized state space
$\mathcal{S}:=(\varepsilon\mathbb{Z})^{6n}$. Since $\mathcal{S}$ is countable,
all of the discrete-state entropies $H,B,K$ apply. Despite Liouville’s
theorem, the discretized entropies can be altered by changing the shape of a
phase volume, so that it occupies different numbers of $\varepsilon$-cubes.

Note that the computation of $B$ now involves two levels of partitioning: (1)
the _fine partition_ of continuous phase space into its discretized version,
and (2) the _coarse partition_ of discretized phase space into Boltzmann
macrostates. For the remainder of this article, the word microscopic refers to
the full continuous description, whereas macroscopic refers to the
discretization into fine macrostates. Although the latter are considered
_microstates_ in the Boltzmann picture, there will be no ambiguity as we’ve
chosen to focus on the Shannon entropy. In light of the correspondence between
$B$ and $H$ in Section I.1, Boltzmann’s coarse macrostates are replaced with
probability distributions over fine macrostates.

For certain volume-preserving dynamical systems, we’ll find initial conditions
that ensure the discretized Shannon entropy never decreases. The idea is to
employ a particularly convenient chaotic map.

###  I.3 The Baker’s Map and the Shift Map

We consider a discrete-time map that shares many properties with Hamiltonian
mechanics, but is more tractable. It substitutes the unit square
$\mathcal{S}_{\mathrm{baker}}:=[0,1)^{2}$ for phase space. Fix
$m\in\mathbb{N}$. The $m$-fold baker’s map
$\beta:\mathcal{S}_{\mathrm{baker}}\rightarrow\mathcal{S}_{\mathrm{baker}}$
acts on the square by stretching its $x$-axis while squeezing its $y$-axis,
each by a factor of $m$, then cutting and re-arranging to get back the unit
square:

$\beta(x,y)=\left(mx-\lfloor mx\rfloor,\;\frac{y+\lfloor
mx\rfloor}{m}\right).$

The combination of stretching and squeezing makes $\beta$ volume-preserving
and chaotic. It also satisfies a CPT-like symmetry, since

$\beta^{-1}=\rho\circ\beta\circ\rho,$ (4)

where $\rho(x,y):=(y,x)$ is a reflection about the line $y=x$. Since $\beta$
is invertible, any (possibly random) initial state
$C_{0}=(X_{0},Y_{0})\in\mathcal{S}_{\mathrm{baker}}$ determines the state at
all times $t\in\mathbb{Z}$ by iterating

$C_{t+1}=\beta(C_{t}),$

forward and backward. Given the distribution of $C_{0}$ and the resolution
$\varepsilon$, we are interested in the Shannon entropy of $C_{t}$’s
discretization at various $t$. In light of the symmetry in Equation 4, we
cannot preferentially guarantee higher entropy at higher $t$.

Instead, provided that the initial distribution is absolutely continuous, the
entropy tends toward a maximum in a symmetric fashion, as
$t\rightarrow\pm\infty$. Some intuition is offered by the special case in
which $C_{0}$ is uniformly distributed on a union of axis-aligned squares,
whose vertex coordinates are multiples of $\delta$, with each of
$\varepsilon,\delta$ being integer powers of $\frac{1}{m}$. The reader may
verify that the entropy is non-decreasing for
$|t|\geq\log_{m}\frac{1}{\varepsilon}-\log_{m}\frac{1}{\delta}$, and is
maximal at $|t|\geq\log_{m}\frac{1}{\varepsilon}+\log_{m}\frac{1}{\delta}$. In
a much more general setting, Theorem 4 will imply an asymptotic version of the
second law of thermodynamics as $t\rightarrow\pm\infty$.

$\beta$ is a prototypical example of a chaotic map: it’s physically realizable
[9] and guides our geometric intuition. It also has a convenient symbolic
representation. To that end, let $\mathbb{Z}_{m}:=\\{0,1,\ldots,m-1\\}$. The
$m$-symbol shift map
$\sigma:\mathcal{S}_{\mathrm{shift}}\rightarrow\mathcal{S}_{\mathrm{shift}}$
is defined on the set of bi-infinite sequences
$\mathcal{S}_{\mathrm{shift}}:=(\mathbb{Z}_{m})^{\mathbb{Z}}$, by simply
shifting the entire sequence $r\in\mathcal{S}_{\mathrm{shift}}$ over by one
position:

$\sigma(r)_{i}:=r_{i+1}.$ (5)

Despite their different appearances, the maps $\beta$ and $\sigma$ are
essentially equivalent, in the sense that the correspondence
$\Psi:\mathcal{S}_{\mathrm{shift}}\rightarrow\mathcal{S}_{\mathrm{baker}}$,
defined by

$\Psi(r):=\left(\sum_{i=1}^{\infty}r_{i-1}m^{-i}\\!\\!\\!\\!\mod
1,\;\sum_{i=1}^{\infty}r_{-i}m^{-i}\\!\\!\\!\\!\mod 1\right),$ (6)

is _almost_ bijective. $\Psi$ interprets the sequence’s two halves $(r_{\geq
0},\,r_{<0})$ as representations, in the base-$m$ positional number system, of
the $(x,y)$ coordinates of a point in $\mathcal{S}_{\mathrm{baker}}$. The only
trouble is that points of $\mathcal{S}_{\mathrm{baker}}$ with $m$-adic
rational coordinates have multiple preimages, due to non-unique
representations such as $0.5=0.4\overline{9}$. Fortunately, these points
collectively have measure zero, so we would not expect to encounter them on a
random draw. On their complement, one can check that the dynamics are
equivalent:

$(\beta\circ\Psi)(r)=(\Psi\circ\sigma)(r).$

In summary, the baker’s map $\beta$ serves as a convenient substitute for
classical Hamiltonian dynamics, sharing key features such as determinism,
reversibility, volume-preservation, chaos, and the second law of
thermodynamics. Motivated by the correspondence $\Psi$, we will base our
models on the shift map $\sigma$. If the initial condition is suitably
randomized, each term in the sequence $r\in\mathcal{S}_{\mathrm{shift}}$ acts
as a random seed, which can be used to emulate stochastic transitions. We will
design macroscopic transitions that depend on only one term, say $r_{0}$.
$\sigma$ shifts these terms like a conveyor belt, providing a fresh $r_{0}$ at
every time step.

As a result, our models’ stochastic macroscopic descriptions are _exactly_
observationally equivalent to their deterministic microscopic descriptions. We
prove it formally in Theorem 3. This appears to be not quite true of the real
world, where microscopic theories have additional predictive power.
Nonetheless, Werndl [10] argues that such equivalences do hold, either exactly
or approximately, in many settings of practical interest.

###  I.4 The Psychological Arrow of Time

Had we only wanted a deterministic reversible model with a second law of
thermodynamics, then either of the maps $\beta$ or $\sigma$, suitably
initialized, would have sufficed. However, the second law is insufficient for
explaining the psychological arrow of time. To begin with, it cannot explain
the time-reversal asymmetry of memories.

To see why, we must understand what memories are. Intuitively, they are
_records_ of past events. They contain information about the event in
question, but that’s not all: while we can also collect information that’s
predictive of _future_ events, we would not call them records. The distinction
is clearest with events that depend on highly chaotic interactions, making
them hard to predict. The weather is a good example: our records span much of
human history (and prehistory, if we include geological evidence of climate
variations). In contrast to how much we know about past weather, we cannot
reliably forecast even one week into the future. To give another example, all
manner of unpredictable scenes can be recorded in a photograph, but only after
they occur. In this sense, memories need not even be associated with living
beings; rather, their defining feature is the ability to stably capture the
information content of an event, no matter how ephemeral.

Just as memories pertain to the past, counterfactuals pertain to the future.
Whereas the existence of records suggests that the past is set in stone, the
future appears malleable: we imagine various counterfactual possibilities, and
plan our lives accordingly. Outside the purview of fundamental physics, nearly
all academic disciplines take the arrow of time for granted. This is reflected
in their mathematical tools: in particular, Pearl’s structural causal models
[11] can model both memories and counterfactuals.

Recall that a directed graph is a set of vertices, along with a set of edges
(arrows) that point from one vertex to another. A causal graph is a directed
graph with no cycles, whose vertices correspond to random variables. Its edges
specify causal relationships, pointing from cause to effect. More precisely,
they encode two kinds of information [12]:

  1. 1.

A set of structural independence constraints that the random variables must
satisfy.

  2. 2.

Rules for modifying the variables’ joint distribution under structural
interventions.

A graph’s structural independence constraints are formally specified by
Pearl’s $d$-separation criterion [11, §1.2]. A joint probability distribution
over a causal graph’s random variables is said to be Markov, relative to the
given graph, if it satisfies these constraints.

A structural causal model is a causal graph equipped with conditional
probability distributions, one for each variable as a function of its parents.
These distributions, together with the graph’s structural independence
constraints, fully determine the variables’ joint probability distribution
[11, §1.2]. In addition to this joint distribution, a causal model also
identifies alternative distributions that would arise, if external influences
were to intervene on some of its variables.

For an illustrative example, imagine a collection of physical systems that are
usually isolated from one another, but occasionally experience pairwise
interactions. Let’s zoom in on two such systems $A$ and $B$, whose sole
interaction within the time interval $[0,3]$ occurs at $t=1.5$. Their causal
graph is as follows:

$\displaystyle\cdots\rightarrow A_{0}\rightarrow A_{1}$
$\displaystyle\rightarrow A_{2}\rightarrow A_{3}\rightarrow\cdots$
$\displaystyle\searrow$ $\displaystyle\cdots\rightarrow B_{0}\rightarrow
B_{1}$ $\displaystyle\rightarrow B_{2}\rightarrow B_{3}\rightarrow\cdots$

$A_{t}$ is a random variable representing the state of system $A$ at time $t$,
and likewise for $B_{t}$. At non-interaction times, the two systems are
modeled as independent Markov chains. During the interaction, $A_{1}$ is said
to _causally influence_ $B_{2}$. Two interpretations of this graph offer
different insights: either (1) we focus on $A$, a system whose data is
_recorded_ by the memory $B$; or (2) we focus on $B$, a system whose dynamics
are _intervened_ upon by the causal actor $A$. Let’s discuss each
interpretation in turn.

####  I.4.1 Memories

As a consequence of the $d$-separation criterion, any pair of random variables
without a common ancestor (i.e., a common cause) must be independent. Thus,
dependent random variables must carry information about some common cause in
the past. In our example, $A_{t}$ and $B_{u}$ share the common ancestor
$A_{1}$, for $t\geq 1$ and $u>1$. Earlier states, such $A_{0}$ and $B_{0}$,
can only be dependent if they share a common ancestor in the more distant past
(implied by the ellipsis).

Motivated by our observation that memories can capture ephemeral events, let’s
imagine that $A$ is a rapidly mixing system, so that the sequence
$(A_{t})_{t\in\mathbb{Z}}$ is i.i.d. All directed edges (arrows) in the first
row are effectively erased, leaving $A_{1}$ as the only possible common
ancestor. By the $d$-separation criterion, $A_{t}$ and $B_{u}$ can only be
dependent if $t=1<u$. Thus, memories are indeed of the past.

Now let’s drop the i.i.d. assumption. The dependence between $A_{t}$ and
$B_{u}$ can be quantified by their mutual information $I(A_{t};B_{u})$ (see
Definition 3). The data processing inequality [5, §2.8] implies
$I(A_{t^{\prime}};B_{u^{\prime}})\geq I(A_{t};B_{u})$ for $t^{\prime}\leq t$
and $u^{\prime}\leq u$, provided that no interactions occur between the times
involved. In other words, information loss is unrestricted, but information
_gain_ requires interaction. Thus, all dependences can be traced backward
through time to some past interaction (or to dependent initial conditions).

The $d$-separation criterion and the data processing inequality, much like the
second law of thermodynamics, impose asymmetries with respect to time
reversal. To see how they work in concert together, let’s decompose the
systems’ joint entropy (dropping the subscripts for convenience):

$H(A,\,B)=H(A)+H(B)-I(A;\,B).$ (7)

The composite system $(A,B)$ is closed throughout the time interval $[0,3]$,
so the second law implies that $H(A,B)$ is non-decreasing. In general, when
$A$ and $B$ interact, their joint entropy may arbitrarily redistribute among
the three right-hand terms. However, when $A$ and $B$ are closed off from each
other, the second law applies to each system individually, so that $H(A)$ and
$H(B)$ are also non-decreasing.

Now we see why the second law on its own is insufficient: it permits an
increase in $I(A;B)$, provided that either $H(A)$ or $H(B)$ simultaneously
undergo an equal or greater increase. In other words, the second law does not
rule out spontaneous information gain between isolated systems. Instead, the
required time-reversal asymmetry is given by the data processing inequality.
Together with the second law, it ensures that all three right-hand
contributions in Equation 7 are non-decreasing.

An interesting consequence is that when $A$ and $B$ are closed off from each
other, an increase in any one of the right-hand terms cannot be compensated
for by a decrease in another; therefore, it necessarily induces an equal or
greater increase in $H(A,B)$. This is an extension of Landauer’s principle,
detailing the irrevocable thermodynamic cost of erasing information; see
Section VI.2.

####  I.4.2 Counterfactuals

Let’s examine the relationship between cause and effect. We say that rain
causes wet grass, whereas wet grass does not cause rain. The inelastic
collisions between rain drops and grass increase entropy, rendering them
thermodynamically irreversible. Note that while a _typical_ configuration of
wet grass does not evolve into rain, our wet grass is decidedly _not_ typical,
because evolving it backward reveals a past in which it did rain. The forward
evolution is distinguished in that it can be predicted by treating the
configuration _as if_ it were typical, using homogeneous transition
probabilities. In contrast, the backward evolution seemingly conspires to
extract the grass’s moisture and blast it up into the sky. The emergence of
homogeneous forward dynamics will be a key feature of our models.

However, our causal intuitions are not confined to processes that are
intrinsically irreversible. For example, consider a frictionless pendulum with
a period of two seconds. Since its trajectory is periodic, any point on the
trajectory causes all others; nonetheless, we prefer to think of earlier
states as causing later states. This makes sense in the context of exogenous
influences: if we place the pendulum to the left of its pivot, then we would
find it on the right a second later, whereas the placement has no retroactive
effect a second prior.

More generally, we imagine being able to perform an intervention on any random
variable of a causal model, assigning it some value and detaching it from its
parents in the graph. Effects then propagate to the variable’s descendants,
yielding a counterfactual outcome. This counterfactual presents an alternative
trajectory for the Universe, in apparent violation of determinism. Moreover,
since the edges are directed forward in time, the intervention changes its
future while holding its past fixed, in apparent violation of CPT symmetry.
Despite violating fundamental physics principles, counterfactual reasoning is
ubiquitous in real-life applications [11].

At this point, we remark that our investigation inevitably touches upon
philosophical themes; nonetheless, all of our questions are scientifically
motivated. For instance, while we do not concern ourselves with the question
of whether free will is “real”, we must reckon with the empirical fact that
intelligent life displays the behaviors associated with free will. These
include reasoning in terms of counterfactuals, in order to plan for the future
(but not for the past). How can physics predict this phenomenon?

Consider that practical models are necessarily incomplete. Returning to our
casual model above, rather than draw it in full, we might only model the
system $B$:

$\displaystyle\cdots\rightarrow B_{0}\rightarrow B_{1}$
$\displaystyle\rightarrow B_{2}\rightarrow B_{3}\rightarrow\cdots$

Viewed in isolation, $B$ is a Markov chain, following its own dynamics in the
absence of external influence. For example, $B$ might be our frictionless
pendulum. The interaction, then, appears as an exogenous intervention on
$B_{2}$, modifying its $B_{1}$-conditioned probability distribution. The
unmodeled variable $A_{1}$ encodes the nature of the intervention. As we saw
when discussing memory, information about $A_{1}$ only appears in $B$’s
future, explaining why counterfactuals do not alter the past. If some
intelligent agent has partial or total control of $A_{1}$’s value, then it
makes sense for the agent to consider each counterfactual possibility,
exercising its “will” to choose $A_{1}$ according to the desired effect on
$B$.

In general, the behavior of agents is determined by Darwinian evolution. In
Section VI.5, we propose an explanation for evolution’s arrow of time; thus,
agents seek to optimize their future. If an agent possesses sufficient
cognitive resources, it may employ a model-based planning algorithm [13]. From
the algorithm’s point of view, choices are made “freely”, in the following
sense: the algorithm can simulate the counterfactual outcomes of a variety of
different choices, and realize whichever one it prefers. This is true despite
the algorithm having a mathematically determined (or possibly randomized)
output.

This discussion leaves us in an awkward position: causal models beautifully
describe the cognitive world of cause, effect, memory, and planning, i.e., the
psychological arrow of time; however, they seem quite far removed from
fundamental physics, with its determinism and CPT symmetry. In this article,
we extend the shift map, in two stages, toward the ultimate aim of deriving
causality as an emergent structure. The result is a type of cellular automaton
that, even more so than the baker’s and shift maps, exhibits key features of
classical mechanics.

By studying these automata, we find that the fundamental time-reversal
asymmetry takes one of two forms, depending on whether we take a microscopic
or macroscopic view. At the microscopic level, symmetry is broken by a Past
Hypothesis, consisting of an absolutely continuous initial condition. At the
macroscopic level, this corresponds to dynamics that are homogeneous in space
and time, and Markov relative to a causal graph who edges are timelike and
future-directed. As a consequence, we can prove generalizations of the second
law of thermodynamics. These lead to insights on a variety of topics related
to the arrow of time.

###  I.5 Article Outline

Section II reviews some literature that provides context for our
contributions. Then, Section III sets notational conventions. It also
introduces useful lemmas from information theory [5], reformulated to suit the
analysis of general Markovian dynamics. Our core mathematical contributions
are split into two stages, developed in Sections IV and V respectively.

Section IV presents the first stage, extending the shift map in such a way as
to emulate arbitrary time-homogeneous Markov chains. We discuss the extent to
which Markov chains exhibit or violate time-reversal symmetry, and prove a
precise correspondence between three presentations of the dynamics. Two of
these are stochastic, corresponding to macroscopic views of the third,
deterministic presentation. We apply this theory to generalize the Past
Hypothesis, and then ask what happens at negative times, before the initial
condition.

Section V presents the second stage, enriching the Markov chains with spatial
structure that turns them into stochastic partitioned cellular automata
(SPCAs). The local dynamics of an SPCA makes it possible to discuss multiple
systems, each having their own entropy, and correlations between them. We find
that SPCAs are Markov relative to a timelike future-directed causal graph.
Moreover, they satisfy the Resource and Memory Laws, which correspond to the
second law of thermodynamics and the data processing inequality, respectively.

Section VI explores applications of our work to a variety of topics, in and
out of physics. In some cases, we obtain novel extensions of existing theory;
in others, we simply demonstrate the increased clarity and precision offered
by SPCAs and their information-theoretic dynamics.

Finally, Section VII concludes with some suggestions for future work.

##  II Related Works

The arrow of time is too broad a topic to comprehensively review in a few
pages. We make our best effort to emphasize the most pertinent literature that
provides context for this article.

###  II.1 Literature on Dynamical Systems

For simplicity’s sake, we focus on the discrete-time (but continuous-state)
setting, to which Devaney [14] provides an accessible introduction. In
practice, we cannot observe a system’s state precisely, so let’s imagine we
instead observe a discrete-valued function of the state; i.e., the set of
possible observations is countable. Then, for all practical purposes, a state
may be identified with its trajectory’s bi-infinite sequence of past, present,
and future observations. The shift map describes the system’s dynamics in this
sequence representation, the study of which is called symbolic dynamics [15].

Despite the system’s determinism, if its initial state is randomly sampled,
the corresponding sequence of observations becomes a discrete-state stochastic
process. Werndl [10] examines deterministic and stochastic systems that are
_observationally equivalent_ , in the sense that the former’s observations are
distributed like the latter. Under reasonable hypotheses, she proves that
Bernoulli dynamical systems are approximately observationally equivalent, at
every resolution, to irreducible and aperiodic Markov chains. In Theorem 3, we
prove exact observational equivalence, between general Markov chains and an
extension of the shift map. Under more general initial conditions, Theorem 4
turns this into an approximate equivalence. We also relate properties between
the two systems, showing how measure-preservation and time-reversal (on the
deterministic side) map to stationarity and duality (on the stochastic side).

The literature includes several dynamical systems modeling the second law of
thermodynamics. Schack and Caves [16] interleave a chaotic system’s dynamics
with random measure-preserving perturbations. Unfortunately, their
perturbations sacrifice determinism and CPT symmetry. For some simple
dynamical systems, Nicolis and Nicolis [17] identify suitable initial
conditions and coarse-grainings that ensure the Markov property. Pitowsky [9]
also studies generalized shift maps, but for the purposes of modeling
deterministic Turing machines. More recently, researchers such as Parrondo
_et al._ [18] are looking more closely at the thermodynamics of correlated
systems.

Perhaps the closest existing model to ours is the multibaker chain of Gaspard
[19]. It employs the baker’s map to gradually extract a source of randomness
that’s set at initialization. By doing so, it deterministically and reversibly
emulates a random walk on $\mathbb{Z}$, i.e., a discrete diffusion process.
Our first-stage model in Section IV generalizes the multibaker chain,
emulating not only random walks, but arbitrary Markov chains.

Continuous-state analogues of the entropy rate [5, §4.2] are given by the
Kolmogorov-Sinai entropy [20] and the topological entropy [21]. These
quantities measure the rate at which a system’s trajectories acquire new
information, as a result of expanding once-hidden microscopic variations. For
the $m$-symbol shift map, they equal $\log m$. Latora and Baranger [22]
describe some circumstances in which the Kolmogorov-Sinai entropy approximates
the rate of entropy growth in dynamical systems.

Some concepts from the computer science literature are helpful. Bennett [2]
reviews connections between logical and physical descriptions of entropy and
reversibility. We draw upon the design of reversible and partitioned cellular
automata (PCAs) [23, 24], essentially fusing them with causal models to create
SPCAs. In the context of reversible computing, Frank [25] anticipates
thermodynamic consequences for the data processing inequality.

Subtle issues come up when comparing Gibbs and Boltzmann entropies, largely
revolving around ambiguous coarse-grainings and subjective probabilities [26].
Algorithmic entropy provides a firm theoretical grounding that minimizes these
ambiguities. Its foundations date back to Occam’s razor, and it appears in
some ambitious accounts of inductive inference and artificial intelligence
[27, 28, 29]. Zurek [30] introduces the algorithmic entropy to physics.
Wallace [31] describes two-part codes in depth, and adds some speculations on
the arrow of time. Last, but not least, Li and Vitányi [6] provide the
standard reference on algorithmic information theory, surveying applications
to physics in their final chapter.

###  II.2 Literature on the Psychological Arrow of Time

The psychological arrow of time is intimately tied to the sense that causes
precede effects. Historically, before we had a mathematical language in which
to discuss them, causal concepts were subject to misunderstanding,
controversy, and even outright dismissal in the scientific community. That
changed with the introduction of Pearl’s structural causal models, a powerful
methodology for causal inference, applicable to a wide range of disciplines
[11].

In this article, we understand causality exactly as Pearl does. In particular,
we discuss counterfactuals using his structural semantics; though, see Pearl
[11, §7.4.1] for a comparison against Lewis’ closest-world semantics, and
Loewer [32] for semantics based on probabilistic conditioning. One advantage
of the structural account is that, because it need not alter the past, it
deals more cleanly with implausible (yet still useful) counterfactuals.

Ties between Pearlean causality and dynamical systems are sparser in the
literature. The numerical study by Paluš  _et al._ [33] presents insights on
some causality detection methods.

Janzing  _et al._ [34] link causality to the algorithmic independence of
initial conditions and dynamics. In the deterministic setting, this approach
predicts the algorithmic entropy to grow unrealistically slowly: the length of
a later state’s description, in terms of only the starting state, dynamics,
and time elapsed, grows at most logarithmically in the time elapsed. On the
other hand, their result makes a lot more sense in the context of random
dynamics, where the description length can grow linearly in the time elapsed.
Using Definition 7, we offer the same conclusions in probabilistic, rather
than algorithmic, terms.

In a deeply thought-provoking treatise, Albert [35] elucidates the
philosophical issues in reconciling statistical physics with the psychological
arrow of time. He argues, alongside Loewer [32], that the arrow of time
emerges from the _Mentaculus_. This is a probability distribution over
Universes, defined by extrapolating a _Past Hypothesis_ in which the Big Bang
is sampled uniformly from a low-entropy macrostate. Our article supports this
conclusion with rigorous theorems. We also extend the Past Hypothesis to non-
uniform continuous distributions, yielding a generalized Mentaculus in
Equations 24 and 25.

In the search for rigorous explanations, a common line of attack takes the
second law of thermodynamics as given, and focuses on what appears to be a
basic component of the psychological arrow: memory. After proposing a
definition for memory, some authors proceed to argue that its operation must
align with the second law’s arrow of time. In light of our observation
following Equation 7, that the second law alone is insufficient, this approach
is unlikely to succeed. Even so, it’s helpful to examine some of these
attempts with care.

Wolpert [36] distinguishes between two types of memory systems: _computer-
type_ and _photograph-type_. Both types aim to possess information at some
time $t_{r}$, about an event occurring at some other time $t_{e}$. A computer-
type memory has access to so much state information at $t_{r}$, that it can
deduce the event at $t_{e}$ by directly simulating the dynamical evolution of
the Universe. Such “memories” have no arrow of time, with both $t_{e}<t_{r}$
and $t_{e}>t_{r}$ being admissible, but they may require unrealistic levels of
precision. As such, they are more like weather predictions rather than
reliable records.

Our notion of a memory aligns better with Wolpert’s photograph-type which,
while less demanding in terms of precision and computation, requires
initialization. Wolpert argues that real-world initialization procedures
result in a net increase in entropy, forcing the memory to align with the
thermodynamic arrow. Unfortunately, this is begging the question: the
thermodynamic arrow makes it so nearly _all_ real-world processes increase
entropy. If anything, the many-to-one mapping that defines an initialization
seems predisposed to _lose_ entropy, which can only be done in reverse; in
order to initialize forward, entropy must be released into the environment
just to stay in accordance with the second law. A perfectly efficient
initialization procedure would be reversible, with the entropy gains and
losses exactly canceling [2].

Mlodinow and Brun [37] argue that even a reversibly implemented memory can
only function in the direction of the thermodynamic arrow. Their thought
experiment consists of a pair of connected chambers containing elastic
particles, and a counter that tracks the net flow of particles from one
chamber to the other. Instead of treating initialization explicitly, the
counter is assumed to have a known value at $t_{e}$. Thus, reading the
counter’s value at $t_{r}$ is enough to infer the net flow of particles during
the time interval between $t_{e}$ and $t_{r}$, acting as a memory of this
interval. In order for this memory to be useful, it should be capable of
recording more than one possible answer, which the authors ensure by applying
a small random perturbation to the particles at $t_{e}$. This directs the
thermodynamic arrow of time away from $t_{e}$, presumably toward $t_{r}$, thus
aligning the two arrows.

Their argument has a few loose ends. Firstly, it doesn’t apply if the
particles are at thermodynamic equilibrium, as no thermodynamic arrow would be
discernible from their evolution. Secondly, it’s unclear how one arrives at
knowledge of the counter’s value at $t_{e}$. And finally, a random
perturbation at $t_{e}$ cannot be a realistic model of uncertainty: it would
direct the thermodynamic arrow away from $t_{e}$ in _both_ directions,
violating the Universe’s low-entropy initial condition. While the argument
captures a valid intuition, that memories should be robust to counterfactual
alternatives, such a principle demands careful justification.

Rovelli [38] presents a physically plausible model consisting of two near-
equilibrium systems with long thermalization times: a cooler memory and a
hotter environment. In a follow-up paper, Rovelli [39] views the environment
as an agent, and its random interactions with the memory as choices. Thus, he
concludes that the exercise of free will increases entropy, and must therefore
align with the thermodynamic arrow. His account of free will in terms of
randomness disagrees with our account in Section I.4.2, where we equated free
will with counterfactual-based planning. Our account is agnostic to whether
the output is deterministic or randomized; thus, it also stands in contrast to
accounts of free will that require quantum or Knightian forms of uncertainty,
including the freebit picture of Aaronson [40].

On the other hand, since causal models are free to invoke Markovian randomness
(e.g., sampling independently of the past), we also question
_superdeterminism_ of the sort suggested by ’t Hooft [41] in his cellular
automaton interpretation of quantum mechanics. Superdeterminism proposes that
our actions must somehow conspire to meet certain constraints on future
outcomes. The trouble with conspiracies is that one must make them
sufficiently powerful to support their proponent theories, while retaining the
appearance of “free” Markovian dynamics [42].

In unfinished work independent of our own, Carroll [43] shares our goal of
deriving Pearlean causality from a suitable Past Hypothesis. While it’s too
early for a technical comparison, we disagree with one of his premises.
Carroll writes: _“Increasing entropy is the sole reason for the asymmetry
between past and future states in the macroscopic world.”_ In Section I.4.1,
we saw that increasing entropy does _not_ imply the data processing
inequality. On the other hand, we will find that all of these asymmetries
follow from a suitable causal model, which in turn emerges from a suitable
pairing of dynamics with a Past Hypothesis.

While entropy’s monotonicity makes it convenient to study, Bennett [44] (see
also Li and Vitányi [6, §7.7]) argues that since both low-entropy (e.g., all
zeros) and high-entropy (e.g., uniformly random) strings can be uninteresting,
another quantity is needed to capture the “interestingness” of life’s
structures, such as its DNA. For Bennett, the interesting strings are those
whose most plausible explanations involve long and difficult computations,
such as Darwinian evolution on geological scales. Thus, he defines an object’s
_logical depth_ to be the time it takes to execute its shortest description.
Stated differently, a logically deep object is one with low algorithmic
entropy, but high time-bounded algorithmic entropy.

Aaronson  _et al._ [45] observe a variety of systems in which logical depth
rises during early stages of dynamical evolution, and then falls during the
approach to thermodynamic equilibrium. While their evidence is largely
empirical, we can understand this phenomenon in terms of Bennett’s slow growth
law [44]. Under Markovian dynamics, the law states that logical depth cannot
(with substantial probability) rise quickly. If the system begins in a
logically shallow state, then high logical depth can only arise from a long,
slow computation 555This argument parallels Section I.4.1 where, instead of
the slow-growth law for logical depth, the data processing inequality acted as
a “no-growth law” for mutual information. There, we concluded that all
correlations can be traced back in time to a common cause.. Thus, logically
deep objects cannot exist too early in the system’s lifetime. They also cannot
exist too late, when the system settles in a very shallow (e.g., uniform)
equilibrium distribution. It follows that logically deep objects, if they
appear at all, must form gradually at intermediate times.

Quantum entanglement is stronger than classical correlation, in that it can
produce a composite system with less entropy than either of its parts. For
example, it’s possible to produce local entropy by measuring a quantum system,
while keeping the global entropy at zero; a global operation can then erase
all traces of this measurement and its entropy. Maccone [3] argues that
whenever entropy decreases for some local observer (let’s name her Alice), any
trace or memory must be erased so that she cannot recall the decrease. This
argument is imprecise: while it’s true that Alice can only retain as much
information as the final entropy of her system, a reduction in her entropy
need not necessarily eliminate evidence that the entropy used to be higher.
Indeed, rather than preserve a high-entropy measurement in its entirety, Alice
can simply summarize its entropy, perhaps rounded to a few significant
figures. A summary has less entropy than the full measurement, so it can
survive a reduction in entropy. If she later measures a lower entropy, she
would notice the decrease.

Finally, Heinrich  _et al._ [46] produce simulations as evidence that natural
selection favors agents with knowledge of the past, over those with knowledge
of the future. However, their arguments do not consider non-living memories
(e.g., geological records), nor alternative scenarios in which knowledge of
the future may be more advantageous. They also present no plausible mechanism
for natural selection between forward-thinking and backward-thinking
organisms.

We should emphasize that, despite calling it the psychological arrow, the
subject of this article is fundamentally physical (or more abstractly,
computational), applying equally well to non-living records. Our physics-first
approach has the advantage of applying not only to certain species of animals,
but to _all possible brains_ , wherever the laws of physics hold. That being
said, we do not treat the animal psychology or neuroscience of time
perception. Being ill-positioned to do these literatures justice, we only
point to the review of Grondin [47] on the perception of short time intervals,
and to the study by Gauthier  _et al._ [48] on perception of the more distant
past and future.

##  III Technical Preliminaries

###  III.1 Notational Conventions

Throughout this article, $\mathbb{R}^{+}$ denotes the non-negative real
numbers, $\mathbb{Z}^{+},\mathbb{Z}^{-}$ the non-negative and non-positive
integers, $\mathbb{N}:=\mathbb{Z}^{+}\setminus\\{0\\}$ the natural numbers,
and $\mathbb{Z}_{m}:=\\{0,1,\ldots,m-1\\}$ denotes the first $m$ elements of
$\mathbb{Z}^{+}$. Let $\oplus$ denote the bitwise XOR on $\mathbb{Z}^{+}$,
e.g., $5\oplus 3=6$.

Uppercase Latin letters $A,B,C$ denote generic sets or random variables, while
lowercase letters denote elements of the corresponding sets $a\in A,\,b\in B$,
or realizations of random variables. $2^{A}$ denotes $A$’s power set,
consisting of all subsets of $A$. Script letters are used for
$\sigma$-algebras $\mathcal{F},\mathcal{G}$, as well as for three important
sets that are treated as fixed in most contexts: the state space $\mathcal{S}$
and the discrete geometry $(\mathcal{X},\mathcal{T})$. The Greek letters
$\mu,\nu,\pi,\Gamma$ denote measures.

$B^{A}$ denotes the set of functions from a domain $A$ to a codomain $B$.
Functions are also called indexed collections or, when $A$ is $\mathbb{N}$ or
$\mathbb{Z}$, sequences. The notation $f:A\rightarrow B$ is synonymous with
$f\in B^{A}$, and means that each $a\in A$ maps to $f(a)=f_{a}\in B$. The
image of a set $A^{\prime}\subset A$ under $f$ is $f(A^{\prime}):=\\{f(a):a\in
A^{\prime}\\}$. $\mathrm{Bij}(A)\subset A^{A}$ denotes the set of bijections
from $A$ onto itself; these functions are synonymously called bijective,
invertible, or reversible. The notation $x\mapsto f(x)$ is synonymous with $f$
itself, and is useful for quickly referring to “anonymous” functions without
naming them. Given either $f:A\rightarrow B$ or
$f:A\setminus\\{a\\}\rightarrow B$, the substitution $f_{a\leftarrow
b}:A\rightarrow B$ equals $f$ everywhere except at $a$, where it equals $b$
instead. That is,

$\displaystyle f_{a\leftarrow b}(a^{\prime})$
$\displaystyle:=\begin{cases}b&\text{if }a^{\prime}=a,\\\
f(a^{\prime})&\text{if }a^{\prime}\neq a.\end{cases}$

Some intuitive shorthands are used: for instance, $f_{A^{\prime}}$ denotes the
restriction of $f$ on the set $A^{\prime}\subset A$. If $A$ is ordered,
$f_{\leq a}$ is shorthand for $f_{\\{a^{\prime}\in A:\;a^{\prime}\leq a\\}}$.
If $f$ takes multiple arguments, we allow partial application from left to
right, so that, e.g., $((f_{a})_{b})_{c}:=(f_{a,b})_{c}:=f_{a,b,c}$.

We want to make correct use of measure theory without overburdering ourselves
with notation and unimportant details. We can usually avoid mentioning
$\sigma$-algebras by assuming some defaults: for a countable set $A$, take it
to be $2^{A}$; for subsets of $\mathbb{R}^{d}$, take the Borel
$\sigma$-algebra; for a product of sets that are each equipped with
$\sigma$-algebras, take it to be generated by the corresponding cylinder sets.
On the implied $\sigma$-algebra of $A$, $\mathcal{M}_{1}(A)$ denotes the set
of probability measures, and $\mathcal{M}_{+}(A)$ denotes the set of measures
that are finite on singletons and not everywhere zero. Thus,
$\mathcal{M}_{1}(A)=\\{\mu\in\mathcal{M}_{+}(A):\mu(A)=1\\}$. In a slight
abuse of notation, we identify singleton sets with their element, so that
$\mu(a):=\mu(\\{a\\})$. In this manner, when $A$ is countable, it’s convenient
to identify measures with real-valued functions of $A$:

$\displaystyle\mathcal{M}_{1}(A)$
$\displaystyle:=\\{\mu\in(\mathbb{R}^{+})^{A}:\sum_{a\in A}\mu(a)=1\\}$
$\displaystyle\subset\mathcal{M}_{+}(A)$
$\displaystyle:=\\{\mu\in(\mathbb{R}^{+})^{A}:\sum_{a\in A}\mu(a)>0\\}.$

A few measures are special enough to merit their own symbols.
$\lambda^{d}\in\mathcal{M}_{+}(\mathbb{R}^{d})$ denotes the Lebesgue (i.e.,
volume) measure. For $a\in A$, $\delta_{a}\in\mathcal{M}_{1}(A)$ denotes the
point mass that puts probability one on $a$. $\sharp:=\sum_{a\in A}\delta_{a}$
denotes the counting measure, i.e., for $A^{\prime}\subset A$,
$\sharp(A^{\prime}):=|A^{\prime}|$.

At times, we describe a collection of conditional distributions consistent
with a causal graph, thus uniquely determining the variables’ joint
distribution. In such cases, it’s implied that all the variables live in a
common probability space $(\Omega,\mathcal{F},\mathbb{P})$. That is, the
random variables are assumed to be defined on some sample space $\Omega$,
equipped with the $\sigma$-algebra $\mathcal{F}\subset 2^{\Omega}$ generated
by the variables, and a probability measure
$\mathbb{P}\in\mathcal{M}_{1}(\Omega)$. When referring to a random variable
$C:\Omega\rightarrow A$, we abuse notation and write $C\in A$. Depending on
context, the expression $F(C)$ may refer to either: (1) $F(\mathbb{P}_{C})$, a
function of $C$’s distribution; or (2) $\omega\mapsto F(\omega)(C(\omega))$, a
random variable obtained by applying a (possibly random) function to $C$’s
realization.

We use some customary shorthands, such as
$\mathbb{P}(C=c):=\mathbb{P}(\\{\omega\in\Omega:\;C(\omega)=c\\})$. The
marginal and conditional distributions of $C$ are written
$\mathbb{P}_{C},\mathbb{P}_{C\mid E}\in\mathcal{M}_{1}(A)$, respectively, for
any event $E\in\mathcal{F}$. For example,
$\mathbb{P}_{C}(c):=\mathbb{P}(C=c)$, and $\mathbb{P}_{C\mid
E}(c):=\mathbb{P}(C=c\mid E)$. Indexed collections of random variables
$\mathbf{C}=(C_{a})_{a\in A}$ may be bolded for emphasis. Via the minor abuse
of swapping argument order, the whole collection $\mathbf{C}$ can also be
thought of as a random variable: $\mathbf{C}(\omega)_{a}:=C_{a}(\omega)$.

Finally, the total variation norm of a signed measure $\mu$ is denoted by

$\lVert\mu\rVert_{\mathrm{TV}}:=\sup_{A\in\mathcal{F}}|\mu(A)|.$

It’s used to express the total variation distance between probability measures
$\mu,\nu$ as $\lVert\mu-\nu\rVert_{\mathrm{TV}}$.

###  III.2 The Kullback-Leibler Divergence

All of our information-theoretic quantities are derived from this definition.

######  Definition 1.

Let $\mathcal{S}$ be a countable set, $\mu\in\mathcal{M}_{1}(\mathcal{S}),$
and $\pi\in\mathcal{M}_{+}(\mathcal{S})$. The Kullback-Leibler divergence of
$\mu$ relative to $\pi$ is

$D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right):=\sum_{s\in\mathcal{S}}\mu(s)\log\frac{\mu(s)}{\pi(s)}.$

Following standard conventions, terms with $\mu(s)=0$ are treated as $0$, and
terms with $\mu(s)>\pi(s)=0$ are treated as $+\infty$ 666When the sum’s
positive and negative terms both diverge to infinity, the result is ill-
defined. For definiteness, we may define
$D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right)$ to be either of $\pm\infty$
in this case.. When the logarithm’s base is $2$, the KL divergence is measured
in units of bits; when the base is $e$, it’s measured in nats.

When $\pi$ is also a probability measure, it’s customary to think of
$D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right)$ as a kind of “distance”
between $\mu$ and $\pi$ [5, §2.3]. However, in this article, a different
interpretation is more useful:
$D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right)$ should be thought of as the
_precision_ with which samples from $\mu$ are known, meaning, loosely
speaking, the smallness of the $\pi$-measure of the “typical support” of
$\mu$. For a concrete example, let $\mu$ be $\pi$-uniform on a $\pi$-finite
support $A\subset\mathcal{S}$; that is, suppose $\pi(A)<\infty$, and let

$\mu(s):=\begin{cases}\pi(s)/\pi(A)&\text{if }s\in A,\\\ 0&\text{if
}s\in\mathcal{S}\setminus A.\end{cases}$

Then, it’s easily verified that
$D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right)=\log\frac{1}{\pi(A)}=\log\frac{1}{\sum_{s\in
A}\pi(s)}$. In general, the _least_ precise distributions are those that are
spread $\pi$-uniformly everywhere, whereas the _most_ precise are focused on a
single element with small $\pi$-measure:

######  Lemma 1.

For fixed $\pi\in\mathcal{M}_{+}(\mathcal{S})$,

$\displaystyle\inf_{\mu\in\mathcal{M}_{1}(\mathcal{S})}D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right)$
$\displaystyle=\log\frac{1}{\sum_{s\in\mathcal{S}}\pi(s)},$
$\displaystyle\sup_{\mu\in\mathcal{M}_{1}(\mathcal{S})}D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right)$
$\displaystyle=\log\frac{1}{\inf_{s\in\mathcal{S}}\pi(s)}.$

###### Proof.

First, we show that for all $\mu\in\mathcal{M}_{1}(\mathcal{S})$,

$\log\frac{1}{\sum_{s\in\mathcal{S}}\pi(s)}\leq
D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right)\leq\log\frac{1}{\inf_{s\in\mathcal{S}}\pi(s)}.$

If $\pi(\mathcal{S})=\infty$, the left-hand inequality follows from the
convention that $\log\frac{1}{\infty}=-\infty$. Otherwise,

$\displaystyle D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right)$
$\displaystyle=\sum_{s\in\mathcal{S}}\mu(s)\log\mu(s)-\sum_{s\in\mathcal{S}}\mu(s)\log\pi(s)$
$\displaystyle\geq\sum_{s\in\mathcal{S}}\mu(s)\log\frac{\pi(s)}{\sum_{s^{\prime}\in\mathcal{S}}\pi(s^{\prime})}-\sum_{s\in\mathcal{S}}\mu(s)\log\pi(s)$
by Gibbs’ inequality
$\displaystyle=\log\frac{1}{\sum_{s^{\prime}\in\mathcal{S}}\pi(s^{\prime})}.$

As for the right-hand inequality, since $0\leq\mu(s)\leq 1$ and
$\pi(s)\geq\inf_{s^{\prime}\in\mathcal{S}}\pi(s^{\prime})$,

$D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right)\leq\sum_{s\in\mathcal{S}}\mu(s)\log\frac{1}{\inf_{s^{\prime}\in\mathcal{S}}\pi(s^{\prime})}=\log\frac{1}{\inf_{s^{\prime}\in\mathcal{S}}\pi(s^{\prime})}.$

Now, to actually achieve the infimum, enumerate
$\mathcal{S}=\\{s_{1},s_{2},\ldots\\}$ and consider the $\pi$-uniform
distribution on $\\{s_{1},\ldots,s_{i}\\}$:

$\mu_{i}(s_{j}):=\begin{cases}\pi(s_{j})/\sum_{k=1}^{i}\pi(s_{k})&\text{if
}j\leq i\\\ 0&\text{if }j>i.\end{cases}$

Then, as $i\rightarrow\infty$,

$D_{\mathrm{KL}}\left(\mu_{i}\mathrel{\|}\pi\right)=\log\frac{1}{\sum_{k=1}^{i}\pi(s_{k})}\rightarrow\log\frac{1}{\sum_{s\in\mathcal{S}}\pi(s)}.$

Finally, to achieve the supremum, choose a sequence $(s_{i})_{i\in\mathbb{N}}$
such that $\lim_{i\rightarrow\infty}\pi(s_{i})=\inf_{s\in\mathcal{S}}\pi(s)$.
Then, as $i\rightarrow\infty$,

$D_{\mathrm{KL}}\left(\delta_{s_{i}}\mathrel{\|}\pi\right)=\log\frac{1}{\pi(s_{i})}\rightarrow\log\frac{1}{\inf_{s\in\mathcal{S}}\pi(s)}.$

∎

When the bounds in Lemma 1 are finite, it’s useful to compare them to
$D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right)$.

######  Definition 2.

Relative to a fixed $\pi\in\mathcal{M}_{+}(\mathcal{S})$, the entropy and
negentropy, respectively, of any $\mu\in\mathcal{M}_{1}(\mathcal{S})$ are

$\displaystyle
H_{\pi}(\mu):=-D_{\mathrm{KL}}\left(\mu\mathrel{\|}\frac{\pi}{\inf_{s\in\mathcal{S}}\pi(s)}\right)$
$\displaystyle=\log\frac{1}{\inf_{s\in\mathcal{S}}\pi(s)}-D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right)\geq
0,$ (8) $\displaystyle
J_{\pi}(\mu):=D_{\mathrm{KL}}\left(\mu\mathrel{\|}\frac{\pi}{\sum_{s\in\mathcal{S}}\pi(s)}\right)$
$\displaystyle=D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right)-\log\frac{1}{\sum_{s\in\mathcal{S}}\pi(s)}\geq
0.$ (9)

If $\inf_{s\in\mathcal{S}}\pi(s)=0$ or $\sum_{s\in\mathcal{S}}\pi(s)=\infty$,
we instead define $H_{\pi}(\mu):=\infty$ or $J_{\pi}(\mu):=\infty$,
respectively, regardless of $\mu$.

Note that the information capacity of $\pi$, generalized from Frank [25] by

$\textbf{I}(\pi):=H_{\pi}(\mu)+J_{\pi}(\mu)=\log\frac{1}{\inf_{s\in\mathcal{S}}\pi(s)}-\log\frac{1}{\sum_{s\in\mathcal{S}}\pi(s)},$

does not depend on $\mu$. Thus, each of $H_{\pi}(\mu)$ or $J_{\pi}(\mu)$ is
maximal precisely when the other is zero. $J_{\pi}(\mu)=0$ iff $\mu$ is the
$\pi$-uniform distribution $\pi/\pi(\mathcal{S})$, and $H_{\pi}(\mu)=0$ iff
$\mu$ is a point mass $\delta_{s}$ satisfying
$s\in\arg\min_{s^{\prime}\in\mathcal{S}}\pi(s^{\prime})$. As a special case,
we recover the Shannon entropy and negentropy:

$\displaystyle
H(\mu):=H_{\sharp}(\mu)=-D_{\mathrm{KL}}\left(\mu\mathrel{\|}\sharp\right)$
$\displaystyle=\sum_{s\in\mathcal{S}}\mu(s)\log\frac{1}{\mu(s)},$
$\displaystyle
J(\mu):=J_{\sharp}(\mu)=\log|\mathcal{S}|+D_{\mathrm{KL}}\left(\mu\mathrel{\|}\sharp\right)$
$\displaystyle=\log|\mathcal{S}|-H(\mu).$

It may aid the reader’s intuition to specialize the results of this article to
the case $\pi=\sharp$. The additional generality enables analysis of dynamics
with non-uniform stationary distributions. The next definition is useful when
we discuss memory, and want to quantify how much two systems know about one
another. In what follows, let $\mathcal{S}_{X},\mathcal{S}_{Y}$ be countable
sets.

######  Definition 3.

The mutual information between a pair of random variables
$X\in\mathcal{S}_{X},\,Y\in\mathcal{S}_{Y}$ is

$I(X;\,Y):=D_{\mathrm{KL}}\left(\mathbb{P}_{(X,Y)}\mathrel{\|}\mathbb{P}_{X}\times\mathbb{P}_{Y}\right)=\sum_{x,y}\mathbb{P}(X=x,Y=y)\log\frac{\mathbb{P}(X=x,Y=y)}{\mathbb{P}(X=x)\mathbb{P}(Y=y)}.$

It’s often convenient to identify a random variable with its distribution. For
example, we may speak of the KL divergence of a random variable, perhaps
conditioned on some event, as a shorthand for the KL divergence of its
marginal or conditional probability measure. That is,
$D_{\mathrm{KL}}\left(X\mathrel{\|}\pi\right):=D_{\mathrm{KL}}\left(\mathbb{P}_{X}\mathrel{\|}\pi\right)$
and $D_{\mathrm{KL}}\left(X\mid
Y=y\mathrel{\|}\pi\right):=D_{\mathrm{KL}}\left(\mathbb{P}_{X\mid
Y=y}\mathrel{\|}\pi\right)$. As a further shorthand, let
$D_{\mathrm{KL}}\left(X\mid
Y\mathrel{\|}\pi_{X}\right):=\mathbb{E}_{y}D_{\mathrm{KL}}\left(X\mid
Y=y\mathrel{\|}\pi_{X}\right)$, where the expectation is over realizations of
$Y$, i.e., $\mathbb{E}_{y}f(y):=\sum_{y}\mathbb{P}(Y=y)f(y)$.

######  Lemma 2.

Let
$\pi_{X}\in\mathcal{M}_{+}(\mathcal{S}_{X}),\,\pi_{Y}\in\mathcal{M}_{+}(\mathcal{S}_{Y})$.
For any random variables $X\in\mathcal{S}_{X},\,Y\in\mathcal{S}_{Y}$,

$\displaystyle
D_{\mathrm{KL}}\left(X,Y\mathrel{\|}\pi_{X}\times\pi_{Y}\right)$
$\displaystyle=D_{\mathrm{KL}}\left(Y\mathrel{\|}\pi_{Y}\right)+D_{\mathrm{KL}}\left(X\mid
Y\mathrel{\|}\pi_{X}\right),$ $\displaystyle D_{\mathrm{KL}}\left(X\mid
Y\mathrel{\|}\pi_{X}\right)$
$\displaystyle=D_{\mathrm{KL}}\left(X\mathrel{\|}\pi_{X}\right)+I(X;\,Y).$

###### Proof.

From their respective definitions,

$\displaystyle D_{\mathrm{KL}}\left(X\mathrel{\|}\pi_{X}\right)$
$\displaystyle=\mathbb{E}_{x,y}\log\frac{\mathbb{P}(X=x)}{\pi_{X}(x)},$
$\displaystyle D_{\mathrm{KL}}\left(Y\mathrel{\|}\pi_{Y}\right)$
$\displaystyle=\mathbb{E}_{x,y}\log\frac{\mathbb{P}(Y=y)}{\pi_{Y}(y)},$
$\displaystyle D_{\mathrm{KL}}\left(X\mid Y\mathrel{\|}\pi_{X}\right)$
$\displaystyle=\mathbb{E}_{x,y}\log\frac{\mathbb{P}(X=x\mid
Y=y)}{\pi_{X}(x)},$ $\displaystyle
D_{\mathrm{KL}}\left(X,Y\mathrel{\|}\pi_{X}\times\pi_{Y}\right)$
$\displaystyle=\mathbb{E}_{x,y}\log\frac{\mathbb{P}(X=x,Y=y)}{\pi_{X}(x)\pi_{Y}(y)},$
$\displaystyle I(X;\,Y)$
$\displaystyle=\mathbb{E}_{x,y}\log\frac{\mathbb{P}(X=x,Y=y)}{\mathbb{P}(X=x)\mathbb{P}(Y=y)}.$

Therefore,

$\displaystyle
D_{\mathrm{KL}}\left(X,Y\mathrel{\|}\pi_{X}\times\pi_{Y}\right)$
$\displaystyle=\mathbb{E}_{x,y}\log\frac{\mathbb{P}(X=x\mid
Y=y)\mathbb{P}(Y=y)}{\pi_{X}(x)\pi_{Y}(y)}$
$\displaystyle=D_{\mathrm{KL}}\left(Y\mathrel{\|}\pi_{Y}\right)+D_{\mathrm{KL}}\left(X\mid
Y\mathrel{\|}\pi_{X}\right),\text{ and}$ $\displaystyle
D_{\mathrm{KL}}\left(X\mid Y\mathrel{\|}\pi_{X}\right)$
$\displaystyle=\mathbb{E}_{x,y}\log\frac{\mathbb{P}(X=x,Y=y)}{\pi_{X}(x)\mathbb{P}(Y=y)}$
$\displaystyle=D_{\mathrm{KL}}\left(X\mathrel{\|}\pi_{X}\right)+I(X;\,Y).$

∎

Our first corollary is a generalization of Equation 7 that expresses the joint
negentropy as a sum of three non-negative contributions.

######  Corollary 1.

Let
$\pi_{X}\in\mathcal{M}_{+}(\mathcal{S}_{X}),\,\pi_{Y}\in\mathcal{M}_{+}(\mathcal{S}_{Y})$.
For any random variables $X\in\mathcal{S}_{X},\,Y\in\mathcal{S}_{Y}$,

$\displaystyle
J_{\pi_{X}\times\pi_{Y}}(X,Y)=J_{\pi_{X}}(X)+J_{\pi_{Y}}(Y)+I(X;\,Y).$

###### Proof.

Substitute the second part of Lemma 2 into the first, to get

$D_{\mathrm{KL}}\left(X,Y\mathrel{\|}\pi_{X}\times\pi_{Y}\right)=D_{\mathrm{KL}}\left(X\mathrel{\|}\pi_{X}\right)+D_{\mathrm{KL}}\left(Y\mathrel{\|}\pi_{Y}\right)+I(X;\,Y).$
(10)

Substituting Equation 9 into Equation 10 yields the desired result. ∎

We close this section with another pair of bounds.

######  Corollary 2.

Let
$\pi_{X}\in\mathcal{M}_{+}(\mathcal{S}_{X}),\,\pi_{Y}\in\mathcal{M}_{+}(\mathcal{S}_{Y})$.
For any random variables $X\in\mathcal{S}_{X},\,Y\in\mathcal{S}_{Y}$,

$\displaystyle\log\frac{1}{\sum_{s\in\mathcal{S}_{X}}\pi_{X}(s)}\leq
D_{\mathrm{KL}}\left(X,Y\mathrel{\|}\pi_{X}\times\pi_{Y}\right)-D_{\mathrm{KL}}\left(Y\mathrel{\|}\pi_{Y}\right)\leq\log\frac{1}{\inf_{s\in\mathcal{S}_{X}}\pi_{X}(s)}.$

###### Proof.

By Lemma 2,

$D_{\mathrm{KL}}\left(X,Y\mathrel{\|}\pi_{X}\times\pi_{Y}\right)-D_{\mathrm{KL}}\left(Y\mathrel{\|}\pi_{Y}\right)=D_{\mathrm{KL}}\left(X\mid
Y\mathrel{\|}\pi_{X}\right)=\mathbb{E}_{y}D_{\mathrm{KL}}\left(X\mid
Y=y\mathrel{\|}\pi_{X}\right).$

The result now follows from Lemma 1, because

$\displaystyle\log\frac{1}{\sum_{s\in\mathcal{S}_{X}}\pi_{X}(s)}$
$\displaystyle\leq\inf_{y}D_{\mathrm{KL}}\left(X\mid
Y=y\mathrel{\|}\pi_{X}\right)$
$\displaystyle\leq\mathbb{E}_{y}D_{\mathrm{KL}}\left(X\mid
Y=y\mathrel{\|}\pi_{X}\right)$
$\displaystyle\leq\sup_{y}D_{\mathrm{KL}}\left(X\mid
Y=y\mathrel{\|}\pi_{X}\right)\leq\log\frac{1}{\inf_{s\in\mathcal{S}_{X}}\pi_{X}(s)}.$

∎

##  IV Markov Chains

In practical applications, when one wishes to model a system that evolves with
time, without concern for microscopic details, it’s common to use a very
simple kind of causal model called a Markov chain. Its random variables are
arranged in a linear sequence, like so:

$\displaystyle C_{0}\rightarrow C_{1}$ $\displaystyle\rightarrow
C_{2}\rightarrow C_{3}\rightarrow\cdots$

Recall that causal graphs encode two things: independence constraints and
intervention rules. For a closed system, interventions play no role, so the
graph only encodes the independences given by Pearl’s $d$-separation
criterion. For a Markov chain, these are nicely summarized by the Markov
property, which can be stated in a symmetric fashion:

$\displaystyle\text{For all }t\in\mathbb{N},\;C_{>t}\text{ is independent of
}C_{<t},\text{ conditioned on }C_{t}.$

The Markov property is unchanged for the time-reversed Markov chain:

$\displaystyle C_{0}\leftarrow C_{1}$ $\displaystyle\leftarrow C_{2}\leftarrow
C_{3}\leftarrow\cdots$

Since the two graphs yield identical constraints on the joint probability
distribution of $\mathbf{C}:=(C_{t})_{t\in\mathbb{Z}^{+}}$, there is no
observation on $\mathbf{C}$ that can distinguish between the graphs. Thus, in
the general case, Markov chains lack a well-defined causal direction.

There exist graphs in which a causal direction _can_ be inferred from passive
observation alone, without interventions: see [11, §2] for a systematic
treatment, or Section V for the relevant case of SPCAs. On the other hand,
non-graphical constraints may also contribute an arrow of time. We’ll soon see
that non-stationary _time-homogeneous_ Markov chains cease to be time-
homogeneous in the reverse direction. This particular asymmetry is responsible
for the second law of thermodynamics; see Theorem 1.

This section has two main purposes. The first is to forge a bridge between
Markov chains and deterministic dynamical systems, which allows useful
properties to transfer from one to the other. We formally define three ways to
specify a Markov chain’s dynamics, the last of which provides our bridge: it
expresses the sequence $\mathbf{C}$ as the macroscopic component of a
deterministic system with random initialization.

This section’s second purpose is to better understand how the arrow of time
arises in Markov chains. We learn how time-homogeneity breaks time-reversal
symmetry. Then, using the bridge to deterministic dynamics, we trace the time-
homogeneity back to microscopic variations in the initial conditions. Finally,
by crossing the bridge to a _reversible_ deterministic system, running that
system backward beyond the initial condition, and then crossing back into the
world of Markov chains, our Markov chains acquire a natural bidirectional
extension:

$\displaystyle\cdots\leftarrow C_{-2}\leftarrow C_{-1}\leftarrow
C_{0}\rightarrow C_{1}$ $\displaystyle\rightarrow C_{2}\rightarrow\cdots$ (11)

Throughout this section, let $\mathcal{S}$ be a fixed countable set. Its
elements should be thought of as the fine macrostates discussed in Section
I.2. $\mathcal{S}$ is our Markov chain’s state space, which we eventually see
as a discretization of some dynamical system’s state space.

When speaking of a collection of random variables, such as $\mathbf{C}$, we
really only care about their joint distribution
$\mathbb{P}_{\mathbf{C}}\in\mathcal{M}_{1}(\mathcal{S}^{\mathbb{Z}^{+}})$.
Thus, we formally define a Markov chain to be any element of
$\mathcal{M}_{1}(\mathcal{S}^{\mathbb{Z}^{+}})$ that satisfies the Markov
property. We say a Markov chain is homogeneous in time, or time-homogeneous,
if its conditional distribution $\mathbb{P}(C_{t+1}=c_{t+1}\mid C_{t}=c_{t})$
does not depend on $t$.

Let
$\mathrm{Markov}(\mathcal{S})\subset\mathcal{M}_{1}(\mathcal{S}^{\mathbb{Z}^{+}})$
denote the set of time-homogeneous Markov chains. An element of
$\mathrm{Markov}(\mathcal{S})$ is uniquely determined by (1) its initial
distribution $\mathbb{P}_{C_{0}}$, and (2) its dynamics, i.e., the time-
independent conditional distributions $\mathbb{P}_{C_{t+1}\mid C_{t}=c_{t}}$.
We always specify the initial distribution directly, but consider three
different means of specifying the dynamics. Let’s start with the direct
approach.

###  IV.1 Transition Matrix Presentation

Since the conditional distributions $\mathbb{P}_{C_{t+1}\mid C_{t}=c_{t}}$ are
assumed not to depend on $t$, we need only specify one distribution for each
possible preceding state $c_{t}\in\mathcal{S}$. In other words, the dynamics
are given by an element of $\mathcal{M}_{1}(\mathcal{S})^{\mathcal{S}}$ or,
equivalently, a $|\mathcal{S}|\times|\mathcal{S}|$ stochastic matrix.

######  Definition 4.

Suppose $\pi\in\mathcal{M}_{+}(\mathcal{S})$. The set of stochastic matrices,
doubly stochastic matrices, and $\pi$-stochastic matrices on $\mathcal{S}$
are, respectively,

$\displaystyle\mathrm{SM}(\mathcal{S})$
$\displaystyle:=\\{p\in(\mathbb{R}^{+})^{\mathcal{S}\times\mathcal{S}}:\;\forall
s\in\mathcal{S},\;\sum_{s^{\prime}\in\mathcal{S}}p(s,s^{\prime})=1\\},$
$\displaystyle\mathrm{DM}(\mathcal{S})$
$\displaystyle:=\\{p\in(\mathbb{R}^{+})^{\mathcal{S}\times\mathcal{S}}:\;\forall
s\in\mathcal{S},\;\sum_{s^{\prime}\in\mathcal{S}}p(s,s^{\prime})=\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime},s)=1\\},$
$\displaystyle\mathrm{SM}_{\pi}(\mathcal{S})$
$\displaystyle:=\\{p\in\mathrm{SM}(\mathcal{S}):\;\forall
s\in\mathcal{S},\;\sum_{s^{\prime}\in\mathcal{S}}\pi(s^{\prime})p(s^{\prime},s)=\pi(s)\\}.$

Note that $\mathrm{SM}_{\sharp}(\mathcal{S})=\mathrm{DM}(\mathcal{S})$. $\pi$
is said to be stationary for $p$ if $p\in\mathrm{SM}_{\pi}(\mathcal{S})$. For
$m\in\mathbb{N}$, a measure $\mu$ or matrix $p$ is said to be $m$-sided if all
its entries are multiples of $\frac{1}{m}$; that is, if
$\mu\in(\frac{1}{m}\mathbb{Z}^{+})^{\mathcal{S}}$ or
$p\in(\frac{1}{m}\mathbb{Z}^{+})^{\mathcal{S}\times\mathcal{S}}$,
respectively. If we don’t want to specify $m$, we can also say it is finite-
sided. It is said to be strictly positive if none of its entries are zero.

######  Definition 5.

The transition matrix presentation of time-homogeneous Markov chains on
$\mathcal{S}$ is the surjective map

$\Phi_{\mathrm{matrix}}:\mathcal{M}_{1}(\mathcal{S})\times\mathrm{SM}(\mathcal{S})\rightarrow\mathrm{Markov}(\mathcal{S}),$

defined as follows. Consider any initial condition
$\mu\in\mathcal{M}_{1}(\mathcal{S})$ and transition matrix
$p\in\mathrm{SM}(\mathcal{S})$. Let the random variable
$\mathbf{C}=(C_{t})_{t\in\mathbb{Z}^{+}}$ be distributed such that, for all
$c:\mathbb{Z}^{+}\rightarrow\mathcal{S}$,

$\mathbb{P}(C_{\leq t}=c_{\leq
t})=\mu(c_{0})\prod_{u=0}^{t-1}p(c_{u},\,c_{u+1})\qquad\forall
t\in\mathbb{Z}^{+}.$

Or equivalently,

$\displaystyle\mathbb{P}(C_{0}=c_{0})$ $\displaystyle=\mu(c_{0}),$ (12)
$\displaystyle\mathbb{P}(C_{t+1}=c_{t+1}\mid C_{\leq t}=c_{\leq t})$
$\displaystyle=p(c_{t},\,c_{t+1})\qquad\forall t\in\mathbb{Z}^{+}.$ (13)

Then, $\Phi_{\mathrm{matrix}}(\mu,\,p):=\mathbb{P}_{\mathbf{C}}.$

Now, just as a Markov chain’s causal graph can be reversed without affecting
$\mathbb{P}_{\mathbf{C}}$, one might wonder: can Equation 13 be reversed, or
does it represents a true time-reversal asymmetry? This is really a two-part
question: (1) can $\mathbb{P}(C_{t-1}=c_{t-1}\mid C_{\geq t}=c_{\geq t})$ be
expressed as a function of only $c_{t}$ and $c_{t-1}$, independent of $t$; and
(2) can $\mathbf{C}$ be extended to negative times, in such a way that
Equation 13 is satisfied there as well?

In general, the answer to both questions is no. Extensions to negative times
are not guaranteed to exist, nor be unique if they do: the simplest
counterexamples are deterministic transitions that are non-surjective or non-
injective, respectively. Even at positive times, the backward probabilities
may be inhomogeneous. Let’s derive them using the Markov property and Bayes’
rule:

$\displaystyle\mathbb{P}(C_{t-1}=c_{t-1}\mid C_{\geq t}=c_{\geq t})$
$\displaystyle=\mathbb{P}(C_{t-1}=c_{t-1}\mid C_{t}=c_{t})$
$\displaystyle=\frac{\mathbb{P}(C_{t-1}=c_{t-1})\mathbb{P}(C_{t}=c_{t}\mid
C_{t-1}=c_{t-1})}{\mathbb{P}(C_{t}=c_{t})}$
$\displaystyle=\frac{\mathbb{P}(C_{t-1}=c_{t-1})}{\mathbb{P}(C_{t}=c_{t})}p(c_{t-1},c_{t}).$
(14)

The analysis is simpler when $p$ is recurrent, meaning that from every
$s\in\mathcal{S}$, we’ll almost surely eventually revisit $s$. In that case,
$p$ has a strictly positive stationary measure $\pi$ which, on each
irreducible component of $\mathcal{S}$, is uniquely determined up to constant
multiples [49, Thm 17.48 and Rmk 17.51(i)]. In particular, if
$p(s^{\prime},s)>0$, then $s^{\prime},s$ are in the same irreducible
component, and so the ratio $\pi(s^{\prime})/\pi(s)$ is uniquely determined.
Therefore, the dual transition matrix

$\displaystyle
p_{\mathrm{dual}}(s,s^{\prime}):=\frac{\pi(s^{\prime})}{\pi(s)}p(s^{\prime},s)$
(15)

is well-defined, and it’s easy to check that
$p_{\mathrm{dual}}\in\mathrm{SM}_{\pi}(\mathcal{S})$. If $p$ is not recurrent
but has one or more stationary measures, the same expression defines the dual
transition matrix with respect to a specific stationary measure $\pi$,
provided that we delete the states with $\pi(s)=0$.

Now, suppose the initial distribution $\mu$ is stationary for $p$. Then,
$\mathbb{P}_{C_{t}}=\mu$ for all $t$ so, wherever $\mu(c_{t})>0$, the backward
dynamics

$\mathbb{P}(C_{t-1}=c_{t-1}\mid C_{\geq t}=c_{\geq
t})=\frac{\mu(c_{t-1})}{\mu(c_{t})}p(c_{t-1},c_{t})=p_{\mathrm{dual}}(c_{t},c_{t-1})$
(16)

are indeed time-homogeneous. This also grants $\mathbf{C}$ a unique extension
to negative times, satisfying both Equations 13 and 16 for all
$t\in\mathbb{Z}$.

On the other hand, when $\mu$ is non-stationary, the backward probabilities in
Equation 14 may differ from $p_{\mathrm{dual}}(c_{t},c_{t-1})$. Typically, the
ratio $\mathbb{P}(C_{t-1}=c_{t-1})/\mathbb{P}(C_{t}=c_{t})$ is time-dependent,
rendering the backward probabilities inhomogeneous in time.

It’s still possible to extend $\mathbf{C}$ in such a way that Equation 16, but
not Equation 13, is satisfied at negative times. Section IV.5 justifies such
an extension in terms of reversible microscopic dynamics. Picturing two arrows
of time diverging from $t=0$ to $\pm\infty$, we find homogeneous dynamics ($p$
at positive times, $p_{\mathrm{dual}}$ at negative times) _along_ the arrow,
and inhomogenous probabilities (inferred using Bayes’ rule) _against_ the
arrow. Thus, just as “down” always points toward Earth’s center, the “past”
always points toward the initial condition.

Suppose $p\in\mathrm{SM}_{\pi}(\mathcal{S})$. Intuitively, as $t$ increases,
the state distribution $\mathbb{P}_{C_{t}}$ moves “closer” to $\pi$. To make
this precise, we define the thermo-majorization relation $\succeq_{\pi}$.

######  Definition 6.

Suppose $\mu,\nu\in\mathcal{M}_{1}(\mathcal{S})$ and
$\pi\in\mathcal{M}_{+}(\mathcal{S})$. We say $\mu$ thermo-majorizes $\nu$ with
respect to $\pi$, and write $\mu\succeq_{\pi}\nu$, if there exists
$p\in\mathrm{SM}_{\pi}(\mathcal{S})$ transforming $\mu$ into $\nu$, i.e.,

$\displaystyle\sum_{s^{\prime}\in\mathcal{S}}\mu(s^{\prime})p(s^{\prime},s)=\nu(s),\quad\sum_{s^{\prime}\in\mathcal{S}}\pi(s^{\prime})p(s^{\prime},s)=\pi(s)\qquad\forall
s\in\mathcal{S}.$

From the fact that $\mathrm{SM}_{\pi}(\mathcal{S})$ is closed under matrix
multiplication, it follows that $\succeq_{\pi}$ is a preorder. Progress along
$\succeq_{\pi}$ can be quantified by the KL divergence:

######  Theorem 1 (Second law of thermodynamics).

Suppose $\mu,\nu\in\mathcal{M}_{1}(\mathcal{S})$,
$\pi\in\mathcal{M}_{+}(\mathcal{S})$, and $\mu\succeq_{\pi}\nu$. Then,

$D_{\mathrm{KL}}\left(\mu\mathrel{\|}\pi\right)\geq
D_{\mathrm{KL}}\left(\nu\mathrel{\|}\pi\right).$

A proof is provided by Cover and Thomas [5, §4.4], and a broad generalization
by Brandão  _et al._ [50, Thm 17]. For a Markov chain $\mathbf{C}$ with
stationary measure $\pi$, it’s immediate from Definitions 4 and 6 that
$C_{t}\succeq_{\pi}C_{t+1}$ for all $t\in\mathbb{Z}^{+}$. Therefore, Theorem 1
implies $D_{\mathrm{KL}}\left(C_{t}\mathrel{\|}\pi\right)\geq
D_{\mathrm{KL}}\left(C_{t+1}\mathrel{\|}\pi\right)$. Using Definition 2, we
recover the familiar statement that entropy increases monotonically:

$H_{\pi}(C_{t})\leq H_{\pi}(C_{t+1})\qquad\forall t\in\mathbb{Z}^{+}.$

###  IV.2 Random Function Presentation

In physics, dynamics are not given as transition matrices, but as reversible
_equations of motion_. Integrating equations of motion for a fixed time
interval yields their discrete-time analogue: invertible functions on
$\mathcal{S}$. These functions should be deterministic; however, as a first
step, we present Markov chains in terms of _random_ functions on
$\mathcal{S}$.

######  Definition 7.

The random function presentation of time-homogeneous Markov chains on
$\mathcal{S}$ is the map

$\Phi_{\mathrm{random}}:\mathcal{M}_{1}(\mathcal{S})\times\mathcal{M}_{1}(\mathcal{S}^{\mathcal{S}})\rightarrow\mathrm{Markov}(\mathcal{S}),$

defined as follows. Consider any initial condition
$\mu\in\mathcal{M}_{1}(\mathcal{S})$ and random dynamics
$\Gamma\in\mathcal{M}_{1}(\mathcal{S}^{\mathcal{S}})$. Let the random
variables $(\mathbf{C},\mathbf{F})=(C_{t},F_{t})_{t\in\mathbb{Z}^{+}}$ be
distributed such that

$\displaystyle\mathbb{P}_{(C_{0},\mathbf{F})}$
$\displaystyle=\mu\times\Gamma^{\mathbb{Z}^{+}},$ (17) $\displaystyle C_{t+1}$
$\displaystyle=F_{t}(C_{t})\qquad\forall t\in\mathbb{Z}^{+}.$ (18)

Then, $\Phi_{\mathrm{random}}(\mu,\,\Gamma):=\mathbb{P}_{\mathbf{C}}.$

In other words, the random functions $(F_{t})_{t\in\mathbb{Z}^{+}}$ are i.i.d.
samples from a fixed distribution $\Gamma$. At each time $t\in\mathbb{Z}^{+}$,
$C_{\leq t}$ is independent of $F_{\geq t}$; applying $F_{t}$ to $C_{t}$
produces the next state $C_{t+1}$.

For example, a random walk on $\mathcal{S}:=\mathbb{Z}$ can be described as
follows. Let $\Gamma$ be the uniform distribution on the multiset
$\\{\iota_{-1},\iota_{0},\iota_{0},\iota_{1}\\}$, where
$\iota_{i}:\mathbb{Z}\rightarrow\mathbb{Z}$ is defined by $\iota_{i}(s):=s+i$.
Let the initial distribution $\mu\in\mathcal{M}_{1}(\mathbb{Z})$ be arbitrary.
Then, $\Phi_{\mathrm{random}}(\mu,\,\Gamma)$ is a random walk that steps left
or right on the number line, with $1/4$ probability each. The equivalent
transition matrix is

$p(s,\,s+i)=\begin{cases}1/2&\text{if }i=0,\\\ 1/4&\text{if }i=\pm 1,\\\
0&\text{otherwise}.\end{cases}$

We extend the definition of $m$-sidedness to measures whose range is
constrained to multiples of $1/m$. Thus,
$\Gamma\in\mathcal{M}_{1}(\mathcal{S}^{\mathcal{S}})$ is $m$-sided iff it is
uniform over some multiset of $m$ functions. In our example, both $\Gamma$ and
$p$ are $4$-sided. The functions $\iota_{i}$ are bijective, whereas the matrix
$p$ is doubly stochastic. These parallels are no coincidence: we now prove a
general correspondence between the random function and transition matrix
presentations.

######  Theorem 2.

For every $\Gamma\in\mathcal{M}_{1}(\mathcal{S}^{\mathcal{S}})$, there is a
_unique_ $p\in\mathrm{SM}(\mathcal{S})$ such that, for all
$\mu\in\mathcal{M}_{1}(\mathcal{S})$,
$\Phi_{\mathrm{matrix}}(\mu,p)=\Phi_{\mathrm{random}}(\mu,\Gamma)$. If
$\Gamma(\mathrm{Bij}(\mathcal{S}))=1$, then $p\in\mathrm{DM}(\mathcal{S})$. If
$\Gamma$ is $m$-sided, then so is $p$.

Conversely, for every $p\in\mathrm{SM}(\mathcal{S})$, there exists
$\Gamma\in\mathcal{M}_{1}(\mathcal{S}^{\mathcal{S}})$ such that, for all
$\mu\in\mathcal{M}_{1}(\mathcal{S})$,
$\Phi_{\mathrm{matrix}}(\mu,p)=\Phi_{\mathrm{random}}(\mu,\Gamma)$. If
$p\in\mathrm{DM}(\mathcal{S})$ and/or $p$ is $m$-sided, then $\Gamma$ can be
chosen to be supported on $\mathrm{Bij}(\mathcal{S})$ and/or $m$-sided,
respectively.

###### Proof.

Uniqueness of $p(s,s^{\prime})$ follows from the fact that it can be read off
a Markov chain, by initializing with $C_{0}=s$ and checking the probability
that $C_{1}=s^{\prime}$:

$p(s,\,s^{\prime})=\Phi_{\mathrm{matrix}}(\delta_{s},\,p)(C_{1}=s^{\prime}).$

To prove the first implication, fix
$\Gamma\in\mathcal{M}_{1}(\mathcal{S}^{\mathcal{S}})$. For
$s,s^{\prime}\in\mathcal{S}$, define the sets

$\displaystyle A(s,s^{\prime})$
$\displaystyle:=\\{f\in\mathcal{S}^{\mathcal{S}}:\;f(s)=s^{\prime}\\},$
$\displaystyle\text{and let }p(s,s^{\prime})$
$\displaystyle:=\Gamma(A(s,s^{\prime})).$ $\displaystyle\text{Then, for all
}s\in\mathcal{S},\;\sum_{s^{\prime}\in\mathcal{S}}p(s,s^{\prime})$
$\displaystyle=\Gamma\left(\bigcup_{s^{\prime}\in\mathcal{S}}A(s,s^{\prime})\right)=\Gamma(\mathcal{S})=1,$

because the sets $A(s,s^{\prime})$, with fixed $s$, form a partition of
$\mathcal{S}^{\mathcal{S}}$. Hence, $p\in\mathrm{SM}(\mathcal{S})$. The roles
of $s$ and $s^{\prime}$ become symmetric when restricting to
$\mathrm{Bij}(\mathcal{S})$, so that the sets
$A(s,s^{\prime})\cap\mathrm{Bij}(\mathcal{S})$, with either $s$ or
$s^{\prime}$ held fixed, form a partition of $\mathrm{Bij}(\mathcal{S})$.
Therefore, by the same argument, if $\Gamma(\mathrm{Bij}(\mathcal{S}))=1$,
then $p\in\mathrm{DM}(\mathcal{S})$. In addition, if $\Gamma$ is $m$-sided,
then so is $p$ by its definition.

Now, fix $\mu\in\mathcal{M}_{1}(\mathcal{S})$. Let $(\mathbf{C},\mathbf{F})$
be as in Definition 7, so that
$\mathbb{P}_{\mathbf{C}}=\Phi_{\mathrm{random}}(\mu,\Gamma)$. By definition,
$\mathbb{P}_{C_{0}}=\mu$, so Equation 12 holds. Furthermore, since $F_{t}$ is
independent of $C_{\leq t}$,

$\mathbb{P}(C_{t+1}=c_{t+1}\mid C_{\leq t}=c_{\leq
t})=\mathbb{P}(F_{t}(c_{t})=c_{t+1})=\Gamma(A(c_{t},c_{t+1}))=p(c_{t},c_{t+1}),$

so Equation 13 holds as well. Therefore,
$\Phi_{\mathrm{matrix}}(\mu,p)=\Phi_{\mathrm{random}}(\mu,\Gamma)$.

To prove the converse, fix $p\in\mathrm{SM}(\mathcal{S})$. Enumerate
$\mathcal{S}=\\{s_{1},s_{2},\ldots\\}$. For each $r\in[0,1)$ and
$s\in\mathcal{S}$, let $f_{r}(s):=s_{i}$, where $i\in\mathbb{N}$ is chosen
such that $\sum_{j=1}^{i-1}p(s,s_{j})\leq r<\sum_{j=1}^{i}p(s,s_{j})$. If we
take $r$ to be drawn uniformly from $[0,1)$, then $f_{r}$ is drawn from the
pushforward measure $\Gamma(B):=\lambda(\\{r\in[0,1):f_{r}\in B\\})$. For all
$s,s_{i}\in\mathcal{S}$, it satisfies

$\Gamma(A(s,s_{i}))=\lambda(\\{r\in[0,1):\,f_{r}(s)=s_{i}\\})=\lambda\left(\left[\sum_{j=1}^{i-1}p(s,s_{j}),\;\sum_{j=1}^{i}p(s,s_{j})\right)\right)=p(s,s_{i}).$

Just as in the previous case, this equation implies that
$\Phi_{\mathrm{matrix}}(\cdot,p)=\Phi_{\mathrm{random}}(\cdot,\Gamma)$. In the
case where $p$ is $m$-sided, by definition, $f_{r}$ = $f_{\lfloor
rm\rfloor/m}$ for all $r\in[0,1)$. $\Gamma$ is then the uniform distribution
over $\\{f_{0},f_{1/m},\ldots,f_{(m-1)/m}\\}$, making it $m$-sided as well.

If $p\in\mathrm{DM}(\mathcal{S})$, special care is needed to construct
$\Gamma$ using only bijections, satisfying
$\Gamma(A(s,s^{\prime})\cap\mathrm{Bij}(\mathcal{S}))=p(s,s^{\prime})$. The
existence of such a $\Gamma$ is a generalization of the Birkhoff-von Neumann
theorem; see the proof by Révész [51]. An easier construction is possible
under the additional hypothesis that $p$ is $m$-sided: consider the bipartite
graph with vertex partition $(\mathcal{S},\mathcal{S})$ and, for each
$s,s^{\prime}\in\mathcal{S}$, $m\cdot p(s,s^{\prime})$ edges from $s$ in the
left partition to $s^{\prime}$ in the right. Since
$p\in\mathrm{DM}(\mathcal{S})$, the graph is $m$-regular, meaning that each
vertex is incident to exactly $m$ edges. Repeated application of Hall’s
marriage theorem partitions the edges into $m$ perfect matchings, i.e.,
bijections on $\mathcal{S}$. We take $\Gamma$ to be the uniform distribution
over these $m$ bijections. ∎

###  IV.3 Deterministic Function Presentation

To complete our bridge into the theory of dynamical systems, we must
derandomize the transition function. Consider again our $4$-sided random walk
on $\mathbb{Z}$, whose dynamics sample uniformly from the multiset of
transition functions
$\\{\iota_{-1},\iota_{0},\iota_{0},\iota_{1}\\}\subset\mathrm{Bij}(\mathbb{Z})$.
We can simulate one step of the walk by rolling a fair $4$-sided die. Denoting
the roll at time $t$ by $R_{t,0}\in\mathbb{Z}_{4}$, $C_{t+1}$ becomes a
deterministic function of the pair $(C_{t},R_{t,0})$. Since a deterministic
function cannot add new rolls to the state, we should attach an infinite
supply of rolls to the initial state $C_{0}$.

The idea, then, is to start with an extended state $(C_{0},R_{0})$, which
includes the bi-infinite sequence $R_{0}=(R_{0,i})_{i\in\mathbb{Z}}$ of pre-
rolled dice. Define a “macroscopic” transition function
$T:\mathbb{Z}\times\mathbb{Z}_{4}\rightarrow\mathbb{Z}\times\mathbb{Z}_{4}$
by, for all $s\in\mathbb{Z}$,

$\displaystyle T(s,0)$ $\displaystyle:=(s-1,\,0),$ $\displaystyle T(s,1)$
$\displaystyle:=(s,\,1),$ $\displaystyle T(s,2)$ $\displaystyle:=(s,\,2),$
$\displaystyle T(s,3)$ $\displaystyle:=(s+1,\,3).$

Note that $T$ is bijective. The full dynamics consist of two interleaved
operations on the expanded state space
$\mathbb{Z}\times(\mathbb{Z}_{4})^{\mathbb{Z}}$. First, $T$ is applied using
only the central (i.e., $0$’th) die:

$(C_{t+1},R^{\prime}_{t,0}):=T(C_{t},R_{t,0}).$

Note that $R^{\prime}_{t,0}=R_{t,0}$ in our example. Then, the $4$-symbol
shift map $\sigma$ is applied to the sequence of dice, centering $R_{t,1}$ in
preparation for the next application of $T$:

$\displaystyle R_{t}=(\ldots,R_{t,-1},$ $\displaystyle
R_{t,0},R_{t,1},\ldots),$ $\displaystyle R_{t+1}=\sigma((R_{t})_{0\leftarrow
R^{\prime}_{t,0}})=\sigma(\ldots,R_{t,-1},R^{\prime}_{t,0},R_{t,1},\ldots)=(\ldots,R^{\prime}_{t,0},$
$\displaystyle R_{t,1},R_{t,2},\ldots).$

In a more compact notation, at time $t+1$ the sequence becomes

$R_{t+1,i}=\begin{cases}R^{\prime}_{t,0}&\text{if }i=-1,\\\ R_{t,i+1}&\text{if
}i\neq-1.\end{cases}$

By induction, for all $t,u,i,j\in\mathbb{Z}^{+}$ satisfying $t+i=u+j$, we have
$R_{t,i}=R_{u,j}$ . In particular,
$R_{t,\mathbb{Z}^{+}}=R_{0,t+\mathbb{Z}^{+}}$; therefore, if the initial dice
$R_{0,\mathbb{Z}}$ are i.i.d., then the unused dice $R_{t,\mathbb{Z}^{+}}$
will continue to be i.i.d. at all later times $t\in\mathbb{Z}^{+}$. As a
result, $C_{t}$’s evolution is time-homogeneous in the direction of increasing
$t$. In contrast, if we were to follow $C_{t}$’s evolution in the direction of
_decreasing_ $t$, toward zero, we would encounter used dice. These dice
correlated with $C_{t}$, in such a way as to return the process to its initial
configuration $C_{0}$.

Let’s get some geometric intuition, using the correspondence $\Psi$ from
Equation 6. It identifies the sequence $R_{t}$ with a point in the unit
square; thus, $(C_{t},R_{t})\in\mathbb{Z}\times(\mathbb{Z}_{4})^{\mathbb{Z}}$
is identified with a point in
$\mathbb{Z}\times[0,1)\times[0,1)\simeq\mathbb{R}\times[0,1)$. The resulting
system is essentially the multibaker chain, first introduced and visualized by
Gaspard [19]. Thanks to $\Psi$, we can think of the sequence

$C_{t},\;R_{t,0},\;R_{t,\pm 1},\;R_{t,\pm 2},\cdots$

as the base-$4$ digits, in order of decreasing significance, of a continuous
state’s coordinates. Although the maps $T,\sigma$ are deterministic and
reversible, their result on $C_{t}$ appears stochastic if we ignore $R_{t}$.
$\sigma$ is chaotic, gradually amplifying formerly insignificant figures in
the real-valued coordinates of $R_{t}$. $T$ uses these as a source of
randomness to evolve $C_{t}$. Since real numbers have infinitely many digits,
they can provide an endless supply of entropy by repeating $\sigma$.

More generally, we can view any time-homogeneous Markov chain $\mathbf{C}$ as
the macroscopic part of some chaotic dynamical system
$(\mathbf{C},\mathbf{R})$. The initial microscopic variables
$(R_{0,i})_{i\in\mathbb{Z}}$ are i.i.d. samples from a probability space
$(\mathcal{R},\mathcal{G},\Gamma)$. Adapting Equation 5 to symbols in
$\mathcal{R}$, the shift map
$\sigma:\mathcal{R}^{\mathbb{Z}}\rightarrow\mathcal{R}^{\mathbb{Z}}$ is again
defined by $\sigma(r)_{t}:=r_{t+1}$. Given a macroscopic transition function
$T:\mathcal{S}\times\mathcal{R}\rightarrow\mathcal{S}\times\mathcal{R}$, the
full dynamics
$\overline{T}:\mathcal{S}\times\mathcal{R}^{\mathbb{Z}}\rightarrow\mathcal{S}\times\mathcal{R}^{\mathbb{Z}}$
are given by

$\displaystyle\overline{T}(s,r):=(s^{\prime},\sigma(r_{0\leftarrow
r^{\prime}})),\text{ where }(s^{\prime},r^{\prime}):=T(s,r_{0}).$ (19)

In other words, $\overline{T}$ first applies $T$ to $(s,r_{0})$, and then
applies $\sigma$ to the entire sequence $r$. In the following definition, let
$\mathrm{Dyn}(\mathcal{S})$ denote the class of all tuples of the form
$(\mathcal{R},\mathcal{G},\Gamma,T)$, where $(\mathcal{R},\mathcal{G},\Gamma)$
is a probability space, and
$T:\mathcal{S}\times\mathcal{R}\rightarrow\mathcal{S}\times\mathcal{R}$ is
$(2^{\mathcal{S}}\times\mathcal{G})$-measurable.

######  Definition 8.

The deterministic function presentation of time-homogeneous Markov chains on
$\mathcal{S}$ is the map

$\Phi_{\mathrm{determ}}:\mathcal{M}_{1}(\mathcal{S})\times\mathrm{Dyn}(\mathcal{S})\rightarrow\mathrm{Markov}(\mathcal{S}),$

defined as follows. Consider any initial condition
$\mu\in\mathcal{M}_{1}(\mathcal{S})$ and deterministic dynamics
$(\mathcal{R},\mathcal{G},\Gamma,T)\in\mathrm{Dyn}(\mathcal{S})$. Let the
random variables $(\mathbf{C},\mathbf{R})=(C_{t},R_{t})_{t\in\mathbb{Z}^{+}}$
be distributed such that

$\displaystyle\mathbb{P}_{(C_{0},R_{0})}$
$\displaystyle=\mu\times\Gamma^{\mathbb{Z}},$ (20)
$\displaystyle(C_{t+1},R_{t+1})$
$\displaystyle=\overline{T}(C_{t},R_{t})\qquad\forall t\in\mathbb{Z}^{+},$
(21)

with $\overline{T}$ defined by Equation 19. Then,
$\Phi_{\mathrm{determ}}(\mu,\mathcal{R},\mathcal{G},\Gamma,T):=\mathbb{P}_{\mathbf{C}}.$

We proceed to this section’s main result, establishing a general
correspondence between the deterministic function and transition matrix
presentations. In order to continue thinking of the microscopic variables
$\mathbf{R}$ as base-$m$ digits of real-valued phase coordinates, we prefer
the probability space $(\mathcal{R},\mathcal{G},\Gamma)$ to be the fair
$m$-sided die $(\mathbb{Z}_{m},2^{\mathbb{Z}_{m}},\frac{1}{m}\sharp)$. A
necessary and sufficient condition for the existence of such a presentation,
is that the transition matrix $p$ be $m$-sided.

As an analogue of Liouville’s theorem, we also prefer $\overline{T}$ to be
reversible and $(\pi\times\Gamma^{\mathbb{Z}})$-measure-preserving, for some
$\pi\in\mathcal{M}_{+}(\mathcal{S})$. By Equation 19, these properties hold
iff $T$ is reversible and $(\pi\times\Gamma)$-measure-preserving.

######  Theorem 3.

For every $(\mathcal{R},\mathcal{G},\Gamma,T)\in\mathrm{Dyn}(\mathcal{S})$,
there is a _unique_ $p\in\mathrm{SM}(\mathcal{S})$ such that, for all
$\mu\in\mathcal{M}_{1}(\mathcal{S})$,
$\Phi_{\mathrm{matrix}}(\mu,p)=\Phi_{\mathrm{determ}}(\mu,\mathcal{R},\mathcal{G},\Gamma,T)$.
If $T$ is $(\pi\times\Gamma)$-measure-preserving, then
$p\in\mathrm{SM}_{\pi}(\mathcal{S})$. If $\Gamma$ is $m$-sided, then so is
$p$.

Conversely, for every $p\in\mathrm{SM}(\mathcal{S})$, there exists
$(\mathcal{R},\mathcal{G},\Gamma,T)\in\mathrm{Dyn}(\mathcal{S})$ such that,
for all $\mu\in\mathcal{M}_{1}(\mathcal{S})$,
$\Phi_{\mathrm{matrix}}(\mu,p)=\Phi_{\mathrm{determ}}(\mu,\mathcal{R},\mathcal{G},\Gamma,T)$.
If $p\in\mathrm{SM}_{\pi}(\mathcal{S})$, with $\pi$ strictly positive and
finite-sided, then $T$ can be chosen to be bijective and
$(\pi\times\Gamma)$-measure-preserving. If $p$ is $m$-sided, then
$(\mathcal{R},\mathcal{G},\Gamma)$ can be chosen to be the fair $m$-sided die,
with $T$ simultaneously being bijective if $p\in\mathrm{DM}(\mathcal{S})$.

The proof is based on that of Theorem 2, and is detailed in Appendix A.

Theorem 3 expresses every time-homogeneous Markov chain as the macroscopic
component of a deterministic system, whose dynamics are given by Equation 19.
Conversely, in every dynamical system of this form, the macroscopic component
is a time-homogeneous Markov chain. While the dynamics of real physical
systems may take other forms, many of them are likewise believed to closely
approximate time-homogeneous Markov chains [10].

For ease of analysis, we base our modeling on Equation 19. In order to build
further intuition on time and reversibility, the following subsections
demonstrate some basic applications. More sophisticated applications, which
require the theory of Section V, are postponed until Section VI.

###  IV.4 The Past Hypothesis

Consider Albert’s [35] proposal that the arrow of time requires a Past
Hypothesis, i.e., a special initial condition. Within our model, we can
investigate exactly which initial conditions are suitable. Theorem 1 says that
the entropy of a Markov chain, with respect to a fixed stationary distribution
$\pi$, cannot decrease. If we want entropy to actually increase rather than
stay fixed, it’s necessary for $\mu$ to have less than maximal entropy.
However, sub-maximal entropy alone is insufficient: if the underlying dynamics
have a CPT-like symmetry, any configuration that exhibits sub-maximal and
increasing entropy, can be converted into one in which entropy is sub-maximal
but _decreasing_.

A closer look at the initial distribution
$\bar{\mu}=\mu\times\Gamma^{\mathbb{Z}}$ from Equation 20 reveals that its
microscopic component is assumed to have the special form
$\Gamma^{\mathbb{Z}}$. In the case of the fair $m$-sided die, we saw that
$\Psi$ maps this to the uniform distribution on
$\mathcal{S}_{\mathrm{baker}}$. This agrees with Albert’s Mentaculus, in which
the starting distribution is assumed to be uniform over some macrostate.

In fact, we can relax the form of the initial distribution $\bar{\mu}$: it’s
sufficient that it be absolutely continuous with respect to
$\sharp\times\Gamma^{\mathbb{Z}}$, meaning that it can be written
$d\bar{\mu}=f\,d(\sharp\times\Gamma^{\mathbb{Z}})$. Here,
$f:\mathcal{S}\times\mathcal{R}^{\mathbb{Z}}\rightarrow\mathbb{R}^{+}$ is
called the Radon-Nikodym derivative, or probability density function, of
$\bar{\mu}$ with respect to $\sharp\times\Gamma^{\mathbb{Z}}$. Explicitly,
this means that for all $A\in 2^{\mathcal{S}}\times\mathcal{G}^{\mathbb{Z}}$,

$\bar{\mu}(A):=\int_{A}f\,d(\sharp\times\Gamma^{\mathbb{Z}})=\sum_{s\in\mathcal{S}}\int_{\\{r\in\mathcal{R}^{\mathbb{Z}}:\,(s,r)\in
A\\}}f(s,r)\,d\Gamma^{\mathbb{Z}}(r).$ (22)

When $\bar{\mu}$ has this form, to an increasingly good approximation as $t$
gets large, $\mathbf{C}$ behaves like a time-homogeneous Markov chain. To
prove it, we first need a technical lemma. In measure theory, a semiring of
sets is a collection of sets $\mathcal{A}$, such that
$\emptyset\in\mathcal{A}$ and, for all $A,B\in\mathcal{A}$, $A\cap B$ is in
$\mathcal{A}$ and $A\setminus B$ is a finite disjoint union of elements of
$\mathcal{A}$. We show that probability density functions can be approximated
by finite linear combinations of characteristic functions on a semiring.

######  Lemma 3.

Let $(\Omega,\mathcal{F},\mu)$ be a $\sigma$-finite measure space, let
$\mathcal{A}$ be a semiring of sets generating $\mathcal{F}$, and let
$f:\Omega\rightarrow\mathbb{R}^{+}$ be a probability density with respect to
$\mu$, i.e., $\int_{\Omega}f\,d\mu=1$. Then, for all $\varepsilon>0$, there
exist $k\in\mathbb{Z}^{+}$ and $(\alpha_{i},A_{i})_{i=1}^{k}$, with
$\alpha_{i}>0$ and the sets $A_{i}\in\mathcal{A}$ mutually disjoint, such that
$g:=\sum_{i=1}^{k}\alpha_{i}\mathbf{1}_{A_{i}}$ is a probability density with
respect to $\mu$, satisfying

$\displaystyle\int_{\Omega}\left|f-g\right|\,d\mu$
$\displaystyle<\varepsilon.$ (23)

###### Proof.

By definition of the Lebesgue integral, $f$ can be approximated by a finite
linear combination of characteristic functions of sets in $\mathcal{F}$. By
the measure approximation theorem [49, Thm 1.65(ii)], these characteristic
functions can themselves be approximated by finite linear combinations of
characteristic functions of sets in $\mathcal{A}$; putting them together
yields Equation 23. Since semirings are closed under set difference and
intersection, the sets $A_{i}$ can be made disjoint. Furthermore, Equation 23
implies that

$\left|1-\int_{\Omega}g\,d\mu\right|=\left|\int_{\Omega}(f-g)\,d\mu\right|\leq\int_{\Omega}|f-g|\,d\mu<\varepsilon,$

so $g$ is almost a probability density. Normalizing $g$ increases the error in
Equation 23 to at most $2\varepsilon$; since $\varepsilon$ was arbitrary, the
proof is finished. ∎

######  Theorem 4.

Suppose $(\mathcal{R},\mathcal{G},\Gamma,T)\in\mathrm{Dyn}(\mathcal{S})$, and
consider the generalized initial condition
$\bar{\mu}\in\mathcal{M}_{1}(\mathcal{S}\times\mathcal{R}^{\mathbb{Z}})$,
defined by $d\bar{\mu}=f\,d(\sharp\times\Gamma^{\mathbb{Z}})$ for some
probability density function
$f:\mathcal{S}\times\mathcal{R}^{\mathbb{Z}}\rightarrow\mathbb{R}^{+}$. Let
the random variables
$(\mathbf{C},\mathbf{R})=(C_{t},R_{t})_{t\in\mathbb{Z}^{+}}$ be distributed
such that

$\displaystyle\mathbb{P}_{(C_{0},R_{0})}$ $\displaystyle=\bar{\mu},$ (24)
$\displaystyle(C_{t+1},R_{t+1})$
$\displaystyle=\overline{T}(C_{t},R_{t})\qquad\forall t\in\mathbb{Z}^{+},$
(25)

with $\overline{T}$ defined by Equation 19. Then,

$\lim_{t\rightarrow\infty}\lVert\mathbb{P}_{C_{\geq
t}}-\Phi_{\mathrm{determ}}(\mathbb{P}_{C_{t}},\mathcal{R},\mathcal{G},\Gamma,T)\rVert_{\mathrm{TV}}=0,$

and the convergence rate is uniform in the choice of transition function $T$.

###### Proof.

Let $\mathcal{A}$ consist of all subsets of
$\mathcal{S}\times\mathcal{R}^{\mathbb{Z}}$ that are of the form

$B^{\prime}\times\prod_{i\in\mathbb{Z}}B_{i},$ (26)

where $B^{\prime}\subset\mathcal{S}$, $B_{i}\in\mathcal{G}$, and, for all but
finitely many $i\in\mathbb{Z}$, $B_{i}=\mathcal{R}$. $\mathcal{A}$ is the
semiring of cylinder sets generating the $\sigma$-algebra
$2^{\mathcal{S}}\times\mathcal{G}^{\mathbb{Z}}$.

Fix the approximation error $\varepsilon>0$. By Lemma 3, there exist positive
coefficients $\alpha_{1},\ldots,\alpha_{k}$ and disjoint sets
$A_{1},\ldots,A_{k}\in\mathcal{A}$, such that the probability measure
$d\bar{\nu}=g\,d(\sharp\times\Gamma^{\mathbb{Z}})$, with density function
$g:=\sum_{j=1}^{k}\alpha_{j}\mathbf{1}_{A_{j}}$, satisfies

$\lVert\bar{\mu}-\bar{\nu}\rVert_{\mathrm{TV}}=\frac{1}{2}\int_{\mathcal{S}\times\mathcal{R}^{\mathbb{Z}}}\left|f-g\right|\,d(\sharp\times\Gamma^{\mathbb{Z}})<\frac{\varepsilon}{2}.$

Now, expressing each of the $A_{j}\in\mathcal{A}$ as in Equation 26, let $t$
be the maximum of $1+|i|$, over all $i\in\mathbb{Z}$ for which at least one of
the $A_{j}$ has $B_{i}\neq\mathcal{R}$ (or $0$ if there is no such $i$). Then,
for each $j=1,\ldots,k$, we can write
$A_{j}=B^{\prime\prime}_{j}\times\mathcal{R}^{\\{i\in\mathbb{Z}:\,|i|\geq
t\\}}$, where $B^{\prime\prime}_{j}\in
2^{\mathcal{S}}\times\mathcal{G}^{\\{i\in\mathbb{Z}:\,|i|<t\\}}$. As a result,
under the distribution $\mathbb{P}^{g}$ defined by

$\displaystyle\mathbb{P}^{g}_{(C_{0},R_{0})}$ $\displaystyle=\bar{\nu},$
$\displaystyle(C_{t+1},R_{t+1})$
$\displaystyle=\overline{T}(C_{t},R_{t})\qquad\forall t\in\mathbb{Z}^{+},$

the “dice” $(R_{0,i})_{|i|\geq t}$ are i.i.d. with marginals $\Gamma$,
independent of the other initial variables. Therefore, starting at time $t$,
$\mathbb{P}^{g}$ becomes a time-homogeneous Markov chain, satisfying

$\mathbb{P}^{g}_{C_{\geq
t}}=\Phi_{\mathrm{determ}}(\mathbb{P}^{g}_{C_{t}},\mathcal{R},\mathcal{G},\Gamma,T).$

Since the initial variables of
$\Phi_{\mathrm{determ}}(\mu,\mathcal{R},\mathcal{G},\Gamma,T)$ are distributed
according to $\mu$, and its subsequent variables evolve independently of
$\mu$, it follows that for all $\mu,\nu\in\mathcal{M}_{1}(\mathcal{S})$,

$\lVert\Phi_{\mathrm{determ}}(\mu,\mathcal{R},\mathcal{G},\Gamma,T)-\Phi_{\mathrm{determ}}(\nu,\mathcal{R},\mathcal{G},\Gamma,T)\rVert_{\mathrm{TV}}=\lVert\mu-\nu\rVert_{\mathrm{TV}}.$

Putting these equations together yields

$\lVert\mathbb{P}^{g}_{C_{\geq
t}}-\Phi_{\mathrm{determ}}(\mathbb{P}_{C_{t}},\mathcal{R},\mathcal{G},\Gamma,T)\rVert_{\mathrm{TV}}=\lVert\mathbb{P}^{g}_{C_{t}}-\mathbb{P}_{C_{t}}\rVert_{\mathrm{TV}},$

which we plug into the triangle inequality to get

$\displaystyle\lVert\mathbb{P}_{C_{\geq
t}}-\Phi_{\mathrm{determ}}(\mathbb{P}_{C_{t}},\mathcal{R},\mathcal{G},\Gamma,T)\rVert_{\mathrm{TV}}$
$\displaystyle\leq\lVert\mathbb{P}_{C_{\geq t}}-\mathbb{P}^{g}_{C_{\geq
t}}\rVert_{\mathrm{TV}}+\lVert\mathbb{P}^{g}_{C_{\geq
t}}-\Phi_{\mathrm{determ}}(\mathbb{P}_{C_{t}},\mathcal{R},\mathcal{G},\Gamma,T)\rVert_{\mathrm{TV}}$
$\displaystyle=\lVert\mathbb{P}_{C_{\geq t}}-\mathbb{P}^{g}_{C_{\geq
t}}\rVert_{\mathrm{TV}}+\lVert\mathbb{P}_{C_{t}}-\mathbb{P}^{g}_{C_{t}}\rVert_{\mathrm{TV}}$
$\displaystyle\leq
2\lVert\mathbb{P}_{(C_{0},R_{0})}-\mathbb{P}^{g}_{(C_{0},R_{0})}\rVert_{\mathrm{TV}}$
$\displaystyle=2\lVert\bar{\mu}-\bar{\nu}\rVert_{\mathrm{TV}}$
$\displaystyle<\varepsilon,$

where the middle inequality holds because Equation 25 makes $\mathbf{C}$ a
deterministic function of $(C_{0},R_{0})$. Since $\varepsilon$ did not depend
on $T$, taking $\varepsilon\rightarrow 0$ proves the uniform convergence. ∎

For some intuition regarding the proof of Theorem 4, consider the case where
$(\mathcal{R},\mathcal{G},\Gamma)$ is the fair $m$-sided die. Using $\Psi$,
identify $\mathcal{R}^{\mathbb{Z}}$ with the unit square, so that
$\mathcal{G}^{\mathbb{Z}},\Gamma^{\mathbb{Z}}$ become its Borel
$\sigma$-algebra and Lebesgue (i.e., area) measure, respectively. The cylinder
sets $A_{j}\in\mathcal{A}$ become finite unions of squares whose vertices have
$m$-adic rational coordinates. The absolutely continuous distribution
$\bar{\mu}$ is “spread out” in such a way that it appears uniform at scales
smaller than the $A_{j}$’s. After enough iterations of stretching by the
baker’s map, the $x$ coordinate becomes uniform on large scales as well. $T$
only looks at a coarse description of the $x$ coordinate; thus, for large $t$,
it yields essentially Markovian behavior.

Of course, this result would be much less interesting if processes only became
Markovian after attaining heat death. Fortunately, the convergence is uniform
in $T$. Therefore, for fixed $\bar{\mu}$, we can always choose a $T$ that
mixes sufficiently slowly, so that the process becomes Markovian long before
its entropy reaches a maximum.

In summary, Equation 22 provides our general Past Hypothesis. While it allows
for messy behavior in some neighborhood of $t=0$, a stable arrow of time is
sure to emerge eventually for $t\gg 0$. Of course, if $T$ is invertible, then
the argument applies equally well in reverse: a stable arrow of time must also
emerge in the opposite direction for $t\ll 0$. By Theorem 4, the forward
dynamics are ultimately determined by $(\mathcal{R},\mathcal{G},\Gamma,T)$,
while the backward dynamics are ultimately determined by
$(\mathcal{R},\mathcal{G},\Gamma,T^{-1})$. By Theorem 3, each of these
corresponds to some transition matrix; to close out this section, we
investigate how the forward and backward matrices are related.

###  IV.5 Dual Arrows

Fix $\pi\in\mathcal{M}_{+}(\mathcal{S})$ and
$(\mathcal{R},\mathcal{G},\Gamma,T)\in\mathrm{Dyn}(\mathcal{S})$, with $T$
bijective and $(\pi\times\Gamma)$-measure-preserving. Then, $\overline{T}$ is
a deterministic, reversible, chaotic map that acts on the microstate
$(C_{t},R_{t})$. The macroscopic transition probabilities
$\mathbb{P}(C_{t+1}=s^{\prime}\mid C_{t}=s)$ depend on how $R_{t}$ is
distributed. When $R_{t}$ is “uniform” (i.e., its distribution is
$\Gamma^{\mathbb{Z}}$) and independent of $C_{t}$, these probabilities are
given by the unique transition matrix $p\in\mathrm{SM}_{\pi}(\mathcal{S})$
that Theorem 3 assigns to $(\mathcal{R},\mathcal{G},\Gamma,T)$. By Theorem 1,
it follows that $H_{\pi}(C_{t})\leq H_{\pi}(C_{t+1})$.

In Definition 8, $R_{0}$ meets this condition, but $R_{t}$ at later times
tends to become correlated with $C_{t}$. Fortunately, since $T$ thereafter
only encounters the terms $R_{t,\mathbb{Z}^{+}}$, which _are_ uniform and
independent, the forward dynamics continue to abide by $p$. Thus, $R_{t}$ has
the remarkable property that it appears well-mixed for the purposes of forward
evolution, but not for the purposes of backward evolution. Indeed, using
Theorem 3 to pass to the transition matrix presentation, Equation 14 shows
that the backward probabilities are inhomogeneous.

As an intuition-building (albeit unrealistic) thought experiment, we can
imagine perturbing an arbitrary microstate $(C_{t},R_{t})$, perhaps
corresponding to the present state of the Universe. That is, without changing
$C_{t}$, we replace $R_{t}$ with a random sample from $\Gamma^{\mathbb{Z}}$
777By Theorem 4, more general perturbations would yield similar results..
Since $\overline{T}$ is chaotic, the evolution of $C_{t}$ is highly sensitive
to this microscopic perturbation; nonetheless, the perturbed forward evolution
would still appear _plausible_. To be mathematically precise, the forward
transition probabilities would be unchanged; the new trajectory simply
resamples from the same matrix $p$ as the unperturbed trajectory.

On the other hand, the perturbed backward evolution would appear truly
incredible. The perturbation destroys any correlations in $R_{t}$ that would
otherwise conspire to restore the past’s low entropy. Reversible phenomena,
such as celestial orbits, would rewind to their former configurations
relatively unharmed. However, thermodynamically irreversible events would fail
to become undone: a shattered vase would no longer enjoy a past in which it
was whole, nor would a fried egg return to its raw origins (perhaps it would
overcook on the pan instead). We do not presume to guess how bizarrely life on
Earth would be afflicted by such a reversal in the arrow of time.

However, the new trajectory can be understood in basic terms. Making $R_{t}$
uniform restores a symmetry between $t$’s past and future: applying Theorem 3
to $(\mathcal{R},\mathcal{G},\Gamma,T)$ and
$(\mathcal{R},\mathcal{G},\Gamma,T^{-1})$, respectively, we find that the
forward and backward dynamics are both homogeneous in time, corresponding to
two different transition matrices.

We now show that these matrices are dual to each other. Recall that, for fixed
$\pi\in\mathcal{M}_{+}(\mathcal{S})$, the dual of a stochastic matrix
$p\in\mathrm{SM}_{\pi}(\mathcal{S})$ is defined by Equation 15. If $p$ is
recurrent, then it uniquely determines $\pi$, hence also $p_{\mathrm{dual}}$;
otherwise, the choice of $\pi$ must be clarified by context.

By introducing one additional piece of notation, we can also reverse the
random function presentation. For
$\Gamma\in\mathcal{M}_{1}(\mathrm{Bij}(\mathcal{S}))$, define
$\Gamma_{\mathrm{dual}}\in\mathcal{M}_{1}(\mathrm{Bij}(\mathcal{S}))$ by
$\Gamma_{\mathrm{dual}}(A):=\Gamma(\\{f\in\mathrm{Bij}(\mathcal{S}):\,f^{-1}\in
A\\})$. In other words, $\Gamma_{\mathrm{dual}}$ samples a bijection from
$\Gamma$ and inverts it.

######  Theorem 5.

Fix $\mu\in\mathcal{M}_{1}(\mathcal{S})$. Suppose
$p\in\mathrm{DM}(\mathcal{S})$ and
$\Gamma\in\mathcal{M}_{1}(\mathrm{Bij}(\mathcal{S}))$. If
$\Phi_{\mathrm{matrix}}(\mu,p)=\Phi_{\mathrm{random}}(\mu,\Gamma)$, then
$\Phi_{\mathrm{matrix}}(\mu,p_{\mathrm{dual}})=\Phi_{\mathrm{random}}(\mu,\Gamma_{\mathrm{dual}})$.

Alternatively, suppose $\pi\in\mathcal{M}_{+}(\mathcal{S})$ is strictly
positive, $p\in\mathrm{SM}_{\pi}(\mathcal{S})$, and
$(\mathcal{R},\mathcal{G},\Gamma,T)\in\mathrm{Dyn}(\mathcal{S})$, with $T$
bijective and $(\pi\times\Gamma)$-measure-preserving. If
$\Phi_{\mathrm{matrix}}(\mu,p)=\Phi_{\mathrm{determ}}(\mu,\mathcal{R},\mathcal{G},\Gamma,T)$,
then
$\Phi_{\mathrm{matrix}}(\mu,p_{\mathrm{dual}})=\Phi_{\mathrm{determ}}(\mu,\mathcal{R},\mathcal{G},\Gamma,T^{-1})$.

###### Proof.

Since $\mathrm{DM}(\mathcal{S})=\mathrm{SM}_{\sharp}(\mathcal{S})$, the
implied choice of stationary measure in the first part is $\sharp$; hence, the
dual matrix in Equation 15 is simply the transpose of $p$. Let
$(\mathbf{C},\mathbf{F})$ be as in Definition 7, so that
$\mathbb{P}_{\mathbf{C}}=\Phi_{\mathrm{random}}(\mu,\Gamma_{\mathrm{dual}})$.
Then, since $F_{t}$ is independent of $C_{\leq t}$,

$\displaystyle\mathbb{P}(C_{t+1}=c_{t+1}\mid C_{\leq t}=c_{\leq t})$
$\displaystyle=\mathbb{P}(F_{t}(c_{t})=c_{t+1})$
$\displaystyle=\Gamma_{\mathrm{dual}}(\\{f\in\mathrm{Bij}(\mathcal{S}):\,f(c_{t})=c_{t+1}\\})$
$\displaystyle=\Gamma(\\{f\in\mathrm{Bij}(\mathcal{S}):\,f(c_{t+1})=c_{t}\\})$
$\displaystyle=p(c_{t+1},c_{t})$
$\displaystyle=p_{\mathrm{dual}}(c_{t},c_{t+1}).$

Similarly, under the second set of hypotheses, let $(\mathbf{C},\mathbf{R})$
be as in Definition 8, so that
$\mathbb{P}_{\mathbf{C}}=\Phi_{\mathrm{determ}}(\mu,\mathcal{R},\mathcal{G},\Gamma,T^{-1})$.
Since $R_{t,0}=R_{0,t}$ is independent of $C_{\leq t}$,

$\displaystyle\pi(c_{t})\mathbb{P}(C_{t+1}=c_{t+1}\mid C_{\leq t}=c_{\leq t})$
$\displaystyle=\pi(c_{t})\mathbb{P}(\exists
a^{\prime}\in\mathcal{R},\,T^{-1}(c_{t},R_{0,t})=(c_{t+1},a^{\prime}))$
$\displaystyle=\pi(c_{t})\mathbb{P}(\exists
a^{\prime}\in\mathcal{R},\,T(c_{t+1},a^{\prime})=(c_{t},R_{0,t}))$
$\displaystyle=(\pi\times\Gamma)(\\{c_{t}\\}\times\\{a\in\mathcal{R}:\,\exists
a^{\prime}\in\mathcal{R},T(c_{t+1},a^{\prime})=(c_{t},a)\\})$
$\displaystyle=(\pi\times\Gamma)((\\{c_{t}\\}\times\mathcal{R})\cap
T(\\{c_{t+1}\\}\times\mathcal{R}))$
$\displaystyle=(\pi\times\Gamma)((\\{c_{t+1}\\}\times\mathcal{R})\cap
T^{-1}(\\{c_{t}\\}\times\mathcal{R}))$
$\displaystyle=(\pi\times\Gamma)(\\{c_{t+1}\\}\times\\{a\in\mathcal{R}:\,\exists
a^{\prime}\in\mathcal{R},\,T(c_{t+1},a)=(c_{t},a^{\prime})\\})$
$\displaystyle=\pi(c_{t+1})p(c_{t+1},c_{t}).$

Therefore,

$\mathbb{P}(C_{t+1}=c_{t+1}\mid C_{\leq t}=c_{\leq
t})=\frac{\pi(c_{t+1})}{\pi(c_{t})}p(c_{t+1},c_{t})=p_{\mathrm{dual}}(c_{t},c_{t+1}).$

∎

In light of Theorem 5, it’s natural to extend Equations 12 and 13 with the
dual Equation 16. That is, given $\mu\in\mathcal{M}_{1}(\mathcal{S})$ and a
recurrent matrix $p\in\mathrm{SM}(\mathcal{S})$, the bidirectional Markov
chain $\mathbf{C}=(C_{t})_{t\in\mathbb{Z}}$ has its joint distribution
uniquely determined by:

$\displaystyle\mathbb{P}(C_{0}=c_{0})$ $\displaystyle=\mu(c_{0}),$
$\displaystyle\mathbb{P}(C_{t+1}=c_{t+1}\mid C_{\leq t}=c_{\leq t})$
$\displaystyle=p(c_{t},c_{t+1})\qquad\quad\,\,\forall t\in\mathbb{Z}^{+},$
$\displaystyle\mathbb{P}(C_{t-1}=c_{t-1}\mid C_{\geq t}=c_{\geq t})$
$\displaystyle=p_{\mathrm{dual}}(c_{t},c_{t-1})\qquad\forall
t\in\mathbb{Z}^{-}.$

$\mathbf{C}$ is effectively two Markov chains glued together at $t=0$, and its
causal graph is Equation 11. When the functions in question are bijective, the
random function and deterministic function presentations have obvious
extensions to negative times. Theorem 5 then extends the correspondences of
Theorems 2 and 3 to bidirectional Markov chains. These might prove helpful for
modeling cosmologies in which the Big Bang is replaced by a temporally
bidirectional Big Bounce.

##  V Stochastic Partitioned Cellular Automata

As a final extension, we supplement the time coordinate with a space
coordinate. The initial condition and dynamics now jointly determine the state
(or its distribution) at every point in spacetime. We say the dynamics are
local if they consist of independent transitions at all points in spacetime;
we say they are homogeneous in space and time, or spacetime-homogeneous, if
the transition matrix is identical at all points. We seek a model whose
forward transitions are both local and spacetime-homogeneous.

In the physical Universe, local interactions propagate no faster than the
speed of light, ensuring a form of causal separation between spacelike
separated events. When viewed in reverse, however, macroscopic events seem to
conspire in a non-local manner: for example, the fragments of a broken vase
rise up simultaneously to reassemble. There is no macroscopic indication that
the fragments are about to rise because, once at rest, the fragments have lost
the _memory_ of their common time of origin. In other words, the fragments
decorrelate from each other when they come to rest.

In this section, we identify a new time-reversal asymmetry, the Memory Law,
which permits spontaneous decorrelation but forbids spontaneous correlation.
It complements the Resource Law, which is a very general and local version of
the second law of thermodynamics.

###  V.1 Core Definitions

We begin by defining our discrete spatial structure. It consists of a set of
positions $\mathcal{X}$ linked by a neighbor relation; in other words, a
graph. We want $\mathcal{X}$ to be homogeneous, meaning that all its elements
should have neighborhoods that “look the same”. To that end, we color the
edges, and require that each $x\in\mathcal{X}$ have one outgoing and one
incoming edge of each color $\tau\in\mathcal{T}$. Thus, each color corresponds
to a bijection on $\mathcal{X}$. By coupling the set of positions
$\mathcal{X}$ with the set of times
$\frac{1}{2}\mathbb{Z}^{+}=\\{0,\frac{1}{2},1,\frac{3}{2},\ldots\\}$, we
obtain the spacetime $\frac{1}{2}\mathbb{Z}^{+}\times\mathcal{X}$. The reason
for including half-integer times will become

clear in Definition 10. Let’s formalize what we have so far.

######  Definition 9.

A homogeneous discrete spatial geometry $(\mathcal{X},\mathcal{T})$ is a set
of spatial positions or cells $\mathcal{X}$, along with a finite set of local
translations or tracks $\mathcal{T}\subset\mathrm{Bij}(\mathcal{X})$. We
assume an identity track: $\mathrm{id}\in\mathcal{T}$. Associated with
$(\mathcal{X},\mathcal{T})$ is the quasimetric

$d(x,y):=\min\\{n\in\mathbb{Z}^{+}:\;\exists\tau_{1},\ldots\tau_{n}\in\mathcal{T},\;\tau_{n}(\ldots(\tau_{1}(x))\ldots)=y\\},$

with $d(x,y):=\infty$ if no such path exists. $d$ is a metric iff
$\mathcal{T}$ is closed under inverses. It determines a partial order on
$\frac{1}{2}\mathbb{Z}^{+}\times\mathcal{X}$: for times
$t,u\in\frac{1}{2}\mathbb{Z}^{+}$ and positions $x,y\in\mathcal{X}$, we write
$(t,x)<(u,y)$ iff $t<u$ and $d(x,y)\leq\lceil u\rceil-\lceil t\rceil$. In this
case, we say $(u,y)$ is reachable from, or in the future of, $(t,x)$, and that
$(t,x)$ is in the past of $(u,y)$.

Also associated with $(\mathcal{X},\mathcal{T})$ is the causal graph
$\mathrm{G}(\mathcal{X},\mathcal{T})$ on the vertex set
$\\{O\\}\cup\left(\frac{1}{2}\mathbb{Z}^{+}\times\mathcal{X}\right)$. It has a
directed edge from $(t,x)$ to $(u,y)$ iff $(t,x)<(u,y)$ and $u=t+\frac{1}{2}$.
To allow for dependences in the initial state, there is also an edge from $O$
to $(0,x)$ for all $x\in\mathcal{X}$.

If either $(t,x)<(u,y)$, $(t,x)=(u,y)$, or $(t,x)>(u,y)$, we say the pairs are
timelike related; otherwise, they are spacelike related. In analogy with light
cones in relativity, for any subset of spacetime
$A\subset\frac{1}{2}\mathbb{Z}^{+}\times\mathcal{X}$, let

$\displaystyle\mathrm{Past}(A)$ $\displaystyle:=\bigcup_{(t,x)\in
A}\left\\{(u,y)\in\frac{1}{2}\mathbb{Z}^{+}\times\mathcal{X}:\;(u,y)<(t,x)\right\\},$
$\displaystyle\mathrm{Future}(A)$ $\displaystyle:=\bigcup_{(t,x)\in
A}\left\\{(u,y)\in\frac{1}{2}\mathbb{Z}^{+}\times\mathcal{X}:\;(u,y)>(t,x)\right\\},$
$\displaystyle\mathrm{NonFut}(A)$
$\displaystyle:=\left(\frac{1}{2}\mathbb{Z}^{+}\times\mathcal{X}\right)\setminus\mathrm{Future}(A).$

It’s easy to check that $\mathrm{G}(\mathcal{X},\mathcal{T})$ has a path from
$(t,x)$ to $(u,y)$ iff $(t,x)<(u,y)$. One example of a spatial geometry is the
infinite grid $\mathcal{X}=\mathbb{Z}^{d}$, equipped with $2d+1$ tracks: the
identity, and the unit displacements. The finite grid
$\mathcal{X}=(\mathbb{Z}_{m})^{d}$ can be made into a spatial geometry using a
periodic variant of the same tracks, connecting at opposite boundaries.

After choosing a spatial geometry, the next step is to define a dynamical
model over it. We have a few options here, with different tradeoffs. For
example, if we wish to study how nature breaks the symmetry between space and
time, then the dynamics should not distinguish between the space and time
axes. For completeness, we include such a model in Appendix B. There, we find
that a spacelike initial condition suffices to break the symmetry, leading to
a macroscopic description in which causality is strictly timelike. To keep
this section simple, however, we take the special status of the time axis for
granted, and seek only to break its symmetry between past and future.

Perhaps the most straightforward model is the ordinary cellular automaton
(CA), whose dynamics compute the state at coordinate
$(t,x)\in\mathbb{Z}^{+}\times\mathcal{X}$, as a function of the previous state
of all neighboring cells $\\{(t-1,\,\tau^{-1}(x)):\;\tau\in\mathcal{T}\\}$.
For our purposes, the CA has two major drawbacks: (1) it combines neighborhood
aggregation and dynamical evolution into a single step, making analysis more
difficult; and (2) the question of whether a given CA is reversible is
undecidable and, even when the answer is affirmative, a CA’s forward and
backward dynamics may require drastically different neighborhood sizes [52].

To solve these issues, Morita and Harao [23] invented the partitioned cellular
automaton (PCA). Both CAs and PCAs are divided into cells $\mathcal{X}$, but
the cells in a PCA are further subdivided along tracks $\mathcal{T}$. Thus,
each pair $(x,\tau)\in\mathcal{X}\times\mathcal{T}$ is the coordinate of a
subcell. The dynamics of a PCA interleave two distinct steps. In a trackwise
translation step, the contents of each subcell $(x,\tau)$ move to
$(\tau(x),\tau)$. Then, in a cellwise evolution step, each cell $x$ evolves
independently of all the others. Thanks to this separation, a PCA is
reversible iff its cellwise evolution rule is. See Kari [24] for a modern
survey of reversible cellular automata, including PCAs.

Just as with the Markov chains in the previous section, we will find
macroscopic views of certain PCAs to have homogeneous transition
probabilities; we call such a view a stochastic partitioned cellular automaton
(SPCA). For the remainder of this section, fix a spatial geometry
$(\mathcal{X},\mathcal{T})$. Additionally, for each track
$\tau\in\mathcal{T}$, fix a countable set $\mathcal{S}_{\tau}$ of fine
macrostates. Subcells on track $\tau$ take states in $\mathcal{S}_{\tau}$;
therefore, a whole cell’s state belongs to
$\mathcal{S}:=\prod_{\tau\in\mathcal{T}}\mathcal{S}_{\tau}$.

An SPCA’s configuration history is a collection of random variables
$\mathbf{C}=(C_{t,x,\tau})_{(t,x,\tau)\in\frac{1}{2}\mathbb{Z}^{+}\times\mathcal{X}\times\mathcal{T}}$,
such that $C_{t,x,\tau}\in\mathcal{S}_{\tau}$ for all $t,x,\tau$. To interpret
$\mathrm{G}(\mathcal{X},\mathcal{T})$ as a graphical model on $\mathbf{C}$,
replace each vertex $(t,x)$ with the corresponding cell $C_{t,x}$. Thus,
$\mathbf{C}$ is Markov relative to $\mathrm{G}(\mathcal{X},\mathcal{T})$ iff
the conditional distribution of each vertex $C_{t,x}$, given all its
nondescendants $C_{\mathrm{NonFut}(t,x)\setminus\\{(t,x)\\}}$, depends only on
its immediate parents. In this case, the joint distribution is uniquely
determined as the product of the conditional distributions. We say that
$\mathbf{C}$ is spacetime-homogeneous if the conditional distributions do not
depend on $t$ or $x$.

Let
$\mathrm{SPCA}(\mathcal{X},\mathcal{T},\mathcal{S})\subset\mathcal{M}_{1}(\mathcal{S}^{\frac{1}{2}\mathbb{Z}^{+}\times\mathcal{X}\times\mathcal{T}})$
denote the set of spacetime-homogeneous distributions that are Markov relative
to $\mathrm{G}(\mathcal{X},\mathcal{T})$ and satisfy the trackwise translation

$\displaystyle
C_{t+\frac{1}{2},\tau(x),\tau}=C_{t,x,\tau}\qquad\forall(t,x,\tau)\in\mathbb{Z}^{+}\times\mathcal{X}\times\mathcal{T}.$
(27)

What data are needed to uniquely determine an element of
$\mathrm{SPCA}(\mathcal{X},\mathcal{T},\mathcal{S})$? Since Equation 27
determines the behavior at half-integer times, it only remains to specify the
behavior at whole-integer times. By homogeneity, and the fact that
$(t,x)\in\mathbb{N}\times\mathcal{X}$ in $\mathrm{G}(\mathcal{X},\mathcal{T})$
has $(t-\frac{1}{2},x)$ as its sole parent, this amounts to choosing a pairing
of initial condition and cellwise evolution. In analogy with Definitions 5, 7