††thanks: author for correspondence<EMAIL_ADDRESS>
# The typical set and entropy in stochastic systems with arbitrary phase space
growth

Rudolf Hanel1,2 and Bernat Corominas-Murtra3 1 Complexity Science Hub Vienna,
Josefstädter Strasse 39, 1080 Vienna, Austria
2 Section for Science of Complex Systems, Medical University of Vienna,
Spitalgasse 23, 1090 Vienna, Austria
3 Institute of Biology, University Graz, Holteigasse 6, A-8010 Graz, Austria

###### Abstract

The existence of the typical set is key for data compression strategies and
for the emergence of robust statistical observables in macroscopic physical
systems. Standard approaches derive its existence from a restricted set of
dynamical constraints. However, given the enormous consequences for the
understanding of the system’s dynamics, and its role underlying the presence
of stable, almost deterministic statistical patterns, a question arises
whether typical sets exist in much more general scenarios. We demonstrate here
that the typical set can be defined and characterized from general forms of
entropy for a much wider class of stochastic processes than it was previously
thought. This includes processes showing arbitrary path dependence, long range
correlations or dynamic sampling spaces; suggesting that typicality is a
generic property of stochastic processes, regardless of their complexity. Our
results impact directly in the understanding of the stability of complex
systems, open the door to new data compression strategies and points to the
existence of statistical mechanics-like approaches to systems arbitrarily away
from equilibrium with dynamic phase spaces. We argue that the potential
emergence of robust properties in complex stochastic systems provided by the
existence of typical sets has special relevance to biological systems.

Entropy, non-exponential phase space growth, Typical set, Asymptotic
Equipartition Property, Extensivity

Many natural systems are characterized by a high degree of internal
stochasticity and for displaying processes leading to forms of organization of
growing complexity Morowitz (1968); Maynard Smith and Szathmáry (1995); Bonner
(1988); Wolpert et al. (2007); Bialek (2012); Solé and Goodwin (2000); Tria et
al. (2014); Loreto et al. (2016); Corominas-Murtra et al. (2018); Iacopini et
al. (2020). Biological systems, at many scales, are paradigmatic examples of
that, triggering the debate whether the existence of open-ended evolution is a
defining trait of them Schuster (1996); Bedau et al. (2000); Ruíz-Mirazo et
al. (2004, 2008); Day (2012); Packard et al. (2019); Pattee and Sayama (2019),
with the resulting challenge for a potential statistical-physics like
characterization. In early embryo morphogenesis, for example, not only the
number of cells increases exponentially in time, resulting into the
corresponding increase of potential configurations, but also cells
differentiate into specialized cell types Wolpert et al. (2007), implying, in
statistical physics language, that new states enter the system. This process
is almost completely irreversible and, although highly precise, is known to
have a strong stochastic component Dietrich and Hiiragi (2007); Maitre et al.
(2016); Giammona and Campàs (2021). On the other side, one can consider
processes with collapsing phase spaces: Away from biology, recent advances in
decay dynamics in nuclear physics succeeded considering a mathematical
framework consisting on the stochastic collapse of the phase space Corominas-
Murtra et al. (2015, 2017); Fujii and Berengut (2021). In figure (1) we
schematically show the processes we are exploring. In spite of the ubiquity of
such phenomena, a comprehensive characterization of systems with dynamic phase
spaces in terms equivalent to the ensemble theory of statistical mechanics is
lacking.

Ensemble formalism in statistical mechanics is grounded on the concept of
typicality Cover and Thomas (2012); Ash (2012); Pathria (2002); Pitowsky
(2012); Lebowitz (1993). Informally speaking, given the set of all potential
sequences of events resulting from a stochastic process, a subset, the typical
set, carries most of the probability Ash (2012); Cover and Thomas (2012). This
should not be confused with the set of most probable sequences: in the case of
the biased coin, for example, the most probable sequence is not in the typical
set. Instead, what it implies is that, for long enough sequences, the
probability that the observed sequence or state belongs to the subset of
sequences forming the typical set goes to $1$. Accordingly, a typical property
for a stochastic system is robust and acts as a strong, almost deterministic
attractor as long as the process unfolds Pitowsky (2012), and one expects to
observe it in the vast majority of cases. Moreover, if such a typical property
exists, one can use this single property to –at least partially– characterize
the system, hence avoiding to go to the detailed, often unaffordable,
microscopic description of all system’s components. Arguably, considerations
based on typicality drive the connection between microscopic dynamics and
macroscopic observables Lebowitz (1993); Battermann (2001); Frigg (2009), and
underlie the existence of the thermodynamic limit and, hence, the consistence
between micro-canonical and canonical ensembles. In the context of information
theory, the existence of the typical set for the outcomes of a given an
information source has deep consequences in the process of data compression
Cover and Thomas (2012); Ash (2012).

Figure 1: (a) Independent drawings of the same dice, either fair or biased,
define a i.i.d. stochastic processes whose typical set is well defined and its
growing is approximately exponential Cover and Thomas (2012). (b) An example
of a system whose typical set may show a super-exponential growth: At every
drawing we update the dice by adding, e.g., a new face. (c) Potential
configurations of early embryo development resembles, intuitively, the picture
of the dice with growing faces. In this biological setting, new cells appear
and, with that, new configurations but, on top of that, cells differentiate
into new types –shown here in red– adding new states in the system that were
not there before. Interestingly, even highly reproducible, the whole process
displays a strong stochastic component Dietrich and Hiiragi (2007). (d)
Nuclear disintegration can be studied from the framework of collapsing phase
spaces Fujii and Berengut (2021). In these processes, the amount of potential
configurations of the system shrinks as long as the process unfolds. Toy
models of embryo packings in (c) have been drawn using the evolver software
package.

The size of the typical set gives us valuable information in relation to the
particular way the stochastic process is filling the phase space. In
equilibrium systems or information sources made of independent drawings of
identically distributed (i.i.d.) random variables, the Gibbs-Shannon entropic
functional arises naturally in the characterization of the typical set Cover
and Thomas (2012); Ash (2012), as the prefactor in the exponential describing
the growth of its volume, establishing a clear connection between
thermodynamics and phase space occupation. In systems/processes with
collapsing or exploding phase spaces, path dependence or strong internal
correlations Kač (1989); Pitman (2006); Clifford and Stirzaker (2008); Tria et
al. (2014); Corominas-Murtra et al. (2015); Loreto et al. (2016); Corominas-
Murtra et al. (2018); Biró and Néda (2018); Jensen et al. (2018); Iacopini et
al. (2020); Korbel et al. (2021), the phase space may grow super- or sub-
exponentially, and the emergence of the Shannon-Gibbs entropic functional
derived from phase space volume occupancy considerations is no longer
guaranteed. The same situation may arise in cases dealing with non-stationary
information sources Gray and Davisson (1974); Visweswariah and Verdu (2000);
Vu and Kass (2009); Boashash and O’Toole (2013); Granero-Belinchón and Garnier
(2019). Generalized forms for entropies have been proposed to encompass these
more general scenarios Abe (2000); Hanel and Thurner (2011a); Enciso and
Tempesta (2017); Tempesta (2016a, b); Thurner et al. (2017); Jizba and Korbel
(2020); Korbel and Jizba (2019); Jizba and Korbel (2017), some of them
explicitly linking the entropic functional to the expected evolution of the
phase space volumes Hanel and Thurner (2011b); Tempesta (2016a); Jensen et al.
(2018); Jensen and Tempesta (2018); Korbel and Thurner (2018); J. Korbel and
Thurner (2020); Hanel and Thurner (2013). In spite notable advances have been
reported even for systems with physical significance Nicholson et al. (2016);
Balogh et al. (2020); Korbel et al. (2021), the concept of typicality has not
been yet explored for systems/processes with exploding or shrinking phase
spaces, displaying path dependent dynamics or subject to internal
correlations.

The purpose of this paper is to fill this important gap in the theory of
stochastic processes, providing results with potential implications in the
theory of non-equilibrium systems and in data compression and coding
strategies. As we shall see, the typical set can be defined for processes
arbitrarily away from the i.i.d. frame, only assuming a very generic
convergence criteria, satisfied by a broad class of stochastic processes, that
here we refer to as compact stochastic processes.

##  I Results

###  I.1 Compact stochastic processes

Let us consider a general class of stochastic processes $\eta$ Gardiner
(1983); Feller (1991). We call this class categorial processes and they
encompass almost any discrete stochastic process that can be conceived. A
realization of $t$ steps of the process is denoted as $\eta(t)$:

$\eta(t)=\eta_{1}\eta_{2}...\eta_{t-1}\eta_{t}\quad,$

where $\eta_{1},\eta_{2}...,\eta_{t-1},\eta_{t}$ are random variables
themselves. Note that, in different realizations of $t$ steps of the process,
the sequence of random variables can be different, as the process may display
path dependence, long term correlations, or changes of the phase space, either
shrinking or expanding. We denote a particular trajectory/path the process may
follow as:

$x(t)\equiv x_{1}x_{2}...x_{t-1}x_{t}\in\Omega(t)\quad,$

$\Omega(t)$ being the set of all possible paths of the process $\eta$ up to
time $t$. We focus on the family of stochastic processes where there exists i)
a positive, strictly concave and strictly increasing function
$\Lambda\in\mathcal{C}^{2}$ in the interval $[1,\infty)$, such that
$\Lambda(1)=0$, and ii) a positive, strictly increasing,
$g\in\mathcal{C}^{2}$, in the interval $(1,\infty)$, by which:

$\displaystyle\lim_{t\to\infty}\frac{1}{g(t)}\Lambda\left(\frac{1}{p(\eta(t))}\right)=1\quad,$
(1)

where the convergence is in probability Feller (1991). We will call this
family of stochastic processes compact stochastic processes (CSP). Given a CSP
process $\eta$, a pair of functions $\Lambda,g$ by which equation (1) is
satisfied define a compact scale of the CSP process $\eta$. Note that these
two functions may not be unique for a given process, meaning that the process
can have several compact scales.

It is straightforward to check that, if $\eta$ is a sequence of i.i.d. random
variables $X_{1},...,X_{t}\sim X$, $\Lambda=\log$ and $g(t)$ is $t$ times the
Shannon entropy of a single realization, $H(X)$, the above condition holds, as
it recovers the standard formulation of the Asymptotic Equipartition Property
(AEP) Ash (2012); Cover and Thomas (2012). Therefore, the drawing of i.i.d.
random variables $\sim X$ is a CSP with compact scale $(\log,H(X)t)$. However,
the range of potential processes is, in principle, much broader. In
consequence, the first question we ask concerns the constraints that the
convergence condition (1) imposes on $\Lambda$. Assuming that (1) holds, one
finds that $\Lambda$’s satisfying the following condition are candidates to
characterize CSP’s –see proposition 1 of the Supplementary Information (SI)
for details:

$\lim_{z\to\infty}\frac{\Lambda(\lambda
z)}{\Lambda(z)}=1\quad,\forall\lambda\in\mathbb{R}^{+}\quad.$ (2)

Typical candidates for $\Lambda$ are of the form $\Lambda(z)=c\log^{d}(z)$,
where $c,d$ are two positive, real valued constants or, more generally:

$\Lambda(z)=c_{1}\log^{d_{1}}(1+c_{2}\log^{d_{2}}(1+c_{3}\log^{d_{3}}(...)))\quad,$

where $c_{1},...$ and $d_{1},...$ are positive, real valued constants. In
previous approaches, these constants have been identified as scaling exponents
that enabled us to classify the different potential growing dynamics of the
phase space Korbel and Thurner (2018).

We observe that for CSP’s, equation (1) directly implies that there are two
non-increasing sequences of positive numbers
$\epsilon_{1},...\epsilon_{t},...$, $\delta_{1},...\delta_{t},...$, with
$\lim_{t\to\infty}\epsilon_{t}=\lim_{t\to\infty}\delta_{t}=0$, from which
there is a subset of paths $A[\epsilon_{t}]\subseteq\Omega(t)$ by which, for
all $x(t)\in A[\epsilon_{t}]$:

$\Lambda^{-1}((1+\epsilon_{t})g(t))\leq
p(x(t))\leq\Lambda^{-1}((1-\epsilon_{t})g(t))\quad,$ (3)

and:

$\mathbb{P}(A[\epsilon_{t}])>1-\delta_{t}\quad.$ (4)

where:

$\mathbb{P}(A[\epsilon_{t}])=\sum_{x(t)\in A[\epsilon_{t}]}p(x(t))\quad.$

We call the sequence of subsets $A[\epsilon_{1}]...A[\epsilon_{t}]$ of the
respective sampling spaces $\Omega(1)...\Omega(t)$ a sequence of typical sets
of $\eta$. Informally speaking, equation (4) tells us that, for large enough
$t$’s, the probability of observing a path that does not belong to the typical
set becomes negligible. In consequence, the typical set can be identified for
CSP’s: Given CSP, the typical set $A[\epsilon_{t}]$ absorbs, in the limit
$t\to\infty$, all the probability –see Theorem 1 of the appendix. We omitted a
direct reference to the process $\eta$ in the notation of the typical set
(i.e.: $A[\epsilon_{t}]\equiv A[\epsilon_{t}](\eta)$) for the sake of
readability. In the sequel we will omit this reference unless it is strictly
necessary. In the next section we provide more details on the specific bounds
in size by studying a subclass of the CCP’s, namely, the class of simple
CCP’s. For them, the characterization of the typical set can be performed from
a generalized form of entropy.

###  I.2 The typical set and generalized entropies

Equation (1) can be related to a general form of path entropy:

$S_{\Lambda}(\eta(t))=\sum_{x(t)\in\Omega(t)}p(x(t))\Lambda\left(\frac{1}{p(x(t))}\right)dx(t)\quad,$
(5)

It can be proven that $S_{\Lambda}$ satisfies three of the four Shannon-
Khinchin axioms expected by an entropic functional Shannon (1948); Khinchin
(1957); Ash (2012) in Khinchin’s formulation Khinchin (1957), to be referred
as SK1, SK2, SK3. In particular SK1 states that entropy must be a function of
the probabilities, which is satisfied by $S_{\Lambda}$, by construction. SK2
states that $S_{\Lambda}$ is maximized by the uniform distribution $q$ over
$\Omega(t)$, i.e.:

$q(x(t))=\frac{1}{|\Omega(t)|}\quad.$

We further observe that $S_{\Lambda}$ is a monotonously increasing function as
well, in the case of uniform probabilities: Let us suppose two CSP’s $\eta$
and $\eta^{\prime}$ that sample uniformly their respective sampling spaces,
$\Omega(t),\Omega^{\prime}(t)$, such that $|\Omega(t)|<|\Omega^{\prime}(t)|)$.
Let, in consequence, $q$ and $q^{\prime}$ be the uniform distributions over
$\Omega(t)$ and $\Omega^{\prime}(t)$, respectively, then:

$S_{\Lambda}(q)=\Lambda\left(|\Omega(t)|\right)<\Lambda\left(|\Omega^{\prime}(t)|\right)=S_{\Lambda}(q^{\prime})\quad,$

where $S_{\Lambda}(q),S_{\Lambda}(q^{\prime})$ are the generalized entropies
as defined in equation (5) applied to distributions $q$ and $q^{\prime}$.
Finally, SK3 states that, if $p(x(t))=0$, then $p(x(t))$ does not contribute
to the entropy, which implies:

$\lim_{p(x(t))\to 0}p(x(t))\Lambda\left(\frac{1}{p(x(t))}\right)=0\quad,$

satisfied as well for any $\Lambda$ considered in the definition of the CSP’s.
In the proposition 3 of the SI we provide details of the above derivations. We
observe that SK4 is not generally satisfied: This axiom states that
$S(AB)=S(A)+S(B|A)$, and one can only guarantee its validity in the case of
Shannon entropy, where $\Lambda=\log$. In the general case, this condition may
not be satisfied. A different arithmetic rule can substitute SK4 to accomodate
other entropic forms Tempesta (2016a). Notice, however, that the use of
Shannon (path) entropy –i.e., $\Lambda=\log$– in the compact scale of a CSP
may be used in a very general case, including systems with correlations or
super-exponential sample space growth, as we will see in section I.3.

If the contributions to the above entropy of the paths belonging to the
complementary set of $A[\epsilon_{t}]$, $\Omega(t)\setminus A[\epsilon_{t}]$
are negligible in the limit of $t\to\infty$, then we call the CSP simple. In
the case of simple CSP’s, the convergence condition (1) can be rewritten as:

$\displaystyle\lim_{t\to\infty}\left|\frac{1}{g(t)}\Lambda\left(\frac{1}{p(\eta(t))}\right)-\frac{S_{\Lambda}(\eta(t))}{g(t)}\right|=0\quad,$
(6)

(in probability). In consequence:

$\frac{S_{\Lambda}(\eta(t))}{g(t)}\to 1\quad.$ (7)

In the theorem 2 of the SI we demonstrate this general result. Once condition
(6) is satisfied, the typical set can be naturally defined for CSP’s in terms
of the generalized entropy $S_{\Lambda}$. We first reword condition (6) as
follows: Given a simple CSP $\eta$, there are two non-increasing sequences of
positive numbers $\epsilon_{1},...\epsilon_{t},...$,
$\delta_{1},...\delta_{t},...$, with
$\lim_{t\to\infty}\epsilon_{t}=\lim_{t\to\infty}\delta_{t}=0$, by which:

$\mathbb{P}\left(\left|\frac{1}{S_{\Lambda}(\eta(t))}\Lambda\left(\frac{1}{p(x(t))}\right)-1\right|>\epsilon_{t}\right)<\delta_{t}\quad.$
(8)

If condition (8) applies, for each $t>0$ there is a set of paths, the typical
set $A[\epsilon_{t}]\subseteq\Omega(t)$, defined as:

$A[\epsilon_{t}]=\left\\{x(t)\in\Omega(t)\mathrel{\mathop{\mathchar
58\relax}}\left|\frac{1}{S_{\Lambda}(\eta(t))}\Lambda\left(\frac{1}{p(x(t))}\right)-1\right|<\epsilon_{t}\right\\},$
(9)

by which $\mathbb{P}(A[\epsilon_{t}])>1-\delta_{t}$. Notice that, now, the
characterization of the typical set is made using the generalized entropy
$S_{\Lambda}$.

The next obvious question refers to the cardinality of the typical set
$|A[\epsilon_{t}]|$. We will see that it can be bounded by above and below in
a way analogous to the standard one Cover and Thomas (2012). We can provide
the first bound by observing that:

$\displaystyle 1-\epsilon_{t}$ $\displaystyle\leq$ $\displaystyle\sum_{x(t)\in
A[\epsilon_{t}]}p(x(t))$ $\displaystyle\leq$
$\displaystyle\frac{|A[\epsilon_{t}]|}{\Lambda^{-1}((1-\epsilon_{t})S_{\Lambda}(\eta(t)))}\quad,$

where $\Lambda^{-1}$ is the inverse function of $\Lambda$, i.e.,
$(\Lambda^{-1}\circ\Lambda)(z)=z$, which exists given the assumption that
$\Lambda$ is a monotonously growing function made in the definition of CSP’s.
From that, it follows that the cardinality of the typical set is bounded from
below as:

$|A[\epsilon_{t}]|\geq(1-\epsilon)\Lambda^{-1}((1-\epsilon)S_{\Lambda}(\eta(t)))\quad.$
(10)

For the upper bound, we observe that:

$\displaystyle 1$ $\displaystyle\geq$ $\displaystyle\sum_{x(t)\in
A[\epsilon_{t}]}p(x(t))$ $\displaystyle\geq$
$\displaystyle\frac{|A[\epsilon_{t}]|}{\Lambda^{-1}((1+\epsilon_{t})S_{\Lambda}(\eta(t)))}\quad,$

leading to:

$|A[\epsilon_{t}]|\leq\Lambda^{-1}((1+\epsilon)S_{\Lambda}(\eta(t)))\quad.$
(11)

Given the bounds provided in equations (10) and (11), one can (roughly)
estimate the volume of the typical set as –see proposition 4 of the SI for
details:

$|A[\epsilon_{t}]|\approx\Lambda^{-1}(S_{\Lambda}(\eta(t)))\quad.$ (12)

The above equation gives us the opportunity of rewriting the entropy in a
Boltzmann-like form. Identifying the cardinality of the typical set as the
effective number of alternatives the system can achieve, one can write:

$S_{\Lambda}(\eta(t))\sim\Lambda(|A[\epsilon_{t}]|)\quad.$

Finally, we notice that we can (roughly) approximate the typical probabilities
as:

$p(x(t))\approx\frac{1}{\Lambda^{-1}(S_{\Lambda}(\eta(t)))}\quad.$

We thus provided a general proof that the typical set exists and that it can
be properly defined for a wide class of stochastic processes, the CSP’s, those
satisfying convergence condition (1). Moreover, we show that its volume can be
bounded and fairly approximated as a function of the generalized entropy
emerging from the convergence condition, $S_{\Lambda}$, as defined in equation
(5).

###  I.3 Example: A path dependent process

Figure 2: The rules of the Chinese restaurant process with memory. Here green
circles represent occupied tables and grey circles empty tables –notice that
in the mathematical formulation of the problem the number of tables is
infinite. Arrows depict the possible transitions of the process and the
associated probabilities.  Figure 3: Numerical simulations for the Chinese
Restaurant process with memory. The blue cloud represents actual numerical
outcomes, dashed orange line the theoretical prediction. Time is given in
arbitrary coordinates, representing a step in the process. In (a) we show the
evolution of the amount of occupied tables against the prediction
$m(t)\sim\sqrt{2t}$. (b) The evolution of Shannon path entropy for the CRPM,
being the prediction given in (13). The dashed red line shows the function
$g(t)\sim\frac{t}{2}\log t$. (c) Evolution of the generalized path entropy
$S_{\Lambda}$, with $\Lambda$ as defined in equation (16). Numerical outcomes
have been obtained from $1000$ replicas of the whole CRPM process up to
$t=10^{4}$ steps.

We briefly explore the behaviour of the typical set and its associated
entropic forms through a model displaying both path dependence and unbounded
growth of the phase space. The process $\eta$ works as follows: Let us suppose
we have a restaurant with an infinite number of tables $m_{1},....,m_{n},...$.
At $t_{0}=0$ a customer enters the restaurant and sits at table $m_{1}$. At
time $t$ a new customer enters the restaurant where already $m(t)$ tables are
occupied –occupation number of each table is unbounded. The customer can chose
either sitting in an already occupied table from the $m_{1},...,m_{m(t)}$
occupied tables, each with equal probability $\frac{1}{m(t)+1}$, or in the
next unoccupied one, $m_{m(t)+1}$, again with probability $\frac{1}{m(t)+1}$.
This process is a version of the so-called Chinese restaurant process Pitman
(2006); Bassetti et al. (2009) with a minimal ingredient of memory/path
dependence. Hence, we refer to it as the Chinese restaurant process with
memory (CRPM). In figure (2) we sketch the rules of this process. Crucially,
as $t\to\infty$, the random variable accounting for the number of tables
$m(t)$ has the following convergent behaviour –see proposition 6 of the SI for
details:

$\frac{m(t)}{\sqrt{2t}}\to 1\quad.$

In figure (3a) we see that the prediction $m(t)\sim\sqrt{2t}$ is quite
accurate when confronted to numerical simulations of the process. This
property enables us to demonstrate that the CRPM we are studying is actually a
CSP with compact scale $(\log,\frac{t}{2}\log t)$ –see theorem 3 of the SI. In
particular, equation (1) is satisfied, in this particular case as:

$\lim_{t\to\infty}\frac{1}{\frac{t}{2}\log
t}\log\left(\frac{1}{p(\eta(t))}\right)=1\quad,$

in probability. In addition, the process is simple –see theorem 4. Since we
are using $\Lambda=\log$, the entropy form that will arise is Shannon path
entropy, by direct application of equation 5, i.e.,
$S_{\Lambda}(\eta(t))=H(\eta(t))$, with $H(\eta(t))$ defined as:

$H(\eta(t))=-\sum_{x(t)\in\Omega(t)}p(x(t))\log p(x(t))\quad.$ (13)

In consequence,

$\frac{H(\eta(t))}{\frac{t}{2}\log t}\to 1\quad.$ (14)

Given the compact scale used, one can estimate the evolution of the size of
the typical set as:

$|A[\epsilon_{t}]|\sim\sqrt{\Gamma(t)}\quad,$ (15)

where $\Gamma$ is the standard $\Gamma$-function Abramowitz and Stegun (1964).
We see that the growth of the typical set as shown in equation (15) is clearly
faster than exponential. In addition, in figure (3b) we see that the
prediction made in equation (14) fits perfectly with the numerical
realizations of the process. Note that we have shown the dependence on Shannon
path entropy for the clarity in the exposition. Indeed, as pointed out above,
a CCP $\eta$ may have several compact scales. For example, taking the compact
scale that led to Shannon entropy, $(\log,g(t))$, with $g(t)=\frac{t}{2}\log
t$, one can construct another compact scale for the CRPM by composing $g^{-1}$
–which, by assumption, exists– to both functions. In consequence, one will
have a new compact scale $(\Lambda,\tilde{g})$, defined as:

$\Lambda(t)=(g^{-1}\circ\log)(t)\sim\frac{2\log(t)}{\mathbf{W}(2\log(t))}\,,\quad\tilde{g}(t)=t\quad,$
(16)

being $\mathbf{W}$ the Lambert function Abramowitz and Stegun (1964), where
only the positive, real branch is taken into account. In figure (3c) we see
that $S_{\Lambda}(\eta(t))$ fits perfectly $g(t)\sim t$, proving that
$(\Lambda,t)$ is a compact scale for the CRPM –see also section 3C.5 of the
SI. We observe that this particular compact scale makes the path entropy
$S_{\Lambda}$ extensive when applied to the CRPM.

##  II Discussion

We demonstrated that, for a very general class of stochastic processes, to
which we refer to as compact stochastic processes, the typical set is well
defined. These processes can be path dependent, contain arbitrary internal
correlations or display dynamic behaviour of the phase space, showing sub- or
super- exponential growth on the effective number of configurations the system
can achieve. The only requirement is that there exist two functions
$\Lambda,g$ for which equation (1) holds. Along the existence of the typical
set, a generalized form of entropy naturally arises, from which, in turn, the
cardinality of the typical set can be computed.

The existence of the typical set in systems with arbitrary phase space growth
opens the door to a proper characterization, in terms of statistical
mechanics, of a number of processes, mainly biological, where the number of
configurations and states changes over time. In particular, it paves the path
towards the statistical-mechanics-like understanding of processes showing
open-ended evolution. For example, this could encompass thermodynamic
characterizations of –part of– developmental paths in early stages of
embryogenesis. The existence of the typical set, even in some extreme
scenarios of stochasticity and phase space behaviour, may not be uniquely
instrumental as a theoretical tool: As a speculative hypothesis, one may
consider that typicality lays behind the astonishing reproducibility and
precision of some biological processes. In this scenario, stochasticity would
drive the system to the set of correct configurations –those belonging to the
typical set– with high accuracy. Selection, in turn, would operate on typical
sets, thereby promoting certain stochastic processes over the others. More
specific scenarios are nevertheless required in order to make this suggesting
hypothesis more sound.

Further works should clarify the potential of the proposed probabilistic
framework to accommodate generalized, consistent forms of thermodynamics and
explore the complications that can arise due to the break of ergodicity that
is implicit in some of the processes compatible with the above description.
Importantly, our results provide a potential starting point for an ensemble
formalism for systems with arbitrary phase space growth, extending the concept
of thermodynamic limit to these systems without requiring further conditions
like microscopic detailed balance. Questions like the definition of free
energies or the possible need of extensivity to have a consistent picture
remain, however, open. To give tentative answers to these questions, links to
early proposals could be in principle drawn, both at the level of
thermodynamic grounds –see, e.g., S. Abe and Plastino (2001); Abe (2006);
Jensen et al. (2018)– and at the level of entropy characterization, as, for
example, in Jensen and Tempesta (2018); Tempesta (2016a); Korbel and Thurner
(2018); Hanel and Thurner (2011a); Korbel et al. (2021). We finally point out
the impact of our results for the study of information sources, given the
important consequences the typical set has for optimal coding and data
compression. The existence of the typical set in these broad class of
information sources, where in general, roughly speaking, the information flow
is not constant, may open the possibility of new compressing strategies. These
could be based, for example, on the encoding of the specific CSP used to
generate the information source and the $\Lambda,g$ functions used to ensure
convergence.

## Acknowledgements

The authors want to thank Petr Jizba and Artemy Kolchinsky for the helpful
discussions that enabled us to improve the quality of the manuscript. B. C-M
wants to acknowledge the helpful hints from Daniel R. Amor and the support of
the field of excellence Complexity in Life, Basic Research and Innovation of
the University of Graz.

## References

  * Morowitz (1968) H. J. Morowitz, _Energy flow in biology: Biological organization as a problem in thermal physics_ (Academic press:London, 1968).
  * Maynard Smith and Szathmáry (1995) J. Maynard Smith and E. Szathmáry, _The Major Transitions in Evolution_ (Freeman:Oxford, 1995).
  * Bonner (1988) J. T. Bonner, _The Evolution of Complexity by Means of Natural Selection_ (Princeton University Press:Princeton, NJ, 1988).
  * Wolpert et al. (2007) L. Wolpert, T. Jessell, P. Lawrence, E. Meyerowitz, E. Robertson, and J. Smith, _Principles of Development_ (Oxford University Press:Oxford, Oxford, 2007), 3rd ed.
  * Bialek (2012) W. Bialek, _Biophysics: Searching for Principles_ (Princeton University Press:Princeton, NJ, 2012).
  * Solé and Goodwin (2000) R. Solé and B. Goodwin, _Signs of life_ (Basic books, Perseus group:New York, 2000).
  * Tria et al. (2014) F. Tria, V. Loreto, V. D. P. Servedio, and S. H. Strogatz, 4, 5890 (2014).
  * Loreto et al. (2016) V. Loreto, V. D. P. Servedio, S. H. Strogatz, and F. Tria, Creativity and universality in language pp. 59–83 (2016).
  * Corominas-Murtra et al. (2018) B. Corominas-Murtra, L. Seoane, and R. Solé, Journal of The Royal Society Interface 15, 20180395 (2018).
  * Iacopini et al. (2020) I. Iacopini, G. Di Bona, E. Ubaldi, V. Loreto, and V. Latora, Phys. Rev. Lett. 125, 248301 (2020).
  * Schuster (1996) P. Schuster, Complexity pp. 22 – 30 (1996).
  * Bedau et al. (2000) M. A. Bedau, J. S. McCaskill, N. H. Packard, S. Rasmussen, C. Adami, D. G. Green, T. Ikegami, K. Kaneko, and T. S. Ray, Artificial Life pp. 363 – 376 (2000).
  * Ruíz-Mirazo et al. (2004) K. Ruíz-Mirazo, J. Peretó, and A. Moreno, Origins of Life and Evolution of the Biosphere pp. 323–346 (2004).
  * Ruíz-Mirazo et al. (2008) K. Ruíz-Mirazo, J. Umérez, and A. Moreno, Biological Philososphy pp. 67 – 85 (2008).
  * Day (2012) T. Day, Journal of the Royal Society Interface pp. 624–639 (2012).
  * Packard et al. (2019) N. Packard, M. A. Bedau, A. Channon, T. Ikegami, S. Rasmussen, K. O. Stanley, and T. Taylor, Artificial Life 25, 93 (2019).
  * Pattee and Sayama (2019) H. H. Pattee and H. Sayama, Artificial Life 25, 4 (2019).
  * Dietrich and Hiiragi (2007) J.-E. Dietrich and T. Hiiragi, Development 134, 4219 (2007).
  * Maitre et al. (2016) J. L. Maitre, H. Turlier, R. Illukkumbura, and et al, Nature 536, 344 (2016).
  * Giammona and Campàs (2021) J. Giammona and O. Campàs, PLoS Comput Biol 17, e1007994 (2021).
  * Corominas-Murtra et al. (2015) B. Corominas-Murtra, R. Hanel, and S. Thurner, Proceedings of the National Academy of Sciences 112, 5348 (2015).
  * Corominas-Murtra et al. (2017) B. Corominas-Murtra, R. Hanel, and S. Thurner, Scientific Reports 7, 11223 (2017).
  * Fujii and Berengut (2021) K. Fujii and J. C. Berengut, Physical Review Letters 126, 102502 (2021).
  * Cover and Thomas (2012) T. M. Cover and J. A. Thomas, _Elements of information theory_ (John Wiley & Sons:New York, 2012).
  * Ash (2012) R. B. Ash, _Information Theory_ (Courier Corporation, 2012).
  * Pathria (2002) R. K. Pathria, _Statistical Mechanics_ (Oxford University Press:Oxford, 2002).
  * Pitowsky (2012) I. Pitowsky, in _Probability in Physics_ , edited by Y. Ben-Menahem and M. Hemmo (Springer: Berlin, 2012), pp. 41–58.
  * Lebowitz (1993) J. L. Lebowitz, Physica A 194, 1 (1993).
  * Battermann (2001) R. Battermann, _The Devil in the Details: Asymptotic Reasoning in Explanation, Reduction, and Emergence_ (Oxford University press: Oxford, UK, 2001).
  * Frigg (2009) R. Frigg, Philosophy of Science 76, 997 (2009).
  * Kač (1989) M. Kač, Advances in Applied Mathematics 10, 270 (1989).
  * Pitman (2006) J. Pitman, _Combinatorial Stochastic Processes_ (Springer-Verlag:Berlin, 2006).
  * Clifford and Stirzaker (2008) P. Clifford and D. Stirzaker, Proceedings of the Royal Society of London A 464, 1105 (2008).
  * Biró and Néda (2018) T. Biró and Z. Néda, Physica A: Statistical Mechanics and its Applications 499, 335 (2018).
  * Jensen et al. (2018) H. J. Jensen, R. H. Pazuki, G. Pruessner, and P. Tempesta, Journal of Physics A: Mathematical and Theoretical 51 (2018).
  * Korbel et al. (2021) J. Korbel, S. D. Lindner, R. Hanel, and S. Thurner, Nature Communications 12, 1127 (2021).
  * Gray and Davisson (1974) R. M. Gray and L. D. Davisson, IEEE Trans. Inform. Theory 20, 502 (1974).
  * Visweswariah and Verdu (2000) S. R. Visweswariah, K. Kulkarni and S. Verdu, IEEE Transactions on Information Theory 46, 1633 (2000).
  * Vu and Kass (2009) B. Vu, V. Q. Yu and R. E. Kass, Neural Computation 21, 688 (2009).
  * Boashash and O’Toole (2013) G. Boashash, B. Azemi and J. O’Toole, IEEE Signal Processing Magazine 30, 108 (2013).
  * Granero-Belinchón and Garnier (2019) S. G. Granero-Belinchón, C. Roux and N. B. Garnier, Entropy 21, 1223 (2019).
  * Abe (2000) S. Abe, Phys. Lett. A 271, 74 (2000).
  * Hanel and Thurner (2011a) R. Hanel and S. Thurner, EPL (Europhysics Letters) 93, 20006 (2011a).
  * Enciso and Tempesta (2017) A. Enciso and P. Tempesta, Journal of Statistical Mechanics: Theory and Experiment 12, 123101 (2017).
  * Tempesta (2016a) P. Tempesta, Annals of Physics 365, 180 (2016a).
  * Tempesta (2016b) P. Tempesta, Proceedings of the Royal Society of London A 472, 20160143 (2016b).
  * Thurner et al. (2017) S. Thurner, B. Corominas-Murtra, and R. Hanel, Physical Review E 96, 032124 (2017).
  * Jizba and Korbel (2020) P. Jizba and J. Korbel, Physical Review E 101, 042126 (2020).
  * Korbel and Jizba (2019) J. Korbel and P. Jizba, Physical Review Letters 122, 120601 (2019).
  * Jizba and Korbel (2017) P. Jizba and J. Korbel, Entropy 19, 605 (2017).
  * Hanel and Thurner (2011b) R. Hanel and S. Thurner, Europhysics Letters 96, 50003 (2011b).
  * Jensen and Tempesta (2018) H. J. Jensen and P. Tempesta, Entropy 20, 804 (2018).
  * Korbel and Thurner (2018) R. Korbel, J. Hanel and S. Thurner, New Journal of Physics 20, 093007 (2018).
  * J. Korbel and Thurner (2020) R. J. Korbel, Hanel and S. Thurner, European Physics Journal, Special Topics 229, 787 (2020).
  * Hanel and Thurner (2013) R. Hanel and S. Thurner, Entropy 15, 5324 (2013).
  * Nicholson et al. (2016) S. B. Nicholson, M. Alaghemandi, and J. R. Green, The Journal of Chemical Physics 145, 084112 (2016).
  * Balogh et al. (2020) S. G. Balogh, G. Palla, P. Pollner, and D. Czégel, Scientific Reports 10, 15516 (2020).
  * Gardiner (1983) C. W. Gardiner, _Handbook of Stochastic Methods for Physics, Chemistry and the Natural Sciences_ (Springer-Verlag: Berlin, Germany, 1983).
  * Feller (1991) W. Feller, _An Introduction to Probability Theory and Its Applications, Vol. 1,2_ (Wiley:New York, NY, USA, 1991).
  * Shannon (1948) C. E. Shannon, Bell Sys. Tech. J. 27, 379 (1948).
  * Khinchin (1957) A. Khinchin, _Mathematical Foundations of Information Theory_ (Dover:New York, 1957).
  * Bassetti et al. (2009) B. Bassetti, M. Zarei, M. Cosentino Lagomarsino, and G. Bianconi, Physical Review E 80, 066118 (2009).
  * Abramowitz and Stegun (1964) M. Abramowitz and I. Stegun, _Handbook of mathematical functions. National Bureau of Standards_ (Applied Mathematics Series 55, U.S. Government Printing Office:Washington DC, 1964).
  * S. Abe and Plastino (2001) F. P. S. Abe, S. Martínez and A. Plastino, Physics Letters A 281, 126 (2001).
  * Abe (2006) S. Abe, Physica A: Statistical Mechanics and its Applications 368, 430 (2006).

## Supplementary material

In this Supplementary material we systematically develop the mathematical
theory used in the main text of the manuscript ”The typical set and entropy in
stochastic systems with arbitrary phase space growth”. The text is structured
as follows: First, we define the class of discrete stochastic systems that we
call categorial, which contain almost anything that can be conceived. From
them, we select the subclass of compact processes, namely, those satisfying
the convergence condition stated in equation (1) of the main text. For them,
we prove the existence of a sequence of typical sets. Further, we define
another subclass, the subclass of simple processes, namely, those by which the
complement of the typical set has no finite contributions to a generalized
entropy in the limit $t\to\infty$. In these processes, the sequence of typical
sets can be defined in terms of the generalized entropy. Finally, we present
an example of a path dependent process, and we show that is compact and
simple. In consequence, we can compute the typical probabilities and the size
of the typical sets, which is shown to grow super-exponentially in time. In
figure (4) –below– we outline the hierarchy that our study induces over
stochastic processes.

Figure 4: A potential hierarchy of discrete stochastic processes. The largest
class would correspond to the categorial processes, which comprise almost
anything that can be conceived as a discrete stochastic process. A subclass of
categorial processes are the compact processes, by which the convergence
condition stated in the equation (1) of the main text holds and, therefore, a
sequence of typical sets can be identified. Inside the compact processes, we
identify the subclass of simple processes, where the sequence of typical sets
can be defined in terms of a general form of entropy. Finally, the simplest
subclass is the one defined by stochastic processes defined by sequences of
independent, identically distributed random variables $\sim X$, by which the
sequence of typical sets can be defined from the entropy in Shannon-like form.
In turn, in i.i.d. systems, the path entropy up to time $t$ can be written as
$t$ times the contribution of a single event Cover and Thomas (2012). Note
that no assumptions of independence or stability of the sampling space are
needed in the two first subclasses, even the typical set can be consistently
identified. In addition, as we will see in section C, the use of Shannon
entropy to characterize the sequence of typical sets is not restricted to
i.i.d. systems.

##  Appendix A Compact categorial processes and typical sets

###  A.1 Categorial processes

Categorial processes $\eta$ are processes that at any time $t$ sample one
state from a finite number of distinguishable states collected in the set
$\Omega_{t}$, called the sample space of the process at time $t$. If we look
at a discrete time line $T={1,2,3,\cdots}$ we represent the process $\eta$ up
to time $t$ as a sequence of random variables $\eta_{t}$, i.e.:

$\eta(t)=\eta_{1}\eta_{2}\cdots\eta_{t-1}\eta_{t}\,.$

The processes $\eta$ neither needs to consist of statistically independent
random variables $\eta_{t}$ nor does the sample space of the process need to
be constant. That is, the local sample spaces $\Omega_{t}$ of the variable
$\eta_{t}$ can differ from the sample space $\Omega_{t^{\prime}}$ of another
variable $\eta_{t^{\prime}}$. If we sample $\eta(t)$ this provides us with a
particular path:

$x(t)=x_{1}x_{2}\cdots x_{t-1}x_{t}\,,$

with $x(t)\in\Omega(t)$, being $\Omega(t)$ defined as:

$\Omega(t)=\Omega_{1}\times\Omega_{2}\times\cdots\times\Omega_{t-1}\times\Omega_{t}\,,$
(17)

in words, the Cartesian product of all local sample spaces
$\Omega_{t^{\prime}}$ up to time $t$.

In principle it could be that also the sample space $\Omega_{t}$ depends on
the path $x(t-1)$ the process has taken up to time $t-1$. In consequence,
$\Omega(t)$ could contain many paths that are not possible for the processes
$\eta$ and, therefore, have zero probability of being sampled. However, we
consider processes by there exists a non-empty subset
$\mathring{\Omega}(t)\subseteq\Omega(t)$, which contains all and only the
sequences $x(t)$ of $\eta$ with $p(x(t))>0$.

######  Definition 1.

Let $\eta$ be a categorial process. We call and $p(x(t))$ the probability of
paths $x(t)\in\Omega(t)$ to be sampled by $\eta$ and, then, we call:

$\mathring{\Omega}(t)=\\{x(t)\in\Omega(t)\,\mathrel{\mathop{\mathchar
58\relax}}\,p(x(t))>0\\}\,,$ (18)

the well formed interior of $\Omega(t)$ or the path sample space of the
process.

Let us call $\Omega_{t}[x(t-1)]$ the set of states of $\Omega_{t}$ that can be
sampled at time $t$ provided that our trajectory up to time $t-1$ was
$x(t-1)$. The set of potential states that can be visited at time $t$, will
then be:

$\Omega_{t}=\bigcup_{x(t-1)\in\mathring{\Omega}(t-1)}\Omega_{t}[x(t-1)]\,,$

i.e. $\Omega_{t}$ contains all states the process could possibly sample at
time $t$ after all possible histories the process could have sampled up to
time $t-1$. In this way we can always assume that we can find $\Omega(t)$ and
its well formed interior $\mathring{\Omega}(t)$ by pruning all ill formed
sequences from $\Omega_{t}\times\mathring{\Omega}(t-1)$. All information on
how the sample space $\Omega_{t}$ gets sampled then solely resides in the
hierarchy of transition probabilities $p(x_{t}|x(t-1))$, where
$x_{t}\in\Omega_{t}$ and $x(t-1)\in\Omega(t-1)$. We get

$\mathring{\Omega}(t)=\\{x(t)\in\Omega_{t}\times\mathring{\Omega}(t-1)\,\mathrel{\mathop{\mathchar
58\relax}}\,p(x_{t}|x(t-1))>0\\}\,.$

In the context of categorial processes, $p(x(t))$ is clearly a monotonic
decreasing function in time bounded below by zero, $p(x(t))\geq 0$. In
consequence, $\lim_{t\to\infty}p(x(t))$ converges for all paths possible paths
$x(t)$ of the process $\eta$. This also means that for almost all paths the
probability $\lim_{t\to\infty}p(x(t))=0$ even though some finite number of
paths could have non-zero probabilities even in the limit $t\to\infty$,
although convergence is guaranteed111Unlike for processes, for systems –e.g.,
particles in a box– it is not guaranteed that adding a new particle –as analog
of to a new sample step– $p(x(t))\leq p(x(t-1)$. In consequence, for systems,
we cannot guarantee convergence of $p(x(t))$ as the system size $t\to\infty$.
After this general description of categorial processes, we can start by
characterizing the subclass of them we are interested in.

###  A.2 Compact categorial processes

In the following we provide the condition of compactness that we impose to
categorial processes in order to ensure the existence of a typical set.

######  Definition 2.

Let $\eta$ be a categorial process $\eta$ and let $\eta(t)$ denote the process
up to time $t$ and $\Omega(t)$ denote the path sample space of $\eta(t)$ (as
discussed above). Let us consider pairs of functions $(\Lambda,g)$, such that
$\Lambda$ is a twice continuously differentiable, strictly monotonic
increasing and strictly concave function on the interval $[1,\infty)$ with
$\lim_{t\to\infty}\Lambda(t)=\infty$ and $\Lambda(1)=0$; and $g$ is a twice
continuously differentiable strictly monotonically increasing function on the
interval $[0,\infty)$. If we can associate such a pair of functions
$(\Lambda,g)$ with the process $\eta$, such that:

$\lim_{t\to\infty}\frac{1}{g(t)}\Lambda\left(\frac{1}{p(\eta(t))}\right)\ =\
1\,,$

(in probability), then we call the process $\eta$ compact in $(\Lambda,g)$ and
$(\Lambda,g)$ a compact scale of $\eta$.

Note that compact scales $(\Lambda,g)$ associated to a given compact
categorial processes (CCP) need not be unique222The fact that we can find
different pairs of functions, $(\Lambda,g)$, in which a process $\eta$ is
compact, leads to questions related to equivalence relations on the space of
pairs, $(\Lambda,g)$. As it turns out, following up the idea of typical sets,
that we are to explode below, a process $\eta$ induces an equivalence relation
on this space, partitioning the space into monads of equivalent compact
scales, $(\Lambda,g)$, of the process. At the same time this means that there
exist inequivalent compact scales, which can be thought of as different
”scales of resolution” to look at a process..

###  A.3 Typical sets in compact categorial processes

Now that we have defined the stage for CCPs we can define particular sequence
of subsets of paths that tell us where the probability of finding paths
”typically” localizes in the path sample space.

######  Definition 3.

Let $\eta$ be compact in $(\Lambda,g)$ and let
$\epsilon_{1},...,\epsilon_{t},...$ be a non-increasing sequence with limit
$\lim_{t\to\infty}\epsilon_{t}=0$, then we can define the set:

$A[\epsilon_{t}]=\left\\{x(t)\in\Omega(t)\,\mathrel{\mathop{\mathchar
58\relax}}\,\left|\frac{1}{g(t)}\Lambda\left(\frac{1}{p(\eta(t))}\right)-1\right|<\epsilon_{t}\right\\}\,,$

for every $t=1,2,3,\cdots$. If for the choice of $\epsilon_{t}$ it holds that

$\lim_{t\to\infty}\mathbb{P}(x(t)\in A[\epsilon_{t}])=1\,,$

then we call $A[\epsilon_{t}]$ a typical set in $(\Lambda,g)$ at time $t$ and
the sequence $\epsilon_{1},\epsilon_{2},...,\epsilon_{t-1},\epsilon_{t}$ a
typical localizer of $\eta$.

At this point we have introduced the notion of typicality. Next we proof the
following:

######  Theorem 1.

If $\eta$ is a CCP in $(\Lambda,g)$, then there exist (a) typical localizer
sequence $\epsilon_{1},\epsilon_{2},...,\epsilon_{t-1},\epsilon_{t},...$
associated to $\eta$ and hence (b) the respective sequence of typical sets
$A[\epsilon_{1}],...,A[\epsilon_{t}],...$ by which:

$\lim_{t\to\infty}\mathbb{P}(x(t)\in A[\epsilon_{t}])=1\,.$

###### Proof.

Since $\eta$ is a CCP we know, by assumption, that, as $t\to\infty$
$\Lambda(1/p(\eta(t)))/g(t)\to 1$ (in probability). We can rewrite this
condition by stating that, for every $\epsilon,\delta>0$, there exists a
$t_{0}$ by which, for each $t>t_{0}$ Feller (1991):

$\mathbb{P}\left(\left|\frac{1}{g(t)}\Lambda\left(\frac{1}{p(x(t))}\right)-1\right|>\epsilon\right)<\delta\,.$

Let $\tau(\varepsilon,\delta)$ be the smallest such $t_{0}$. We can then use
two arbitrary strictly monotonic decreasing functions $\epsilon^{*}_{n}$ and
$\delta^{*}_{n}$ that converge to zero and construct a monotonically
increasing sequence of times $t_{n}=\tau(\epsilon^{*}_{n},\delta^{*}_{n})$
such that for all $t\geq t_{n}$ it is true that

$\mathbb{P}\left(\left|\frac{1}{g(t)}\Lambda\left(\frac{1}{p(x(t))}\right)-1\right|>\epsilon^{*}_{n}\right)<\delta^{*}_{n}\,.$

From that, it is straightforward to define a typical localizer sequence
$\epsilon_{1},...,\epsilon_{t},...$, by just taking:

$(\forall t\mathrel{\mathop{\mathchar 58\relax}}t_{n}\leq
t<t_{n+1})\,,\,\epsilon_{t}=\epsilon^{*}_{n}\,.$

Finally, the condition:

$\lim_{t\to\infty}\mathbb{P}(x(t)\in A[\epsilon_{t}])=1\,,$

follows as a direct consequence of the construction of the sequence of typical
sets $A[\epsilon_{1}],...,A[\epsilon_{t}],...$, thereby concluding the proof.
∎

The next step is to check what kind of functions $\Lambda$ can be expected
when dealing with CCP’s. To that end, we will impose a condition to the CCP,
namely, that the CCP is filling. From this –very mild– condition, we will then
check which functions enable the convergence criteria to be fullfilled. First
of all, we need to introduce some technical terms.

######  Definition 4.

Let $\eta$ be a CCP in $(\Lambda,g)$ with a typical localizer sequence
$\epsilon_{1},...,\epsilon_{t},...$. We define the upper and lower typical
ratios, $r_{\pm}(t)$, in $(\Lambda,g)$ as:

$r_{\pm}(t)=\frac{\Lambda^{-1}\left((1\pm\epsilon_{t})g(t)\right)}{\Lambda^{-1}\left(g(t)\right)}\,,$

where $\Lambda^{-1}$ is the inverse function of $\Lambda$, which exists due to
the strict monotonicity of $\Lambda$.

Note that, by construction, $r_{+}(t)\geq 1$ and $r_{-}(t)\leq 1$.

######  Definition 5.

We call a CCP $\eta$ filling in $(\Lambda,g)$ if its typical ratios have the
property $\lim_{t\to\infty}r_{+}(t)=\infty$ and $\lim_{t\to\infty}r_{-}(t)=0$.

We can now say something about the shape of functions $\Lambda$.

######  Proposition 1.

If $\eta$ is a filling CCP in $(\Lambda,g)$, then it follows that:

$\lim_{z\to\infty}\frac{\Lambda(\lambda z)}{\Lambda(z)}=1\,,$

for all $\lambda>0$.

###### Proof.

We note that for filling CCP $\eta$ it is true that:

$\frac{1}{g(t)}\Lambda(r_{\pm}(t)\Lambda^{-1}(g(t)))\to 1\,,$

as $t\to\infty$. We can rewrite $z_{t}=\Lambda^{-1}(g(t))$ and for $\lambda>1$
we find a $t_{0}$ such that $\lambda=r_{+}(t_{0})$. Therefore for all
$t>t_{0}$ we find:

$1\leq\frac{\Lambda(\lambda
z_{t})}{\Lambda(z_{t})}\leq\frac{\Lambda(r_{+}(t)z_{t})}{\Lambda(z_{t})}\to
1\,.$

The other case, $0<\lambda<1$, we prove analogously using $r_{-}$ instead of
$r_{+}$, and the proposition follows. ∎

To get an idea which kind of functions satisfy this condition we can look at
the following example:

######  Proposition 2.

For any $c>0$ the function $\Lambda(z)=\log(z)^{c}$ has the property
$\lim_{z\to\infty}\Lambda(\lambda z)/\Lambda(z)=1$ for all $\lambda>0$.

###### Proof.

We can proof this by direct computation, i.e.:

$\displaystyle\frac{\Lambda(\lambda z)}{\Lambda(z)}$ $\displaystyle=$
$\displaystyle\left(\frac{\log(\lambda z)}{\log(z)}\right)^{c}$
$\displaystyle=$
$\displaystyle\left(\frac{\log(\lambda)+\log(z)}{\log(z)}\right)^{c}$
$\displaystyle=$
$\displaystyle\left(1+\frac{\log(\lambda)}{\log(z)}\right)^{c}\,.$

Since $\log(z)\to\infty$, one can easily read from the last line that the
example family of functions $\Lambda$ fulfils the proposition. ∎

In general we can say that candidates for $\Lambda$ of filling CCPs are of the
form $\Lambda(z)=c\log(z)^{d}$ for some positive constants $c$ and $d$ or even
slower growing functions of the form:

$\Lambda=c_{1}\log(1+c_{2}\log(1+c_{3}\log(\cdots)^{d_{3}})^{d_{2}})^{d_{1}}\,.$

##  Appendix B Typical sets, simplicity condition and generalized entropies

###  B.1 Generalized entropies associated to CCP’s

We start by defining the generalized entropy associated to a CCP $\eta$ in
$(\Lambda,g)$

######  Definition 6.

Let $\eta$ be a CCP in $(\Lambda,g)$, then we call the measure, $S_{\Lambda}$
of $\eta(t)$, defined as:

$S_{\Lambda}(\eta(t))=\sum_{x(t)\in\Omega(t)}p(x(t))\Lambda\left(\frac{1}{p(x(t))}\right)\,,$
(19)

a generalized path entropy associated with $\eta$. Note that for a set
$B\subset\Omega(t)$ the generalized entropy measure, $S_{\Lambda}(B)$, is
given by $S_{\Lambda}(B)=\sum_{x(t)\in
B}p(x(t))\Lambda\left(1/p(x(t))\right)$.

In the following proposition we see that the above defined entropy satisfies
three of the four Shannon-Khinchin’s axioms for an entropy measure Khinchin
(1957) (SK1, SK2, SK3). The fourth axiom (SK4) is not generally satisfied.

######  Proposition 3.

The entropy functional $S_{\Lambda}$defined in equation (19) satisfies the
first three of the four Shannon-Khinchin’s axioms for an entropy measure as
formulated in Khinchin (1957):

SK1 $S_{\Lambda}$ is a contiunous function only depending on the probabilities
$p(x(t))$.

SK2 $S_{\Lambda}$ is maximized if $(\forall p(x(t)))$
$p(x(t))=\frac{1}{|\Omega(t)|}$, i.e., equiprobability.

SK3 If $p(x(t))=0$, then: $p(x(t))\Lambda\left(\frac{1}{p(x(t))}\right)=0$,
i.e., events with zero probability have no contribution to the entropy.

###### Proof.

To demonstrate SK1, it is enough to observe that $S_{\Lambda}$ is only
function of the probabilities and to take into account that, by assumption,
$\Lambda\in{\cal C}^{2}$, therefore, $S_{\Lambda}$ continuous.

To demonstrate SK2, we need to maximize the functional $\psi$, defined as:

$\psi=S_{\Lambda}(\eta(t))-\alpha\left(\sum_{x(t)\in\Omega(t)}p(x(t))-1\right)\,,$

where $\alpha$ is a Lagrangian multiplier implementing the normalization
constraint. Maximizing $\psi$ with respect to a $p(x(t))$yields:

$0=\frac{\partial\psi}{\partial
p(x(t))}=\Lambda(z)-z\Lambda^{\prime}(z)-\alpha\,,$

where $z=1/p(x(t))$ and $\Lambda^{\prime}$ is the first derivative of
$\Lambda$. Note that if the equation does not depend explicitly on $x(t)$ and
if it has a unique solution then the proposition is proved, since all
$p(x(t))$ have the same value. To see that a unique solution exists we need to
show that $f(z)=\Lambda(z)-z\Lambda^{\prime}(z)$ is strictly monotonic. To see
that, it is enough to note that the first derivative of $f$ is given by
$f^{\prime}(z)=-z\Lambda^{\prime\prime}(z)>0$, since, by definition of
compactness, $\Lambda\in{\cal C}^{2}$ and strictly concave; and therefore
$\Lambda^{\prime\prime}(z)<0$.

Finally, to demonstrate that $S_{\Lambda}$ satisfies SK3 we apply the
l’Hopital rule. First, by defining $y=1/z$, one has that:

$\lim_{z\to
0}z\Lambda\left(\frac{1}{z}\right)=\lim_{y\to\infty}\frac{1}{y}\Lambda(y)\,.$

Then, considering that, by definition, $\Lambda\in{\cal C}^{2}$ is a strictly
growing and concave function, one is led, after application to the l’Hopital
rule for the limit, to:

$\lim_{y\to\infty}\frac{1}{y}\Lambda(y)=\lim_{y\to\infty}\Lambda^{\prime}(y)=0\,,$

thereby concluding the proof. ∎

We observe that SK3 enables us to safely perform the sum for the entropy over
the whole set of paths $\Omega(t)$, since
$\sum_{x(t)\in\mathring{\Omega}(t)}(...)=\sum_{x(t)\in\Omega(t)}(...)$.

###  B.2 Simple CCP’s

Now we define the condition of simplicity, namely, the property of processes
by which the contributions to the entropy from paths outside the typical set
vanish333It is however conceivable that CCPs exist that are not simple and the
entropy in the limit has singular contributions from complement of the typical
set. Even in probabilistic terms the complement of the typical set has measure
zero, the presence of a large amount of highly improbable paths could give a
non vanishing contribution to the entropy..

######  Definition 7.

Let $\eta$ be a filling CCP in $(\Lambda,g)$ with a typical localizer sequence
$\epsilon_{1},...,\epsilon_{t},...$. Let
$A^{c}[\epsilon_{t}]=\Omega(t)\setminus A[\epsilon_{t}]$ be the complement of
the typical set in the well formed interior of $\Omega(t)$. We call $\eta$
simple if:

$\lim_{t\to\infty}\frac{1}{g(t)}S_{\Lambda}(A^{c}[\epsilon_{t}])=0\,.$

Given a filling CCP in $(\Lambda,g)$ $\eta$, one can check if the simplicity
condition is satisfied as follows: Let $p^{*}(x(t))$ be such that

$p^{*}(x(t))=\min_{\mathring{\Omega}(t)}\\{p(x(t))\\}\,,$

–recall that we select among those paths $x(t)\in\mathring{\Omega}(t)$ i.e.,
those by which $p(x(t))>0$. Then, assume the extreme case by which $(\forall
x(t)\in A^{c}[\epsilon_{t}],p(x(t))=p^{*}(x(t))$, thereby maximizing
$\Lambda(1/p(x(t)))$ and, in consequence, the contribution of the
complementary of the typical set to the entropy. If the following limit holds:

$\lim_{t\to\infty}\frac{\delta_{t}}{g(t)}\Lambda\left(\frac{1}{p^{*}(x(t))}\right)=0\,,$

then the process is simple. Note that the converse may not be true, there can
be processes by which this proof does not hold but still, they are simple. For
that, one must explore other strategies.

###  B.3 Generalized entropies and the typical set

We go now to the next step in the characterization of the typical set: For
processes satisfying the simplicity condition, the typical set can be defined
in terms of the generalized entropy $S_{\Lambda}$. This is consequence of the
following theorem:

######  Theorem 2.

If $\eta$ is a simple CCP in $(\Lambda,g)$ with typical localizer sequence
$\epsilon_{1},...,\epsilon_{t},...$ and corresponding sequence of typical sets
$A[\epsilon_{1}],...,A[\epsilon_{t}],...]$, then:

$\lim_{t\to\infty}\frac{S_{\Lambda}(\eta(t))}{g(t)}=\lim_{t\to\infty}\frac{S_{\Lambda}(A[\epsilon_{t}])}{g(t)}=1\,.$

###### Proof.

We will start with the second equality, namely:

$\lim_{t\to\infty}\frac{S_{\Lambda}(A[\epsilon_{t}])}{g(t)}=1\,.$

From the definition of typical sets we know that, for paths $x(t)\in
A[\epsilon_{t}]$, it is true that:

$\frac{1}{\Lambda^{-1}((1+\epsilon_{t})g(t))}\ \leq\ p(x(t))\ \leq\
\frac{1}{\Lambda^{-1}((1-\epsilon_{t})g(t))}\,.$

In consequence, given that $\mathbb{P}(x(t)\in
A[\epsilon_{t}]))>1-\delta_{t}$, one can bound $S_{\Lambda}(A[\epsilon_{t}])$
as:

$(1-\delta_{t})(1-\epsilon_{t})<\frac{S_{\Lambda}(A[\epsilon_{t}])}{g(t)}<(1-\delta_{t})(1+\epsilon_{t})\,.$

Since, by construction
$\lim_{t\to\infty}\epsilon_{t}=\lim_{t\to\infty}\delta_{t}=0$, this second
part of the theorem is proven. From that, the statement of the theorem:

$\lim_{t\to\infty}\frac{S_{\Lambda}(\eta(t))}{g(t)}=\lim_{t\to\infty}\frac{S_{\Lambda}(A[\epsilon_{t}])}{g(t)}=1\,,$

follows directly given the assumption of simplicity. ∎

Therefore, as we advanced above, in simple CCP’s, one can define the typical
set $A[\epsilon_{t}]$ as:

$A[\epsilon_{t}]=\left\\{x(t)\in\Omega(t)\,\mathrel{\mathop{\mathchar
58\relax}}\,\left|\frac{1}{S_{\Lambda}(\eta(t))}\Lambda\left(\frac{1}{p(x(t))}\right)-1\right|<\epsilon_{t}\right\\}\,,$

and, consequently, the typical probabilities will be bounded by:

$\displaystyle(\forall x(t)\in A[\epsilon_{t}])\;;\quad\quad\quad$
$\displaystyle\,\frac{1}{\Lambda^{-1}(S_{\Lambda}(\eta(t))(1+\epsilon_{t}))}$
$\displaystyle<$ $\displaystyle p(x(t))$ $\displaystyle<$
$\displaystyle\frac{1}{\Lambda^{-1}(S_{\Lambda}(\eta(t))(1-\epsilon_{t}))}\,.$

Finally, as shown in equations (10) and (11) of the main text, the cardinality
of the typical set can be bounded, in terms of the generalized entropy
$S_{\Lambda}$ as:

$\displaystyle(1-\epsilon_{t})\Lambda^{-1}((1-\epsilon_{t})S_{\Lambda}(\eta(t)))$
$\displaystyle<$ $\displaystyle|A[\epsilon_{t}]|$ $\displaystyle<$
$\displaystyle\Lambda^{-1}((1+\epsilon_{t})S_{\Lambda}(\eta(t)))\,.$

As a consequence of the above chain of inequalities, one can go further in the
characterization of the generalized entropy and its relation to the typical
set. Indeed, for simple CCPs, $g(t)\sim
S_{\Lambda}(\eta(t)\sim\Lambda(|A[\epsilon_{t}]|)$. We demonstrate that in the
following proposition:

######  Proposition 4.

Let $\eta$ be a simple CCP in $(g,\Lambda)$ with some typical localizer
sequence $\epsilon_{1},...,\epsilon_{t},...$, then:

$\lim_{t\to\infty}\frac{\Lambda(|A[\epsilon_{t}]|)}{S_{\Lambda}(\eta(t))}\ =\
1\,.$

###### Proof.

from equation (LABEL:Seq:BoundS), one can derive the following chain of
inequalities:

$\displaystyle\Lambda((1-\epsilon_{t})\Lambda^{-1}((1-\epsilon_{t})S_{\Lambda}(\eta(t))))$
$\displaystyle<$ $\displaystyle\Lambda(|A[\epsilon_{t}]|)$ $\displaystyle<$
$\displaystyle(1+\epsilon_{t})S_{\Lambda}(\eta(t))\,.$

The last term has no difficulties. To explore the behaviour of the first one,
just rename the term:

$z\equiv\Lambda^{-1}((1-\epsilon_{t})S_{\Lambda}(\eta(t)))\,,$

and rewrite the first term of the inequality as:

$\Lambda((1-\epsilon_{t})\Lambda^{-1}((1-\epsilon_{t})S_{\Lambda}(\eta(t))))=\Lambda((1-\epsilon_{t})z)\,.$

We know, from proposition 1, that the functions we are dealing with behave
such that:

$\lim_{z\to\infty}\frac{\Lambda(\lambda z)}{\Lambda(z)}\to 1\,,\,(\forall
z>0).$

As a consequence:

$\frac{\Lambda((1-\epsilon_{t})\Lambda^{-1}((1-\epsilon_{t})S_{\Lambda}(\eta(t))))}{S_{\Lambda}(\eta(t))}\to
1\,.$

Therefore, since also the third term goes trivially to $\sim
S_{\Lambda}(\eta(t))$, we can conclude that:

$\frac{\Lambda(|A[\epsilon_{t}]|)}{S_{\Lambda}(\eta(t))}\ \to 1\,,$

as we wanted to demonstrate. ∎

##  Appendix C The Chinese Restaurant process

We now turn to analysing the version of the Chinese restaurant process with
memory (CRPM) discussed in the main body of the paper. The version presented
here is a variation of the standard Chinese Restaurant process as found in
Pitman (2006); Bassetti et al. (2009).

###  C.1 Definition and basics

Suppose a restaurant with an infinite set of tables $m_{1},...,m_{n},...$ each
with infinite capacity. The first customer enters and sits at the first table
$m_{1}$. The second customer now has a choice to also sit down at the first
table $m_{1}$ together with the first customer or to choose a free table
$m_{2}$, each with probability $1/2$. Let $m(t-1)$ be the number of occupied
tables at $t-1$. If the $t$’th customer finds that $m(t-1)$ tables are already
occupied by some guests, then again the customer will choose one of the non-
empty tables:

$m_{1},...,m_{m(t-1)}\,,$

each with probability $1/(m(t-1)+1)$, in which case $m(t)=m(t-1)$, or the next
empty table $m_{m(t-1)+1}$, also with probability $1/(m(t-1)+1)$. In this
later case $m(t)=m(t-1)+1$. The key point is therefore the number of occupied
tables $m(t)$. We observe that the amount of occupied tables it can be
rewritten as a stochastic recurrence:

$m(t+1)=m(t)+\zeta(m(t))\,,$ (21)

where $\zeta(m(t))$ is a random variable by which:

$p(\zeta(m(t))=0)=\frac{m(t)}{m(t+1)}\;,\,p(\zeta(m(t))=1)=\frac{1}{m(t+1)}\,.$

Clearly,

$m(t)=1+\sum_{t^{\prime}\leq t}\zeta(m(t))\,,$

is a non decreasing function in $t$. Now let us define $M_{k}(t)$ as a random
variable taking values uniformly at random over the set
$m_{1},...,m_{k},m_{k+1}$ at time $t$. The sequence of random variables
accounting describing the CRPM $\eta(t)$ can be written as:

$\eta(t)=M_{1}(1),M_{1}(2),M_{m(2)}(3),...,M_{m(t)}(t+1),...\,,$

leading to paths $x(t)$ of the kind:

$x(t)=m_{1},m_{1},m_{2},m_{1},m_{2},m_{3},m_{2},m_{2},m_{1},m_{3},...$

We emphasize that the tables visited are distinguishable and can visited
repeatedly. The CRPM however does not fill up $\Omega(t)$, i.e. there exist
elements in $\Omega(t)=\times_{t^{\prime}=1}^{t}\Omega_{t^{\prime}}$, that are
not potential paths of the CRP. This includes all sequences that select a
table $m_{i}$ without ever having chosen some table $m_{j}$, with $j<i$
before. For example, the path
$x(t)=(m_{1},m_{2},m_{1},m_{2},m_{3},m_{1},m_{5},m_{4},m_{3},\cdots)$ is not
possible, because $m_{5}$ is chosen before $m_{4}$. The CRPM therefore gives
us the opportunity to introduce sampling spaces conditional to a particular
well formed path. In this particular case, it is enough to observe that the
sampling space some well formed path $x(t)\in\Omega(t-1)$ sees at time $t$ is
given by:

$\Omega_{t}[x(t-1)]=\\{m_{1},m_{2},\cdots,m_{m[x](t-1)]+1}\\}\,,$ (22)

where $m[x](t-1)$ is the number of different tables the well formed CRPM path
$x(t-1)$ has sampled at time $t-1$. By convention, we define $m[x](1)=1$.

###  C.2 Statistics of the CRPM

We start computing the probability of a particular path
$x(t)\in\mathring{\Omega}(t)$.

######  Proposition 5.

Let process $\eta(t)$ be the CRPM and $x(t)\in\mathring{\Omega}(t)$ be a given
path of the process up to time $t$. Let $m[x](t^{\prime})$ be the number of
occupied tables in the restaurant associated with the path $x(t^{\prime})$ at
time $t^{\prime}$. Then the probability to observe the particular sequence of
tables, $p(x(t))$ is given by:

$p(x(t))=\prod_{t^{\prime}=1}^{t}\left(m[x](t^{\prime})+1\right)^{-1}\,.$

###### Proof.

The proposition follows from direct calculation. ∎

Now we will see that the sequence corresponding to the number of occupied
tables converges to a tractable functional form.

######  Proposition 6.

Given the sequence of occupied tables of the CRPM $m(1),...,m(t)$ as defined
in equation (21), then:

$\frac{m(t)}{\sqrt{2t}}\to 1\,,$

in probability.

###### Proof.

Consider the random variable $\Delta t_{k}$ denoting the amount of steps by
which $m(t)=k$. $\Delta t_{k}$ is a geometric random variable with associated
law:

$p(\Delta
t_{k}=i)=\left(1-\frac{1}{k}\right)^{i-1}\frac{1}{k}\;,\,\langle\Delta
t_{k}\rangle=k\;,\,\sigma^{2}(\Delta t_{k})=k^{2}-k\,.$

Now we construct a new set of renormalized random variables, $\delta
t_{1},...,\delta t_{k}$ as:

$\delta t_{k}\equiv\frac{\Delta t_{k}}{k}\;,\,\langle\delta
t_{k}\rangle=1\;,\,\sigma^{2}(\delta t_{k})=1-\frac{1}{k}\,.$

In that context, the sum of $\delta t_{1},...,\delta t_{k}$ is the sum of $k$
random variables with mean $1$ and $\sigma^{2}<1$. Therefore, there exists a
monotonously increasing function, $\mu(t)$ by which, by the law of large
numbers, for each pair $\epsilon,\delta<0$, there exists $t_{0}$ such that,
for $t>t_{0}$:

$\mathbb{P}\left(\left|\frac{\sum_{k\leq m(t)}\delta
t_{k}}{\mu(t)}-1\right|>\epsilon\right)<\delta\,.$

Notice that, in this setting, we have that the deviations behave close to a
discrete random walk centered at $0$ and with step length $\sigma^{2}<1$.
Since for all $\delta t_{k}$, $\langle\delta t_{k}\rangle=1$:

$\frac{m(t)}{\mu(t)}\to 1\;,\;{\rm(in\;probability)}\,,$

and, since, by construction:

$\sum_{k\leq\mu(t)}k\delta t_{k}=t\,,$

one has that:

$\mu(t)\sim\sqrt{2t}\,.$

where ”$\sim$” means asymptotically equivalent, as we wanted to demonstrate. ∎

###  C.3 The typical set of the CRP

######  Theorem 3.

The CRPM is compact with compact scale $(\Lambda,g(t))=(\log,\frac{t}{2}\log
t)$.

###### Proof.

We need to demonstrate that:

$\frac{1}{\frac{t}{2}\log t}\log\left(\frac{1}{p(\eta(t))}\right)\to
1\,,\;\;{\rm(in\;probability)}\,.$

We first note that, according to the definition of the sequence of the number
of occupied tables given in equation (21), and the statement of proposition 5,
one can rewrite the logarithmic term of the condition for compactness as:

$\log\left(\frac{1}{p(\eta(t))}\right)=\sum_{t^{\prime}\leq
t}\log(m(t^{\prime}))\,.$

Now, let us define a new random variable $z(t)$ as follows:

$z(t)=m(t)-\mu(t)\,,$

with $\mu(t)=\sqrt{2t}$. Notice that, according to proposition 6, we have
that:

$\frac{z(t)}{\mu(t)}\to 0\;,\;{\rm(in\;probability)}\,.$

We can then rewrite condition of compactness, with $g(t)=\sum_{t^{\prime}\leq
t}\log(\mu(t))$, as:

$\displaystyle\frac{1}{\sum_{t^{\prime}\leq
t}\log(\mu(t^{\prime}))}\log\left(\frac{1}{p(\eta(t))}\right)$
$\displaystyle=$ $\displaystyle\frac{1}{\sum_{t^{\prime}\leq
t}\log(\mu(t^{\prime}))}\sum_{t^{\prime}\leq t}\log(m(t^{\prime}))$
$\displaystyle=$ $\displaystyle\frac{1}{\sum_{t^{\prime}\leq
t}\log(\mu(t^{\prime}))}\sum_{t^{\prime}\leq
t}\log(\mu(t^{\prime})+z(t^{\prime}))$ $\displaystyle=$
$\displaystyle\frac{1}{\sum_{t^{\prime}\leq
t}\log(\mu(t^{\prime}))}\sum_{t^{\prime}\leq
t}\log(\mu(t^{\prime}))+\log\left(1+\frac{z(t^{\prime})}{\mu(t^{\prime})}\right)$
$\displaystyle=$ $\displaystyle 1+\frac{1}{\sum_{t^{\prime}\leq
t}\log(\mu(t^{\prime}))}\sum_{t^{\prime}\leq
t}\log\left(1+\frac{z(t^{\prime})}{\mu(t^{\prime})}\right)\,.$

It remains to see that the second term of the sum goes to $0$. Clearly, by
proposition 6:

$\frac{\log\left(1+\frac{z(t)}{\mu(t)}\right)}{\log(\mu(t))}\to
0\;,\;\;{\rm(in\;probability)}\,.$

Consequently:

$\frac{1}{\sum_{t^{\prime}\leq
t}\log(\mu(t^{\prime}))}\log\left(\frac{1}{p(\eta(t))}\right)\to
1\;,\;\;{\rm(in\;probability)}\,.$

Finally, we need to compute the asymptotic form of $\sum_{t^{\prime}\leq
t}\log(\mu(t^{\prime}))$. Observing that we have a Riemann sum, one can
consider:

$\sum_{t^{\prime}\leq
t}\log(\mu(t^{\prime}))\sim\int^{t}\log(\sqrt{2t^{\prime}})dt^{\prime}\sim\frac{t}{2}\log
t\,,$

thus concluding the proof. ∎

###  C.4 The entropy of the CRP

We demonstrate here that the CRPM is simple. In consequence, the typical set
can be computed as a function of the entropy. In that case, one can show that
a suitable choice is $\Lambda=\log$ –chosen by the sake of simplicity–,
implying that the associated entropy is Shannon path entropy. However, we
emphasize that this choice is not unique. Given a different choice of $g$, one
could have another $\Lambda$ by which the process is also simple and,
therefore, the typical set could be defined through another form of entropy.
We briefly comment this point in the next section, sketching how another
potential pair $(\Lambda,g)$ functions would work as well.

######  Theorem 4.

The CRPM is simple in $(\Lambda,g(t))=(\log,\frac{t}{2}\log t)$.

###### Proof.

Since the CRPM is compact with compact scale
$(\Lambda,g(t))=(\log,\frac{t}{2}\log t)$, we know that there is a typical
localizer sequence $\epsilon_{1},...,\epsilon_{t},...$ with associated
$\delta_{1},...,\delta_{t},...$, such that
$\lim_{t\to\infty}\epsilon_{t}=\lim_{t\to\infty}\delta_{t}=0$. The paths
belonging to the typical set $A[\epsilon_{t}]$, are those satisfying:

$e^{-(1+\epsilon_{t})\frac{t}{2}\log t}\leq p(x(t))\leq
e^{-(1-\epsilon_{t})\frac{t}{2}\log t}\,.$

In addition, the measure associated to the typical set $A[\epsilon_{t}]$ is
given by:

$\mathbb{P}(A[\epsilon_{t}])\geq 1-\delta_{t}\,.$

In consequence,

$\displaystyle(1-\epsilon_{t})(1-\delta_{t})\frac{t}{2}\log t$
$\displaystyle\leq$ $\displaystyle-\sum_{x(t)\in A[\epsilon_{t}]}p(x(t))\log
p(x(t))$ $\displaystyle\leq$
$\displaystyle(1+\epsilon_{t})(1-\delta_{t})\frac{t}{2}\log t\,.$

Now let’s consider that the complement of the typical set
${\Omega}(t)\setminus A[\epsilon_{t}]$, whose measure is:

$\mathbb{P}({\Omega}\setminus A[\epsilon_{t}])\leq\delta_{t}\,,$

is completely populated by those paths by which:

$x(t)\in{\Omega}\setminus
A[\epsilon_{t}]\;,\,p(x^{*}(t))=\min_{\mathring{\Omega}(t)}\\{p(x(t))\\}\,,$

therefore, for all paths $x(t)\in\mathring{\Omega}(t)$:

$-\log p(x(t))\leq-\log p^{*}(x(t))\,.$

The least probable path is the one that increases the number of tables at
every step, having it probability $p^{*}(x(t))$ of:

$p^{*}(x(t))=\frac{1}{t!}\,,$

leading to $-\log p^{*}(x(t))\sim t\log t$, thanks to the Stirling’s
approximation Abramowitz and Stegun (1964). In that context:

$-\sum_{x(t)\in{\Omega}(t)\setminus A[\epsilon_{t}]}p(x(t))\log
p(x(t))\leq\delta t\log t\,.$

Collecting the above reasoning, and by observing that the defined entropy is
actually the Shannon path entropy, $S_{\Lambda}(\eta(t))=H(\eta(t))$ Cover and
Thomas (2012):

$H(\eta(t))=-\sum_{x(t)\in{\Omega}(t)}p(x(t))\log p(x(t))\,,$

one has that:

$\displaystyle(1-\epsilon_{t})(1-\delta_{t})\frac{t}{2}\log t$
$\displaystyle\leq$ $\displaystyle H(\eta(t))$ $\displaystyle\leq$
$\displaystyle(1+\epsilon_{t})(1-\delta_{t})\frac{t}{2}\log t+\delta_{t}t\log
t\,.$

In consequence, by defining $g(t)=\frac{t}{2}\log t$, one is led to:

$(1-\delta_{t})(1-\epsilon_{t})\leq\frac{H(\eta(t))}{g(t)}\leq(1-\delta_{t})(1+\epsilon_{t})+2\delta_{t}\,.$

Since we know that
$\lim_{t\to\infty}\epsilon_{t}=\lim_{t\to\infty}\delta_{t}=0$ we conclude
that:

$\frac{H(\eta(t))}{g(t)}\to 1\;,$

as we wanted to demonstrate. ∎

###  C.5 A different compact scale $(\Lambda,g)$ for the CRP

We finally briefly comment how another compact scale made of different
$(\Lambda,g)$ functions could be used to characterize the typical set and the
generalized entropy of the CRP. We avoid the technical details, for the sake
of simplicity. We start computing the inverse function of $g$, $g^{-1}$:

$g^{-1}(z)\approx\frac{2z}{\mathbf{W}(2z)}\,,$

where $\mathbf{W}$ is the Lambert function Abramowitz and Stegun (1964), where
only the positive, real branch is taken into account. Then we compose it with
the $\log$ function, thereby defining a new function $\Lambda$ as:

$\Lambda(z)=(g^{-1}\circ\log)(z)\sim\frac{2\log(z)}{\mathbf{W}(2\log(z))}\,.$
(23)

We observe that $\Lambda$ as above defined is a strictly growing, concave
function with continuous second derivatives. Clearly, $(g^{-1}\circ g)(t)\sim
t$. Therefore, as a direct consequence of theorem 3, the CRPM is compact in
$(\Lambda,t)$:

$\frac{1}{g^{-1}\left(\frac{t}{2}\log
t\right)}(g^{-1}\circ\log)\left(\frac{1}{p(\eta(t))}\right)=\frac{1}{t}\Lambda\left(\frac{1}{p(\eta(t))}\right)\to
1\;.$

(in probability). In consequence, the size of the typical set and the typical
probabilities can be approximated from the following generalized entropy
$S_{\Lambda}$:

$S_{\Lambda}(\eta(t))=\sum_{x(t)\in{\Omega}(t)}p(x(t))\frac{2\log\left(\frac{1}{p(x(t))}\right)}{\mathbf{W}\left[2\log\left(\frac{1}{p(x(t))}\right)\right]}\;.$
(24)

where we explicitly wrote it in terms the functional form of
$\Lambda=g^{-1}\circ\log$ as defined in equation (23).