# Renewal model for dependent binary sequences

Marco Zamparo111Dipartimento di Fisica, Università degli Studi di Bari and
INFN, Sezione di Bari, via Amendola 173, aaz 70126 Bari, Italy
aaz E-mail<EMAIL_ADDRESS>
aaz ORCIDiD: 0000-0002-1336-0158

###### Abstract

We suggest to construct infinite stochastic binary sequences by associating
one of the two symbols of the sequence with the renewal times of an underlying
renewal process. Focusing on stationary binary sequences corresponding to
delayed renewal processes, we investigate correlations and the ability of the
model to implement a prescribed autocovariance structure, showing that a large
variety of subexponential decay of correlations can be accounted for. In
particular, robustness and efficiency of the method are tested by generating
binary sequences with polynomial and stretched-exponential decay of
correlations. Moreover, to justify the maximum entropy principle for model
selection, an asymptotic equipartition property for typical sequences that
naturally leads to the Shannon entropy of the waiting time distribution is
demonstrated. To support the comparison of the theory with data, a law of
large numbers and a central limit theorem are established for the time average
of general observables.

Keywords: Dependent binary data; Stationary binary sequences; Inverse
problems; Maximum entropy principle; Law of large numbers; Central limit
theorem

Mathematics Subject Classification 2020: Primary 62B05; 62H22; 60G10,
Secondary 60G17; 82B20

##  1 Introduction

Binary processes arise in natural and social sciences any time a phenomenon is
dichotomized according to the occurrence or non-occurrence of a property of
interest. Modeling, statistical inference from data, and generation of
dependent binary sequences, both finite and infinite, have thus received a lot
of attention in a number of disciplines, such as statistical physics [1],
system biology [2], computational neuroscience [3], actuarial and financial
sciences [4], and machine learning [5], among others. While finite sequences
are generally associated with graphical models [6], infinite sequences are
usually understood as time series.

Modeling and generating binary sequences with prescribed correlations is one
of the major problems to be faced [1]. For finite sequences, the solution to
the problem is in principle represented by the Ising model, which is an
exponential family able to reproduce all inputs in (the interior of) the
correlation polytope [6]. For infinite sequences, the problem of constructing
binary variables with given correlations is more challenging since there is no
universal framework to refer to. Indeed, finite-dimensional distributions
structured according to the Ising model are generally not consistent under
marginalization, so that they cannot be regarded as children of a common
probability measure associated with a stochastic process. On the other hand,
the Ising model is the only known parametric family that can cover all
correlations of a finite number of binary variables. For this reason, in order
to describe and generate infinite binary sequences, researchers have devised
several approaches, each with its own advantages and disadvantages, which can
be grouped in autoregressive models[7, 8, 9, 10, 11, 12, 13, 14], latent
factor models [15, 16, 17], and mixed models which combine autoregression with
latent factors [7, 20]. Autoregressive models are Markov chains with the
property that the current probability of a symbol conditional on the past
history is determined by a linear function of the previous outcomes [7], in a
number corresponding to the order of the chain, linearity being postulated to
not have explosion of parameters. These type of models can produce any
exponential decay of correlations, whereas subexponential decays are off
limits due to Markovianity and finite state space [21]. Latent factor models
rely on an underlying latent process, and the first proposal to generate an
infinite dependent binary sequence was to clip a latent Gaussian process at a
fixed level [15]. Different latent factor approaches are represented by
mixture models whereby the binary symbols are drawn independently with law
determined by the realization of an underlying process, such as a latent
Gaussian process [16] or a latent binary process [17]. Latent factor
approaches can introduce a long-range dependence between the binary variables
and can thus describe both exponential and subexponential decays of
correlations, such as polynomial decay. However, the analysis of clipping
performed in [18] has revealed that there are serious restrictions to the type
of correlations that can be produced. In fact, decay rates, in the case of
exponential decay, and decay exponents, in the case of polynomial decay,
cannot be smaller than a certain minimum threshold. Similar restrictions have
been found in mixture models with latent binary inputs [17]. These
restrictions have been weakened in [19] by means of an algorithm that by
iterating the latent factor model of [17], which transforms the latent binary
input in a binary output, adds dependence to an initial uncorrelated binary
sequence step by step. Other algorithms to generate dependent binary sequences
and their demonstration through numerical experiments are discussed in [22,
23, 24, 25].

In this paper we suggest and investigate a new latent factor approach for
infinite binary sequences that relies on renewal processes [26]. Our proposal
is to associate one of the two symbols of the sequence with the renewal times
of a discrete-time delayed renewal process, and the other symbol with all
other times, thus defining a regenerative phenomenon a la Kingman [27]. Delay
makes it possible to construct stationary binary sequences. This way, we can
offer a flexible and powerful model that is under full mathematical control
and that is able to implement a large variety of subexponential prescriptions
for the correlations, from polynomial to stretched-exponential decays as we
shall demonstrate. Furthermore, reflecting an underlying renewal structure,
generation of the process in numerical experiments is immediate.

The paper is organized as follows. In section 2 we introduce the model and
discuss its Markovian limit. Section 3 is devoted to correlations. In this
section we prove the fundamental property of the model that binary symbols
that follows a renewal time are independent of previous symbols and we show
that the autocovariance solves a renewal equation. Then we investigate the
direct problem of determining the asymptotics of correlations from the waiting
time distribution and the inverse problem of associating a renewal structure
to a prescribed autocovariance for binary symbols. In section 4 we prove limit
theorems for the probability of typical sequences and for the time averages of
general observables. In particular, we demonstrate an asymptotic equipartition
property that naturally introduces the Shannon entropy of the waiting time
distribution and leads to the maximum entropy principle for model selection
[28, 29]. Then we provide a law of large numbers and a central limit theorem
for the normal fluctuations of empirical means, and we apply them to
estimation of the waiting time distribution and of the autocovariance from
data. These results cannot be deduced from the standard limit theory of
regenerative processes with independent cycles [26] and require new arguments.
Conclusions are drawn in section 5. The most technical mathematical proofs are
reported in the appendices in order to not interrupt the flow of the
presentation.

##  2 Definition of the model

Let on a probability space $(\Omega,\mathscr{F},\mathbb{P})$ be given positive
integer-valued random variables $S_{1},S_{2},\ldots$. We construct a binary
stochastic sequence $X:=\\{X_{t}\\}_{t\geq 1}$ with entries valued in
$\mathbb{N}_{2}:=\\{0,1\\}$ by supposing that the variable $S_{n}$ is the
waiting time for the $n$th symbol 1 of the sequence, which occurs at the
renewal time $T_{n}:=S_{1}+\cdots+S_{n}$. Thus, $X_{t}:=1$ if
$t\in\\{T_{n}\\}_{n\geq 1}$ and $X_{t}:=0$ otherwise for each $t\geq 1$. Our
fundamental assumptions are $(i)$ that waiting times are independent and
$(ii)$ that $S_{2},S_{3},\ldots$ have the same distribution, which could
differ from the distribution of $S_{1}$. Under these assumptions, the sequence
$\\{T_{n}\\}_{n\geq 1}$ is a renewal process, delayed if $S_{1}$ is not
distributed as $S_{2}$. We refer to [26] for basics of renewal theory. The
reason for letting $S_{1}$ behave differently from the other waiting times is
that its distribution can be chosen in such a way that the sequence $X$ is
stationary, as explained by the following theorem which is proved in Appendix
A. We recall that the process $X$ is stationary if $\\{X_{t+1}\\}_{t\geq 1}$
is distributed as $\\{X_{t}\\}_{t\geq 1}$, where $\\{X_{t}\\}_{t\geq 1}$ is
understood as a random element in the set $\mathbb{N}_{2}^{\infty}$ of all
binary sequences equipped with the cylinder $\sigma$-field $\mathscr{B}$.
Hereafter, $\mathbb{E}$ denotes expectation with respect to $\mathbb{P}$.

###### Theorem 2.1.

The binary sequence $X$ is stationary if and only if
$\mathbb{E}[S_{2}]<\infty$ and for every $s\geq 1$

$\mathbb{E}[S_{2}]\,\mathbb{P}[S_{1}=s]=\mathbb{P}[S_{2}\geq s].$

Theorem 2.1 recovers well-known conditions for the delayed renewal chain
$\\{T_{n}\\}_{n\geq 1}$ to be stationary, that means that the statistical
properties of the number of renewals in a given temporal window are invariant
with respect to time shifts [26]. Under the hypothesis of stationarity, which
is now made, the only input of the model $X$ is the distribution of the
waiting time $S_{2}$. Depending on the need, we refer to its density
$p:=\mathbb{P}[S_{2}=\cdot\,]$ or to its tail $Q:=\mathbb{P}[S_{2}>\cdot\,]$.
Thus, according to Theorem 2.1, we suppose that
$\mu:=\mathbb{E}[S_{2}]=\sum_{s\geq 1}sp(s)=\sum_{t\geq 0}Q(t)<\infty$ and
that $\mathbb{P}[S_{1}=s]=(1/\mu)\sum_{n\geq s}p(n)$ for every $s\geq 1$. We
notice that $\mathbb{E}[X_{1}]=\mathbb{P}[T_{1}=1]=\mathbb{P}[S_{1}=1]=1/\mu$.

The analysis of the finite-dimensional distributions reveals that if the
sequence $X$ is stationary, then it is time-reversible in the sense that
$(X_{t},\ldots,X_{2},X_{1})$ is distributed as $(X_{1},X_{2},\ldots,X_{t})$
for all $t$. The finite-dimensional distributions of $X$ are provided by the
next proposition, which is demonstrated in Appendix B. We make the usual
conventions that an empty sum is assumed to be 0 and an empty product is
assumed to be 1.

###### Proposition 2.1.

For any integer $t\geq 1$ and numbers $x_{1},x_{2},\ldots,x_{t}$ in
$\mathbb{N}_{2}$

$\displaystyle\pi_{t}(x_{1},x_{2},\ldots,x_{t}):$
$\displaystyle=\mathbb{P}\big{[}X_{1}=x_{1},X_{2}=x_{2},\ldots,X_{t}=x_{t}\big{]}$
$\displaystyle=\frac{1}{\mu}\bigg{[}\sum_{s\geq
t}Q(s)\bigg{]}^{\prod_{n=1}^{t}(1-x_{n})}\prod_{i=1}^{t}\big{[}Q(i-1)\big{]}^{\prod_{n=1}^{i-1}(1-x_{n})x_{i}}$
$\displaystyle\,\cdot\,\,\prod_{i=1}^{t-1}\prod_{j=i+1}^{t}\big{[}p(j-i)\big{]}^{x_{i}\prod_{n=i+1}^{j-1}(1-x_{n})x_{j}}\prod_{j=1}^{t}\big{[}Q(t-j)\big{]}^{x_{j}\prod_{n=j+1}^{t}(1-x_{n})}$
$\displaystyle=\pi_{t}(x_{t},\ldots,x_{2},x_{1})$

with $0^{0}:=1$.

Proposition 2.1 can be used to compute the conditional probability of a symbol
given the past and allows us to get some insight into the dependence structure
of the stochastic sequence $X$. Let us denote by $l_{t}(x_{1},\ldots,x_{t})$
the position of the first symbol $1$ in the binary string
$(x_{1},\ldots,x_{t})$: $l_{t}(x_{1},\ldots,x_{t}):=l$ if $x_{l}=1$ and
$x_{1}=\cdots=x_{l-1}=0$ for some $l\leq t$, and
$l_{t}(x_{1},\ldots,x_{t}):=\infty$ if $x_{1}=\cdots=x_{t}=0$. Proposition 2.1
shows through easy manipulations that for any positive integer $t$ and binary
numbers $x_{1},\ldots,x_{t}$

$\mathbb{P}\big{[}X_{t+1}=1\big{|}X_{t}=x_{1},\ldots,X_{1}=x_{t}\big{]}=\begin{cases}\displaystyle{\frac{Q(t)}{\sum_{s\geq
t}Q(s)}}&\mbox{if }l_{t}(x_{1},\ldots,x_{t})=\infty;\\\\[10.00002pt]
\displaystyle{\frac{p(l)}{Q(l-1)}}&\mbox{if
}l_{t}(x_{1},\ldots,x_{t})=:l<\infty\end{cases}$ (2.1)

provided that $\mathbb{P}[X_{1}=x_{t},\ldots,X_{t}=x_{1}]>0$. Pay attention to
the inverse order of $x_{1},\ldots,x_{t}$ in the conditioning event. Formula
(2.1) draws a link between our model and the so-called “stochastic chains with
memory of variable length” [30]. In this class of models, which can be built
on a larger alphabet than $\mathbb{N}_{2}$, the number of variables involved
in the conditioning event is determined by a “context length function”, which
itself depends on the past variables. The context length function of our model
is exactly the function $l_{t}$ that maps any binary string
$(x_{1},\ldots,x_{t})$ in $l_{t}(x_{1},\ldots,x_{t})$. Since the function
$l_{t}$ is unbounded as the time $t$ goes on, our model constitutes a
stochastic chain having in general memory of unbounded variable length.

In spite of an unbounded context length, the process $X$ is a Markov chain for
certain particular waiting time distributions $p$. The sequence $X$ is a
Markov chain of order $M\geq 1$ if the conditional probability of a symbol
given the past depends only on the state of the last $M$ variables. We can
include sequences of i.i.d. random variables in this definition by letting $M$
to take the value zero. The requirement that the conditional probability (2.1)
is independent of $x_{M+1},\ldots,x_{t}$ for Markovianity of order $M\geq 0$
results in the following corollary of Proposition 2.1, whose proof is reported
in Appendix C.

###### Corollary 2.1.

The binary sequence $X$ is a Markov chain of order $M\geq 0$ if and only if
there exists a real number $\lambda\in[0,1)$ such that
$p(M+s+1)=\lambda^{s}p(M+1)$ for all $s\geq 1$.

##  3 Correlations

The binary sequence $X:=\\{X_{t}\\}_{t\geq 1}$ is a regenerative process with
regeneration points $\\{T_{n}\\}_{n\geq 1}$ and independent cycles [26]. This
means that the past and the future of each renewal event, i.e. of each symbol
1, are independent. Such conditional independence is stated by the following
proposition, whose proof is provided in Appendix D.

###### Proposition 3.1.

For every positive integers $s\leq t$ and binary numbers $x_{1},\ldots,x_{t}$

$\displaystyle\mathbb{P}\big{[}X_{1}=x_{1},\ldots,X_{t}=x_{t}\big{|}X_{s}=1\big{]}=\,\,$
$\displaystyle\mathbb{P}\big{[}X_{1}=x_{1},\ldots,X_{s}=x_{s}\big{|}X_{s}=1\big{]}$
$\displaystyle\cdot\,\,\,$
$\displaystyle\mathbb{P}\big{[}X_{s}=x_{s},\ldots,X_{t}=x_{t}\big{|}X_{s}=1\big{]}.$

Conditional independence associated with renewals is exploited in this section
to study correlations. The covariance of two random variables $Y$ and $Z$ on
the probability space $(\Omega,\mathscr{F},\mathbb{P})$ is denoted by
$\mathrm{cov}[Y,Z]$:

$\mathrm{cov}[Y,Z]:=\mathbb{E}\big{[}(Y-\mathbb{E}[Y])(Z-\mathbb{E}[Z])\big{]}=\mathbb{E}[YZ]-\mathbb{E}[Y]\,\mathbb{E}[Z].$

For every $t\geq 0$, the autocovariance
$\rho_{t}:=\mathrm{cov}[X_{1},X_{t+1}]$ reads $\rho_{t}=c_{t}-c_{0}^{2}$ with

$c_{t}:=\mathbb{E}[X_{1}X_{t+1}].$

Notice that $c_{0}=\mathbb{E}[X_{1}]=1/\mu$. The next proposition, which is
based on Proposition 3.1 and is proved in Appendix E, shows that the sequence
$c:=\\{c_{t}\\}_{t\geq 0}$ solves a renewal equation with waiting time
distribution $p$. As a consequence, the renewal theorem [31] gives
$\lim_{t\uparrow\infty}c_{t}=c_{0}/\mu=c_{0}^{2}$, namely
$\lim_{t\uparrow\infty}\rho_{t}=0$, provided that $p$ is aperiodic. The
probability distribution $p$ is aperiodic if there is no proper sublattice of
$\\{1,2,\dots\\}$ containing its support.

###### Proposition 3.2.

For every integer $t\geq 1$

$c_{t}=\sum_{s=1}^{t}p(s)\,c_{t-s}.$

By resorting to the literature on the renewal equation, we investigate the
direct problem of determining the asymptotics of the sequence $c$, and hence
of the autocovariance, from a given waiting time distribution $p$, as well as
the inverse problem of finding conditions on a prescribed $c$ such that $c$
solves a renewal equation with some probability distribution $p$ of finite
mean. The latter aims to answer the question of which autocovariance
structures can be reproduced by our model. Before that, we want to point out
that the autocovariance of the binary sequence $X$ describes the time
dependence of any temporal correlations, as shown by the following technical
lemma that explores temporal correlations of general observables. The lemma is
proved in Appendix F and will be used in section 4 to address the mixing
properties of $X$.

###### Lemma 3.1.

Fix positive integers $m$ and $n$ and let $f$ and $g$ be two real functions on
$\mathbb{N}_{2}^{m}$ and $\mathbb{N}_{2}^{n}$, respectively, such that
$f(0,\ldots,0)=g(0,\ldots,0)=0$. Set $Z_{t}:=g(X_{t},\ldots,X_{t+n-1})$ for
$t\geq 1$. Then, for all $t\geq 1$

$\displaystyle\mathrm{cov}\big{[}f(X_{1},\ldots,X_{m}),Z_{m+t}\big{]}$
$\displaystyle=\sum_{i=1}^{m}\sum_{j=1}^{n}C_{i,j}(t)\,\frac{\mathbb{E}[\mathds{1}_{\\{S_{1}=i\\}}f(X_{m},\ldots,X_{1})]}{\mathbb{P}[S_{1}=i]}\,\frac{\mathbb{E}[\mathds{1}_{\\{S_{1}=j\\}}Z_{1}]}{\mathbb{P}[S_{1}=j]},$

where for $i\geq 1$ and $j\geq 1$

$C_{i,j}(t):=\sum_{u=1}^{i}\sum_{v=1}^{j}p(i-u)\,\rho_{u+t+v-2}\,p(j-v)$

with $p(0):=-1$.

###  3.1 Autocorrelation: direct problem

Let us study the asymptotics of the autocovariance for a given waiting time
distribution. Pure exponential decay of correlations can be described by
Markov chains as identified by Corollary 2.1 and is somehow trivial. We shall
touch on the exponential behavior of the autocovariance when dealing with the
inverse problem. Here we focus on subexponential decays that account for long-
range dependence that cannot be explained by Markov processes. A natural
setting for subexponentiality in renewal theory was given in [32]. Let the
symbol $\sim$ denotes asymptotic equivalence for sequences: $a_{t}\sim b_{t}$
means $\lim_{t\uparrow\infty}a_{t}/b_{t}=1$. Following [32], we say that a
positive real sequence $a:=\\{a_{t}\\}_{t\geq 0}$ belongs to the class
$\mathscr{S}$ of subexponential sequences if $A:=\sum_{t\geq 0}a_{t}<\infty$,
$a_{t+1}\sim a_{t}$, and $\sum_{n=0}^{t}a_{n}a_{t-n}\sim 2Aa_{t}$. The
requirement $a_{t+1}\sim a_{t}$ prevents $a$ from growing exponentially, thus
justifying the terminology “subexponential”. The asymptotic behavior of the
autocovariance $\rho_{t}$ can be characterized in general when there exists
$\lambda\in(0,1]$ such that $\\{\lambda^{-t}Q(t)\\}_{t\geq 0}\in\mathscr{S}$,
namely when the tail probability $Q$ has exponential rate $\lambda$ and a
subexponential correction that forms a sequence in $\mathscr{S}$. The case
$\lambda=1$ corresponds to a pure subexponential behavior. In fact, Theorem
3.2 of [33] for the rate of convergence of renewal sequences gives the
following result.

###### Theorem 3.1.

Assume that $p$ is aperiodic and that $\\{\lambda^{-t}Q(t)\\}_{t\geq
0}\in\mathscr{S}$ for some $\lambda\in(0,1]$. Then

$\rho_{t}\sim\frac{\sum_{n>t}Q(n)}{\mu\big{[}\sum_{n\geq
0}\lambda^{-n}Q(n)\big{]}^{2}}.$

Subexponential behaviors that find wide application are polynomial decays,
which fall under the umbrella of regular variation, and Weibull-type decays
represented by stretched exponentials. We now suppose $\lambda=1$ and discuss
these decays in some detail. We stress that the necessary condition
$\sum_{t\geq 0}Q(t)<\infty$ for the sequence $\\{Q(t)\\}_{t\geq 0}$ to belong
to $\mathscr{S}$ is satisfied since $\sum_{t\geq 0}Q(t)=\mu<\infty$ by the
hypothesis of stationarity.

####  3.1.1 Polynomial decay

A positive sequence $a:=\\{a_{t}\\}_{t\geq 0}$ is regularly varying if there
exists an index $\alpha\in\mathbb{R}$ and a slowly varying function $\ell$
such that $a_{t}\sim t^{\alpha}\ell(t)$. A real measurable function $\ell$ is
slowly varying if it is positive on a neighborhood of infinity, say
$(\tau,\infty)$ with some $\tau>0$, and satisfies the scale-invariance
property $\lim_{z\uparrow\infty}\ell(\eta z)/\ell(z)=1$ for any number
$\eta>0$. Trivially, a measurable function with a finite positive limit at
infinity is slowly varying. The simplest non-trivial example is represented by
the logarithm. We refer to [34] for the theory of slow and regular variation.
We stress that a slowly varying function $\ell$ is dominated by polynomials in
the sense that $\lim_{z\uparrow\infty}z^{\gamma}\ell(z)=\infty$ and
$\lim_{z\uparrow\infty}z^{-\gamma}\ell(z)=0$ for all $\gamma>0$ according to
Proposition 1.3.6 of [34]. The uniform convergence theorem [34] states that
the scale-invariance property of slowly varying functions actually is uniform
for $\eta$ that belongs to each compact set in $(0,\infty)$. This fact can be
used to show that $a_{t+1}\sim a_{t}$ if $a$ is a regularly varying sequence.
Combined with the dominated convergence theorem, it also shows that
$\sum_{n=0}^{t}a_{n}a_{t-n}\sim 2\sum_{n=0}^{\lfloor
t/2\rfloor}a_{n}a_{t-n}\sim 2Aa_{t}$ when $A:=\sum_{t\geq 0}a_{t}<\infty$,
$\lfloor t/2\rfloor$ denoting the integer part of $t/2$. Thus, any summable
regularly varying sequence is an element of $\mathscr{S}$. Summability imposes
the restriction $\alpha\leq-1$ to the index.

These arguments show that if $Q(t)\sim t^{-\gamma-1}\ell(t)$ with an exponent
$\gamma>0$ and an arbitrary slowly varying function $\ell$, then
$\\{Q(t)\\}_{t\geq 0}\in\mathscr{S}$. In such case we have the asymptotic
equivalence $\sum_{n>t}Q(n)\sim(1/\gamma)t^{-\gamma}\ell(t)$ by Proposition
1.5.10 of [34]. Thus, we get the following corollary of Theorem 3.1.

###### Corollary 3.1.

Assume that $p$ is aperiodic and $Q(t)\sim t^{-\gamma-1}\ell(t)$ with an
exponent $\gamma>0$ and a slowly varying function $\ell$. Then

$\rho_{t}\sim\frac{\ell(t)}{\gamma\mu^{3}t^{\gamma}}.$

In contrast to the latent factor models analyzed in [17] and [18], which can
account for polynomial decay of correlations but not for too small exponents,
Corollary 3.1 of Theorem 3.1 shows that a renewal structure is able to
describe polynomial decays of the autocovariance with any exponent $\gamma>0$.
Actually, the hypothesis $\gamma>0$ is not necessary and we can also have
$\gamma=0$, so that the autocovariance decays slower than any polynomial, but
in this case the asymptotic behavior of $\\{\sum_{n>t}Q(n)\\}_{t\geq 0}$
cannot be resolved in general. Notice that summability of $\\{Q(t)\\}_{t\geq
0}$ when $\gamma=0$ imposes restrictions on $\ell$. For instance, if $Q(t)\sim
t^{-1}(\ln t)^{-\beta-1}$ with a number $\beta>0$, then $\\{Q(t)\\}_{t\geq
0}\in\mathscr{S}$ and Theorem 3.1 gives
$\rho_{t}\sim(1/\mu^{3})\sum_{n>t}Q(n)\sim(1/\beta\mu^{3})(\ln t)^{-\beta}$.

####  3.1.2 Stretched-exponential decay

In [32] the following sufficient condition for subexponentiality was proposed.
Let $h$ be a continuously differentiable real function on a neighborhood of
infinity, say $(\tau,\infty)$ with some $\tau>0$, such that its derivative
$h^{\prime}$ enjoys the properties that $-z^{2}h^{\prime}(z)$ is increasing to
infinity with respect to $z$ and that
$\int_{\tau}^{\infty}e^{\frac{1}{2}z^{2}h^{\prime}(z)}dz<\infty$. Then, a
positive sequence $a:=\\{a_{t}\\}_{t\geq 0}$ such that $A:=\sum_{t\geq
0}a_{t}<\infty$ and $a_{t+1}\sim a_{t}\sim e^{-th(t)}$ satisfies
$\sum_{n=0}^{t}a_{n}a_{t-n}\sim 2Aa_{t}$, and hence belongs to $\mathscr{S}$.
We have used this criterion to investigate the asymptotic behavior of the
autocovariance when $Q(t)\sim e^{-t^{\beta}\ell(t)}$ with a stretching
exponent $\beta\in(0,1)$ and some function $\ell$. The following corollary of
Theorem 3.1, which is proved in Appendix G, gives sufficient conditions on
$\ell$ that imply $\\{Q(t)\\}_{t\geq 0}\in\mathscr{S}$. We point out that
$\ell$ is slowly varying under those conditions.

###### Corollary 3.2.

Assume that $p$ is aperiodic and $Q(t)\sim e^{-t^{\beta}\ell(t)}$ with a
stretching exponent $\beta\in(0,1)$ and a twice continuously differentiable
positive function $\ell$ on a neighborhood of infinity that satisfies
$\lim_{z\uparrow\infty}z\ell^{\prime}(z)/\ell(z)=0$ and
$\lim_{z\uparrow\infty}z^{2}\ell^{\prime\prime}(z)/\ell(z)$ exists. Then

$\rho_{t}\sim\frac{t^{1-\beta}}{\mu^{3}\beta\ell(t)}e^{-t^{\beta}\ell(t)}.$

To conclude, we observe that the hypothesis $\beta<1$ can be relaxed in favor
of $\beta=1$ to come fairly close to exponential decay of correlations while
staying in the framework of subexponential sequences. If for example $Q(t)\sim
e^{-t(\ln t)^{-\gamma}}$ with some number $\gamma>0$, then $Q(t+1)\sim
Q(t)\sim e^{-th(t)}$ with $h(z):=(\ln z)^{-\gamma}$. This function $h$
satisfies the above sufficient condition for subexponentiality, so that
$\rho_{t}\sim(1/\mu^{3})\sum_{n>t}Q(n)\sim(1/\mu^{3})(\ln t)^{\gamma}e^{-t(\ln
t)^{-\gamma}}$ by Theorem 3.1.

###  3.2 Autocorrelation: inverse problem

Let us now investigate the possibility to implement a prescribed
autocovariance. Here the focus is on short time scales since Theorem 3.1 and
its Corollaries 3.1 and 3.2 already settle the issue on long time scales,
demonstrating that a large class of asymptotic prescriptions can be obtained.
We want to understand conditions on a non-negative sequence
$c:=\\{c_{t}\\}_{t\geq 0}$ under which there exists a waiting time
distribution $p$ of finite mean whose associated stationary binary sequence
$X:=\\{X_{t}\\}_{t\geq 1}$ satisfies $c_{t}=\mathbb{E}[X_{1}X_{t+1}]$ for all
$t\geq 0$. For simplicity, we assume that $c_{t}>0$ for every $t\geq 0$. In
the light of Theorem 2.1 and Proposition 3.2, this is tantamount to ask under
which conditions on $c$ there exists a probability distribution $p$ with the
properties $\sum_{s\geq 1}sp(s)=1/c_{0}$ and
$\sum_{s=1}^{t}p(s)\,c_{t-s}=c_{t}$ for all $t\geq 1$. Such a $p$, if any, is
uniquely defined by the renewal equation and meets the requirement
$\sum_{s\geq 1}sp(s)=1/c_{0}$ if and only if
$\lim_{t\uparrow\infty}c_{t}=c_{0}^{2}$. In fact, if $p$ is a probability
distribution such that $\sum_{s=1}^{t}p(s)\,c_{t-s}=c_{t}$ for all $t\geq 1$,
then it is aperiodic since $p(1)=c_{1}/c_{0}>0$. This way, the renewal theorem
[31] gives $\lim_{t\uparrow\infty}c_{t}=c_{0}/\sum_{s\geq 1}sp(s)$ if
$\sum_{s\geq 1}sp(s)<\infty$ and $\lim_{t\uparrow\infty}c_{t}=0$ if
$\sum_{s\geq 1}sp(s)=\infty$.

Finding the minimal conditions on the sequence $c$ for the existence of an
associated waiting time distribution $p$ is a difficult task. We stress that
the problem consists in determining whether or not the function $p$ that
solves the problem $\sum_{s=1}^{t}p(s)\,c_{t-s}=c_{t}$ for every $t\geq 1$ is
non-negative and sums to 1. However, there is a sufficient condition that
covers many applications. A sequence $c:=\\{c_{t}\\}_{t\geq 0}$ is a Kaluza
sequence [27] if $c_{t}>0$ and $c_{t-1}c_{t+1}\geq c_{t}^{2}$ for all $t\geq
1$. It follows that $c_{0}>0$. The following theorem states that the
hypothesis that $c$ is a Kaluza sequence such that
$\lim_{t\uparrow\infty}c_{t}=c_{0}^{2}$ guarantees the existence of an
associated waiting time distribution of finite mean. The proof is provided in
Appendix H.

###### Theorem 3.2.

Let $c:=\\{c_{t}\\}_{t\geq 0}$ be a Kaluza sequence such that
$\lim_{t\uparrow\infty}c_{t}=c_{0}^{2}$. Then, there exists a unique waiting
time distribution $p$ with the properties $\sum_{s\geq 1}sp(s)=1/c_{0}$ and
$\sum_{s=1}^{t}p(s)\,c_{t-s}=c_{t}$ for all $t\geq 1$. As a consequence, the
stationary binary sequence $X:=\\{X_{t}\\}_{t\geq 1}$ associated with $p$
satisfies $c_{t}=\mathbb{E}[X_{1}X_{t+1}]$ for all $t\geq 0$.

We point out that Theorem 3.2 of [33] offers an inverse of Theorem 3.1: if
$c:=\\{c_{t}\\}_{t\geq 0}$ is a Kaluza sequence such that
$\lim_{t\uparrow\infty}c_{t}=c_{0}^{2}$ and $\\{c_{t+1}-c_{t}\\}_{t\geq
0}\in\mathscr{S}$, then there exists a unique associated waiting time
distribution $p$ whose tail $Q$ enjoys the property
$(1/\mu^{3})\sum_{n>t}Q(n)\sim\rho_{t}:=c_{t}-c_{0}^{2}$.

A practical criterion to recognize a Kaluza sequence that puts the emphasis on
the autocovariance is the following. Consider a sequence
$c:=\\{c_{t}\\}_{t\geq 0}$ defined by $c_{0}:=\xi$ and
$c_{t}:=\xi^{2}+me^{-\phi(t)}$ for $t\geq 1$ with constants $\xi\in(0,1]$ and
$m\in[0,\xi(1-\xi)]$ and a concave function $\phi$ such that $\phi(0)=0$ and
$\lim_{z\uparrow\infty}\phi(z)=\infty$. Then, $c$ is a Kaluza sequence and
$\lim_{t\uparrow\infty}c_{t}=c_{0}^{2}$. Indeed,
$c_{0}=\xi^{2}+\xi(1-\xi)\geq\xi^{2}+me^{-\phi(0)}$, so that for each $t\geq
1$

$\displaystyle c_{t-1}c_{t+1}-c_{t}^{2}$
$\displaystyle\geq[\xi^{2}+me^{-\phi(t-1)}][\xi^{2}+me^{-\phi(t+1)}]-[\xi^{2}+me^{-\phi(t)}]^{2}$
$\displaystyle=m\xi^{2}[e^{-\phi(t-1)}+e^{-\phi(t+1)}-2e^{-\phi(t)}]$
$\displaystyle+m^{2}e^{-2\phi(t)}[e^{2\phi(t)-\phi(t-1)-\phi(t+1)}-1].$

This way, the concavity of $\phi$ and the consequent convexity of $e^{-\phi}$
give $c_{t-1}c_{t+1}-c_{t}^{2}\geq 0$ for all $t\geq 1$. We have thus proved
the following corollary of Theorem 3.2.

###### Corollary 3.3.

Let $\xi\in(0,1]$ and $m\in[0,\xi(1-\xi)]$ be two constants and let $\phi$ be
a concave function such that $\phi(0)=0$ and
$\lim_{z\uparrow\infty}\phi(z)=\infty$. Then, there exists a unique waiting
time distribution $p$ of finite mean whose associated stationary binary
sequence $X:=\\{X_{t}\\}_{t\geq 1}$ satisfies $\mathbb{E}[X_{1}]=\xi$ and
$\rho_{t}:=\mathrm{cov}[X_{1},X_{t+1}]=me^{-\phi(t)}$ for all $t\geq 1$.

We appeal to Corollary 3.3 to draw some examples. Our model can implement the
autocovariances $\rho_{t}=m(1+t)^{-\gamma}$ and $\rho_{t}=me^{-\kappa
t^{\beta}}$ for $t\geq 1$ with any real numbers $\xi\in(0,1]$,
$m\in[0,\xi(1-\xi)]$, $\gamma>0$, $\kappa>0$, and $\beta\in(0,1]$. Figure 4.2
compares $\rho_{t}$ with $(1/\mu^{3})\sum_{n>t}Q(n)$ for the two inverse
problems corresponding to the polynomial correlation structures
$c_{t}=1/4+(1/4)(1+t)^{-\gamma}$ for $t\geq 0$ with exponents $\gamma=2$ and
$\gamma=4$, respectively. We see that the earlier mentioned asymptotic
equivalence $\rho_{t}\sim(1/\mu^{3})\sum_{n>t}Q(n)$ is confirmed. Figure 4.2
shows the same comparison for the two stretched-exponential cases
$c_{t}=1/4+(1/4)e^{-t^{\beta}}$ for $t\geq 0$ with exponents $\beta=1/2$ and
$\beta=1$, respectively. This time, the asymptotic equivalence
$\rho_{t}\sim(1/\mu^{3})\sum_{n>t}Q(n)$ is confirmed only for the
subexponential case $\beta=1/2$. The exponential case $\beta=1$ is solved
explicitly by the formulas $\rho_{t}=(1/4)e^{-t}$ and
$(1/\mu^{3})\sum_{n>t}Q(n)=(1/8)(\frac{1+e^{-1}}{2})^{t}$ for all $t\geq 0$,
which shows that the decay rates of the autocovariance and of the associated
waiting time distribution are different.

##  4 Limit theorems

Figure 4.1: Autocovariance $\rho_{t}$ (red) and $(1/\mu^{3})\sum_{n>t}Q(n)$
(blue) versus $t$ for the inverse problem with
$c_{t}=1/4+(1/4)(1+t)^{-\gamma}$ for $t\geq 0$ with $\gamma=2$ (left) and
$\gamma=4$ (right).

Figure 4.2: Autocovariance $\rho_{t}$ (red) and $(1/\mu^{3})\sum_{n>t}Q(n)$
(blue) versus $t$ for the inverse problem with $c_{t}=1/4+(1/4)e^{-t^{\beta}}$
for $t\geq 0$ with $\beta=1/2$ (left) and $\beta=1$ (right).

There are a number of limit theorems for the sequence $X:=\\{X_{t}\\}_{t\geq
1}$ that follow from an underlying ergodic property. In this section we
discuss some of these limit theorems, proving at first ergodicity of a related
dynamical system. We refer to [35] for basics of ergodic theory. Recalling
that $\mathscr{B}$ denotes the $\sigma$-field on $\mathbb{N}_{2}^{\infty}$
generated by the cylinder subsets, it is now convenient to introduce the
probability measure $\mathbb{P}_{o}[\,\cdot\,]:=\mathbb{P}[X\in\cdot\,]$ on
$\mathscr{B}$ and the probability space
$(\mathbb{N}_{2}^{\infty},\mathscr{B},\mathbb{P}_{o})$. We can deduce almost
sure convergence in $(\Omega,\mathscr{F},\mathbb{P})$ from almost sure
convergence in $(\mathbb{N}_{2}^{\infty},\mathscr{B},\mathbb{P}_{o})$. In
fact, since almost sure convergence is defined only in terms of probability
distributions [36], if $G,G_{1},G_{2},\ldots$ are real
$\mathscr{B}$-measurable functions on $\mathbb{N}_{2}^{\infty}$ such that
$\lim_{n\uparrow\infty}G_{n}(x)=G(x)$ for $\mathbb{P}_{o}\mbox{-a.e.\ }x$,
then $\lim_{t\uparrow\infty}G_{t}(X)=G(X)$ $\mathbb{P}$-a.s.. The same can be
said for convergence in mean. The reason to deal with the new probability
space $(\mathbb{N}_{2}^{\infty},\mathscr{B},\mathbb{P}_{o})$ is that it can be
endowed with a measure-preserving transformation. Such transformation is the
left-shift operator $\mathcal{T}$ that maps any binary sequence
$x:=\\{x_{t}\\}_{t\geq 1}\in\mathbb{N}_{2}^{\infty}$ in
$\mathcal{T}x:=\\{x_{t+1}\\}_{t\geq 1}$. The operator $\mathcal{T}$ is
measurable and, due to stationary of $X$, preserves measures, namely
$\mathbb{P}_{o}[\mathcal{T}^{-1}\mathcal{B}]=\mathbb{P}_{o}[\mathcal{B}]$ for
each $\mathcal{B}\in\mathscr{B}$. Indeed, if $\mathcal{B}$ is an element of
$\mathscr{B}$, then
$\mathbb{P}_{o}[\mathcal{T}^{-1}\mathcal{B}]=\mathbb{P}[\mathcal{T}X\in\mathcal{B}]=\mathbb{P}[\\{X_{t+1}\\}_{t\geq
1}\in\mathcal{B}]=\mathbb{P}[\\{X_{t}\\}_{t\geq
1}\in\mathcal{B}]=\mathbb{P}_{o}[\mathcal{B}]$. The transformation
$\mathcal{T}$ is strong-mixing in the sense of ergodic theory, as stated by
the following lemma that in proved in Appendix I. The proof relies on Lemma
3.1.

###### Lemma 4.1.

Assume that $p$ is aperiodic. Then, for all $\mathcal{A}$ and $\mathcal{B}$ in
$\mathscr{B}$

$\lim_{t\uparrow\infty}\mathbb{P}_{o}[\mathcal{A}\cap\mathcal{T}^{-t}\mathcal{B}]=\mathbb{P}_{o}[\mathcal{A}]\,\mathbb{P}_{o}[\mathcal{B}].$

Due to strong-mixing, the transformation $\mathcal{T}$ is ergodic according to
Corollary 1.14.2 of [35], which means that the only members $\mathcal{B}$ of
$\mathscr{B}$ with $\mathcal{T}^{-1}\mathcal{B}=\mathcal{B}$ satisfy
$\mathbb{P}_{o}[\mathcal{B}]=0$ or $\mathbb{P}_{o}[\mathcal{B}]=1$. We use
ergodicity to demonstrate an asymptotic equipartition property, which
justifies the principle of maximum entropy for model selection, and to
investigate the behavior of empirical means.

###  4.1 Asymptotic equipartition property

Description of data requires to select a statistical model, that is a waiting
time distribution $p$ once our framework is considered. One tool for model
selection is the maximum entropy principle [28, 29], which would amount to
pick the probability distribution $p$ of finite mean that meets certain moment
constraints representing the available information and that maximizes the
Shannon entropy. The Shannon entropy $\mathcal{H}(p)$ of $p$ is defined by

$\mathcal{H}(p):=-\sum_{s\geq 1}p(s)\ln p(s)$

with $0\ln 0:=0$. We point out that
$\mathcal{H}(p)\leq\mu\ln\mu+(1-\mu)\ln(\mu-1)<\infty$ whenever
$\mu:=\sum_{s\geq 1}sp(s)<\infty$ since $-p(s)\ln
p(s)\leq\mu^{-s}(\mu-1)^{s-1}-p(s)-p(s)\ln[\mu^{-s}(\mu-1)^{s-1}]$ for all
$s\geq 1$ by concavity. Actually, the largest value of the entropy is
$\mu\ln\mu+(1-\mu)\ln(\mu-1)$, which is attained if and only if
$p(s)=\mu^{-s}(\mu-1)^{s-1}$ for every $s$. The Shannon entropy can be derived
axiomatically as a measure of uncertainty in the outcomes of a random
variable. Instead, in this section we show that the entropy $\mathcal{H}(p)$
of $p$ naturally arises as the answer to the question “how many typical
sequences are there?”. In fact, we demonstrate that there are about
$e^{(t/\mu)\mathcal{H}(p)}$ typical sequences of length $t$, each with
probability about $e^{-(t/\mu)\mathcal{H}(p)}$. It follows that selecting the
waiting time distribution that maximizes the entropy means not excluding
possible sequences arbitrarily. If the only available information is the mean
$\mu$, then the maximum entropy prescription is the waiting time distribution
$p$ defined by $p(s)=\mu^{-s}(\mu-1)^{s-1}$ for all $s$. According to
Corollary 2.1, the binary sequence $X$ associated with such $p$ is a sequence
of i.i.d. binary random variables with mean $1/\mu$.

Let us formalize and explain the above statements. Together with the Shannon
entropy of the waiting time distribution, we consider for each $t\geq 1$ the
Shannon entropy $\mathcal{H}(\pi_{t})$ of the finite-dimensional distribution
$\pi_{t}$ of $X$:

$\mathcal{H}(\pi_{t}):=-\sum_{x_{1}\in\mathbb{N}_{2}}\cdots\sum_{x_{t}\in\mathbb{N}_{2}}\pi_{t}(x_{1},\ldots,x_{t})\ln\pi_{t}(x_{1},\ldots,x_{t}).$

Proposition 2.1 and stationary and reversibility of $X$ give

$\displaystyle\mathcal{H}(\pi_{t})$
$\displaystyle=\ln\mu-\mathbb{E}\Bigg{[}\prod_{n=1}^{t}(1-X_{n})\Bigg{]}\ln\sum_{s\geq
t}Q(s)-2\sum_{s=1}^{t}\mathbb{E}\Bigg{[}\prod_{n=1}^{s-1}(1-X_{n})X_{s}\Bigg{]}\ln
Q(s-1)$
$\displaystyle-\sum_{s=1}^{t}(t-s)\,\mathbb{E}\Bigg{[}X_{1}\prod_{n=2}^{s}(1-X_{n})X_{s+1}\Bigg{]}\ln
p(s)$ $\displaystyle=\ln\mu-\frac{1}{\mu}\sum_{s\geq t}Q(s)\ln\sum_{s\geq
t}Q(s)-\frac{2}{\mu}\sum_{s=1}^{t}Q(s-1)\ln Q(s-1)$
$\displaystyle-\frac{1}{\mu}\sum_{s=1}^{t}(t-s)\,p(s)\ln p(s),$

where we have used the facts that
$\mathbb{E}[\prod_{n=1}^{t}(1-X_{n})]=\mathbb{P}[S_{1}>t]$,
$\mathbb{E}[\prod_{n=1}^{s-1}(1-X_{n})X_{s}]=\mathbb{P}[S_{1}=s]$, and
$\mathbb{E}[X_{1}\prod_{n=2}^{s}(1-X_{n})X_{s+1}]=\mathbb{P}[S_{1}=1,S_{2}=s]$
for all $s$. After invoking the properties of Cesáro means and the dominated
converge theorem, this formula shows that the entropy rate of the sequence $X$
is

$\lim_{t\uparrow\infty}\frac{\mathcal{H}(\pi_{t})}{t}=\frac{\mathcal{H}(p)}{\mu}.$
(4.1)

Then, under ergodicity of the left-shift operator $\mathcal{T}$, the Shannon-
McMillan-Breiman theorem [37] yields for $\mathbb{P}_{o}\mbox{-a.e.\ }x$

$\lim_{t\uparrow\infty}-\frac{1}{t}\ln\pi_{t}(x_{1},\ldots,x_{t})=\lim_{t\uparrow\infty}\frac{\mathcal{H}(\pi_{t})}{t}=\frac{\mathcal{H}(p)}{\mu}.$

These considerations, in combination with Lemma 4.1 and the possibility to
deduce almost sure convergence in $(\Omega,\mathscr{F},\mathbb{P})$ from
almost sure convergence in
$(\mathbb{N}_{2}^{\infty},\mathscr{B},\mathbb{P}_{o})$, prove the following
asymptotic equipartition property, which states that all long typical
sequences of length $t$ have roughly the same probability
$e^{-(t/\mu)\mathcal{H}(p)}$.

###### Theorem 4.1.

Assume that $p$ is aperiodic. Then

$\lim_{t\uparrow\infty}-\frac{\mu}{t}\ln\pi_{t}(X_{1},\ldots,X_{t})=\mathcal{H}(p)\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \mathbb{P}\mbox{-a.s.}.$

Theorem 4.1 implies that there are about $e^{(t/\mu)\mathcal{H}(p)}$ typical
sequences of length $t$. This fact is illustrated by the following corollary,
whose proof is reported in Appendix J. A formal notion of typical set is
needed here. Given a real number $\delta\in(0,1)$, according to [37] we say
that $\mathcal{X}\subseteq\mathbb{N}_{2}^{t}$ is a typical set of length
$t\geq 1$ if $\mathbb{P}[(X_{1},\ldots,X_{t})\in\mathcal{X}]\geq 1-\delta$. We
denote by $|\mathcal{X}|$ the cardinality of a set $\mathcal{X}$.

###### Corollary 4.1.

Fix $\epsilon>0$ and assume that $p$ is aperiodic. The following conclusions
hold for all sufficiently large $t$:

  1. (i)

there exists a typical set $\mathcal{X}_{o}$ of length $t$ such that
$|\mathcal{X}_{o}|\leq e^{(t/\mu)[\mathcal{H}(p)+\epsilon]}$;

  2. (ii)

any typical set $\mathcal{X}$ of length $t$ satisfies $|\mathcal{X}|\geq
e^{(t/\mu)[\mathcal{H}(p)-\epsilon]}$.

###  4.2 Empirical means

Applications to real data require to explain whether or not ensemble averages
can be estimated by means of time averages, also known as empirical means. If
$G$ is a $\mathscr{B}$-measurable function on $\mathbb{N}_{2}^{\infty}$, then
its empirical mean up to time $t\geq 1$ is the random variable

$\frac{1}{t}\sum_{n=1}^{t}G(X_{n},X_{n+1},\ldots)=\frac{1}{t}\sum_{n=0}^{t-1}G(\mathcal{T}^{n}X).$

Birkhoff ergodic theorem [35] tells us that if the left-shift operator
$\mathcal{T}$ is ergodic and the expectation
$\int_{\mathbb{N}_{2}^{\infty}}|G(x)|\,\mathbb{P}_{o}[dx]=\mathbb{E}[|G(X)|]$
is finite, then for $\mathbb{P}_{o}\mbox{-a.e.\ }x$

$\lim_{t\uparrow\infty}\frac{1}{t}\sum_{n=0}^{t-1}G(\mathcal{T}^{n}x)=\int_{\mathbb{N}_{2}^{\infty}}G(x)\,\mathbb{P}_{o}[dx]=\mathbb{E}[G(X)].$

The convergence also holds in mean by Corollary 1.14.1 of [35]. This way,
Lemma 4.1 and the possibility to export convergences from
$(\mathbb{N}_{2}^{\infty},\mathscr{B},\mathbb{P}_{o})$ to
$(\Omega,\mathscr{F},\mathbb{P})$ result in the following law of large
numbers, which gives a positive answer to the possibility of estimating
ensemble averages with time averages. We stress that in most applications the
observable $G$ depends only on a finite number of variables, so that $G$ is
automatically $\mathscr{B}$-measurable and bounded.

###### Theorem 4.2.

Let $G$ be a $\mathscr{B}$-measurable function on $\mathbb{N}_{2}^{\infty}$
such that $\mathbb{E}[|G(X)|]<\infty$. If $p$ is aperiodic, then

$\lim_{t\uparrow\infty}\frac{1}{t}\sum_{n=0}^{t-1}G(\mathcal{T}^{n}X)=\mathbb{E}[G(X)]\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \mathbb{P}\mbox{-a.s. and in mean}.$

We deepen the study of empirical means investigating their normal
fluctuations. Since $X$ is a regenerative process with independent cycles
[26], if $G$ depends on exactly one binary variable, then the normal
fluctuations of its empirical mean are described under the optimal hypothesis
$\mathbb{E}[S_{2}^{2}]=\sum_{s\geq 1}s^{2}p(s)<\infty$ by the central limit
theorem for cumulative processes with a regenerative structure [26]. It is
worth noting that in such case the empirical mean of $G$ up to time $t$ is a
linear function of the number of renewals by $t$, so that even its large
fluctuations can be completely characterized through well-established large
deviation principles for discrete-time renewal-reward processes [38, 39],
which include the counting renewal process. To deal with functions $G$ that
involve more than one variable, and that cannot be tackled by the standard
limit theory of regenerative processes with independent cycles, we resort to
the theory of the central limit theorem for stationary sequences [40]. To
begin with, we introduce the strong mixing coefficient $\alpha_{t}$ of the
sequence $X$, which measures the memory of the past on future events $t$ time
steps later. According to [21], the strong mixing coefficient $\alpha_{t}$, or
$\alpha$-mixing coefficient, of $X$ is defined for each $t\geq 1$ by

$\alpha_{t}:=\sup_{m\geq
1}\,\adjustlimits{\sup}_{\mathcal{A}\in\mathscr{F}_{1}^{m}}{\sup}_{\mathcal{B}\in\mathscr{F}_{m+t}^{\infty}}\bigg{\\{}\Big{|}\mathbb{P}[\mathcal{A}\cap\mathcal{B}]-\mathbb{P}[\mathcal{A}]\,\mathbb{P}[\mathcal{B}]\Big{|}\bigg{\\}}.$

Here $\mathscr{F}_{a}^{b}$ is the $\sigma$-algebra generated by
$X_{a},\ldots,X_{b}$ for $1\leq a\leq b\leq\infty$. The sequence $X$ is strong
mixing in the sense of probability theory if
$\lim_{t\uparrow\infty}\alpha_{t}=0$. The following proposition provides an
estimate of the $\alpha$-mixing coefficient of our model. The proof is based
on Lemma 3.1 and is proposed in Appendix K. Recall that
$\rho_{t}:=\mathrm{cov}[X_{1},X_{t+1}]$.

###### Proposition 4.1.

For each $t\geq 1$

$\alpha_{t}\leq 3\mu^{2}\sum_{n\geq
t}|\rho_{n+1}-\rho_{n}|+4\mu^{2}\sum_{n\geq
t}n\,|\rho_{n+1}-2\rho_{n}+\rho_{n-1}|.$

Empirical means display normal fluctuations when the strong mixing coefficient
decays reasonably fast, and precisely when $\sum_{t\geq 1}\alpha_{t}<\infty$.
In fact, let us consider a bounded observable $G$ and for each $n\geq 0$ let
us set $Z_{n}:=G(\mathcal{T}^{n}X)$ for brevity. Due to boundedness of $G$
Theorem 4.2 tells us that
$\lim_{t\uparrow\infty}(1/t)\sum_{n=0}^{t-1}Z_{n}=\mathbb{E}[Z_{0}]$
$\mathbb{P}\mbox{-a.s.}$ if $p$ is aperiodic. The normal fluctuations of
$(1/t)\sum_{n=0}^{t-1}Z_{n}$ around $\mathbb{E}[Z_{0}]$ are described as
follows by Theorem 18.6.3 of [40], which states the central limit theorem for
functionals of mixing sequences.

###### Theorem 4.3.

Let $G$ be a bounded $\mathscr{B}$-measurable function on
$\mathbb{N}_{2}^{\infty}$ and set $Z_{n}:=G(\mathcal{T}^{n}X)$ for $n\geq 0$.
Assume that $\sum_{t\geq 1}\alpha_{t}<\infty$ and $\sum_{m\geq
1}\mathbb{E}[|Z_{0}-\mathbb{E}[Z_{0}|\mathscr{F}_{1}^{m}]|]<\infty$. Then

$v:=\mathrm{cov}[Z_{0},Z_{0}]+2\sum_{n\geq 1}\mathrm{cov}[Z_{0},Z_{n}]$

is finite and non-negative, and provided that $v\neq 0$

$\lim_{t\uparrow\infty}\mathbb{P}\Bigg{[}\frac{1}{\sqrt{vt}}\sum_{n=0}^{t-1}\big{(}Z_{n}-\mathbb{E}[Z_{0}]\big{)}\leq
z\Bigg{]}=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{z}e^{-\frac{1}{2}\zeta^{2}}d\zeta.$

We point out that the hypotheses of the theorem about $G$ are automatically
satisfied when $G$ depends only on a finite number of variables, since in such
case $\mathbb{E}[Z_{0}|\mathscr{F}_{1}^{m}]=Z_{0}$ for all sufficiently large
$m$. The following lemma based on Proposition 4.1 shows that the finiteness of
the second moment of the waiting time distribution suffices for $\sum_{t\geq
1}\alpha_{t}<\infty$, thus implying the validity of the central limit theorem.
The proof is provided in Appendix L.

###### Lemma 4.2.

The two following statements are equivalent:

  1. (i)

$p$ is aperiodic and $\sum_{s\geq 1}s^{2}p(s)<\infty$;

  2. (ii)

$\sum_{t\geq 1}t|\rho_{t}-\rho_{t-1}|<\infty$.

Either of them implies $\sum_{t\geq 1}\alpha_{t}<\infty$ and $\sum_{s\geq
1}s^{2}p(s)=\mu+2\mu^{3}\sum_{t\geq 0}\rho_{t}$.

We stress that a coupling argument can show, without the need of an explicit
estimate of the $\alpha$-mixing coefficient, that an aperiodic waiting time
distribution satisfies $\sum_{s\geq 1}s^{\gamma}p(s)<\infty$ for a real number
$\gamma>1$ if and only if $\sum_{t\geq 1}t^{\gamma-2}\alpha_{t}<\infty$ (see
[41], Theorem 6.1).

###  4.3 Empirical analyses

Finally, we demonstrate the theory of empirical means through estimation of
the waiting time distribution and of the autocovariance from data. The focus
is on the possibility to identify their decay, that is on the possibility to
estimate $p(s)$ for large $s$ and $\rho_{\tau}$ for large $\tau$. In order to
avoid complications related to nonlinear functions of empirical means, we
imagine that $\mu$ is known in advance. Importantly, we suppose that either
$(i)$ or $(ii)$ of Lemma 4.2 hold, so that if $G$ is an observable that
depends on a finite number of variables, then both the law of large numbers
stated by Theorem 4.2 and the central limit theorem of Theorem 4.3 hold.

Fix an integer $s\geq 1$ and take

$G(x):=\mu x_{1}\prod_{k=2}^{s}(1-x_{k})x_{s+1}$

for all $x\in\mathbb{N}_{2}^{\infty}$.

Figure 4.3: Empirical estimates of $p(s)$ versus $s$ with data sequences of
length $t=10^{6}$ (red) and $t=10^{8}$ (blue) generated by the models defined
by $c_{t}=1/4+(1/4)(1+t)^{-\gamma}$ for $t\geq 0$ with $\gamma=2$ (left) and
$\gamma=4$ (right). Black curves are the theoretical limits $p(s)$.

Figure 4.4: Empirical estimates of $p(s)$ versus $s$ with data sequences of
length $t=10^{6}$ (red) and $t=10^{8}$ (blue) generated by the models defined
by $c_{t}=1/4+(1/4)e^{-t^{\beta}}$ for $t\geq 0$ with $\beta=1/2$ (left) and
$\beta=1$ (right). Black curves are the theoretical limits $p(s)$.

Recalling that $Z_{n}:=G(\mathcal{T}^{n}X)$ for $n\geq 0$, we have
$\mathbb{E}[Z_{0}]=\mu\mathbb{P}[S_{1}=1,S_{2}=s]=p(s)$, so that the empirical
mean of $G$ estimates the waiting time distribution at $s$. Simple
applications of Proposition 3.1 show that $\mathrm{cov}[Z_{0},Z_{n}]=\mu
p(s)-p^{2}(s)$ if $n=0$, $\mathrm{cov}[Z_{0},Z_{n}]=-p^{2}(s)$ if $1\leq n<s$,
and $\mathrm{cov}[Z_{0},Z_{n}]=\mu^{2}p^{2}(s)\rho_{n-s}$ if $n\geq s$. This
way, the variance $v_{s}:=\mathrm{cov}[Z_{0},Z_{0}]+2\sum_{n\geq
1}\mathrm{cov}[Z_{0},Z_{n}]$ introduced by Theorem 4.3 turns out to be

$\displaystyle v_{s}$ $\displaystyle=\mu
p(s)+(1-2s)p^{2}(s)+2\mu^{2}p^{2}(s)\sum_{n\geq 0}\rho_{n}$ $\displaystyle=\mu
p(s)-2sp^{2}(s)+\mu^{-1}p^{2}(s)\sum_{n\geq 1}n^{2}p(n).$

We have made use of the identity $\sum_{s\geq
1}s^{2}p(s)=\mu+2\mu^{3}\sum_{t\geq 0}\rho_{t}$ provided by Lemma 4.2 to get
at the second equality. If a data sequence of length $t$ is given, then we
expect to be able to estimate $p(s)$ for values of $s$ such that
$\sqrt{v_{s}/t}\ll p(s)$. At large $s$, this means values of $s$ such that
$p(s)\gg\mu/t$ because $v_{s}\sim\mu p(s)$. Figure 4.4 shows results of
estimation for two data sequences of length $t=10^{6}$ and $t=10^{8}$,
respectively, when data are generated by the models of Figure 4.2, which
correspond to $c_{t}=1/4+(1/4)(1+t)^{-\gamma}$ for $t\geq 0$ with exponents
$\gamma=2$ and $\gamma=4$. In such cases, the condition $p(s)\gg\mu/t$ for
proper estimation reads $s\ll 1.56\,t^{1/4}$ for $\gamma=2$ and $s\ll
1.65\,t^{1/6}$ for $\gamma=4$. Figure 4.4 reports the same estimation for the
models of Figure 4.2 defined by $c_{t}=1/4+(1/4)e^{-t^{\beta}}$ for $t\geq 0$
with exponents $\beta=1/2$ and $\beta=1$. The condition $p(s)\gg\mu/t$ now
becomes $s\ll\ln^{2}t$ for $\beta=1/2$ and $s\ll 2.63\,\ln t$ for $\beta=1$.

Figure 4.5: Empirical estimates of $\rho_{\tau}$ versus $\tau$ with data
sequences of length $t=10^{6}$ (red) and $t=10^{8}$ (blue) generated by the
models defined by $c_{t}=1/4+(1/4)(1+t)^{-\gamma}$ for $t\geq 0$ with
$\gamma=2$ (left) and $\gamma=4$ (right). Black curves are the theoretical
limits $\rho_{\tau}$.

Figure 4.6: Empirical estimates of $\rho_{\tau}$ versus $\tau$ with data
sequences of length $t=10^{6}$ (red) and $t=10^{8}$ (blue) generated by the
models defined by $c_{t}=1/4+(1/4)e^{-t^{\beta}}$ for $t\geq 0$ with
$\beta=1/2$ (left) and $\beta=1$ (right). Black curves are the theoretical
limits $\rho_{\tau}$.

Moving to the autocovariance, pick an integer $\tau\geq 0$ and consider the
function

$G(x):=x_{1}x_{\tau+1}-1/\mu^{2}$ (4.2)

for all $x\in\mathbb{N}_{2}^{\infty}$. As $\mathbb{E}[Z_{0}]=\rho_{\tau}$, the
empirical mean of $F$ estimates $\rho_{\tau}$. Once again, simple applications
of Proposition 3.1 yield
$\mathrm{cov}[Z_{0},Z_{n}]=\mu^{2}c_{n}^{2}c_{\tau-n}-c_{\tau}^{2}$ if $0\leq
n<\tau$ and $\mathrm{cov}[Z_{0},Z_{n}]=\mu^{2}c_{\tau}^{2}\rho_{n-\tau}$ if
$n\geq\tau$. This way, the variance
$v_{\tau}:=\mathrm{cov}[Z_{0},Z_{0}]+2\sum_{n\geq 1}\mathrm{cov}[Z_{0},Z_{n}]$
reads

$\displaystyle v_{\tau}$ $\displaystyle=\begin{cases}\rho_{0}+2\sum_{n\geq
1}\rho_{n}&\mbox{if }\tau=0;\\\
c_{\tau}-c_{\tau}^{2}+2\sum_{n=1}^{\tau}(\mu^{2}c_{n}^{2}c_{\tau-n}-c_{\tau}^{2})+2\mu^{2}c_{\tau}^{2}\sum_{n\geq
0}\rho_{n}&\mbox{if }\tau\geq 1\end{cases}$
$\displaystyle=\begin{cases}\mu^{-3}\sum_{n\geq 1}n^{2}p(n)-\mu^{-1}&\mbox{if
}\tau=0;\\\
2\sum_{n=0}^{\tau}(\mu^{2}c_{n}^{2}c_{\tau-n}-c_{\tau}^{2})+\mu^{-1}c_{\tau}^{2}\sum_{n\geq
1}n^{2}p(n)-c_{\tau}&\mbox{if }\tau\geq 1.\end{cases}$ (4.3)

Since
$\lim_{\tau\uparrow\infty}v_{\tau}=c_{0}^{2}(1-4c_{0}+3c_{0}^{2})+8c_{0}^{2}\sum_{t\geq
0}\rho_{t}+2\mu\sum_{t\geq 1}\rho_{t}^{2}=:\sigma^{2}$ with $\sigma>0$, we
expect that $\rho_{\tau}$ can be estimated with a data sequence of length $t$
when $\tau$ satisfies $\rho_{\tau}\gg\sigma/\sqrt{t}$. Figure 4.6 illustrates
results of estimation for two data sequences of length $t=10^{6}$ and
$t=10^{8}$, respectively, when data are generated by the models of Figures 4.2
and 4.4. The condition $\rho_{\tau}\gg\sigma/\sqrt{t}$ explicitly is $\tau\ll
0.54\,t^{1/4}$ for $\gamma=2$ and $\tau\ll 0.77\,t^{1/8}$ for $\gamma=4$.
Figure 4.6 provides the same results with reference to the models of Figures
4.2 and 4.4. This time, the condition $\rho_{\tau}\gg\sigma/\sqrt{t}$ is
$\tau\ll 0.25\,\ln^{2}t$ for $\beta=1/2$ and $\tau\ll 0.5\,\ln t$ for
$\beta=1$. The comparison between the waiting time distribution and the
autocovariance shows that the former is easier to estimate than the latter.

A final remark is in order. If $\mu$ is not known in advance, then its inverse
can be estimated through the empirical mean of the observable $G(x):=x_{1}$
for all $x\in\mathbb{N}_{2}^{\infty}$. Apart from an additive constant, this
observable is (4.2) with $\tau=0$. Thus, the variance of its empirical mean
exactly is $v_{0}$ given by (4.3).

##  5 Conclusions

We have explored the use of renewal processes to generate binary sequences
valued in $\\{0,1\\}$, where the symbol 1 marks a renewal event. Focusing on
stationary binary sequences corresponding to delayed renewal processes, we
have demonstrated the ability of the model to account for subexponential
autocovariances with special attention to polynomial and stretched-exponential
decays. Our model performs at least as well as the algorithms proposed in [19]
and [23, 24] that seem to represent the state of the art, but at variance with
them, generating a binary sequence with our model is a trivial task.
Furthermore, our model is under full mathematical control, and this fact
allowed us to build a mathematical theory of its asymptotic properties. In
fact, in addition to shedding light on the asymptotic behaviors of a large
class of correlations and to demonstrating an asymptotic equipartition
property, we have developed a theory for empirical means proving a law of
large numbers and a central limit theorem. The latter describes the typical
fluctuations of empirical means when the second moment of the waiting time
distribution is finite. We leave for future work the study of typical
fluctuations when the second moment of the waiting time distribution is
infinite. In such case, empirical means are expected to be not in the Gaussian
basin of attraction. We also leave for future work the investigation of their
large fluctuations.

## Acknowledgements and Funding

The author is grateful to Alessandro Pelizzola for useful discussions. This
research was funded by Regione Puglia (Italy) through the research programme
REFIN - Research for Innovation (protocol code A7B78549, project number
UNIBA044).

## Author declarations: Conflict of interest

The author has no conflicts to disclose.

## Author declarations: Data availability

No datasets were used to support this study.

##  Appendix A Proof of Theorem 2.1

A monotone class argument [36] shows that the sequence $X$ is stationary,
namely that $\mathbb{P}[\\{X_{t+1}\\}_{t\geq
1}\in\mathcal{B}]=\mathbb{P}[\\{X_{t}\\}_{t\geq 1}\in\mathcal{B}]$ for all
$\mathcal{B}\in\mathscr{B}$, if and only if $(X_{2},\ldots,X_{t+1})$ is
distributed as $(X_{1},\ldots,X_{t})$ for every $t\geq 1$. If the process $X$
is stationary, then for any $s\geq 2$

$\displaystyle\mathbb{P}[T_{1}\geq
s]=\mathbb{P}\big{[}X_{1}=\cdots=X_{s-1}=0\big{]}$
$\displaystyle=\mathbb{P}\big{[}X_{2}=\cdots=X_{s}=0\big{]}$
$\displaystyle=\mathbb{P}\big{[}X_{1}=0,X_{2}=\cdots=X_{s}=0\big{]}$
$\displaystyle+\mathbb{P}\big{[}X_{1}=1,X_{2}=\cdots=X_{s}=0\big{]}$
$\displaystyle=\mathbb{P}[T_{1}\geq s+1]+\mathbb{P}[T_{1}=1,T_{2}\geq s+1],$

which, due to the independence between $S_{1}=T_{1}$ and $S_{2}=T_{2}-T_{1}$,
is tantamount to

$\mathbb{P}[S_{1}=s]=\mathbb{P}[S_{1}=1]\,\mathbb{P}[S_{2}\geq s].$

This identity is trivial for $s=1$ and is valid for all $s\geq 1$ as a
consequence. In combination with the fact that $\sum_{s\geq
1}\mathbb{P}[S_{1}=s]=1$ and $\sum_{s\geq 1}\mathbb{P}[S_{2}\geq
s]=\mathbb{E}[S_{2}]$, it implies $\mathbb{P}[S_{1}=1]>0$ and
$1=\mathbb{P}[S_{1}=1]\,\mathbb{E}[S_{2}]$. Thus, $\mathbb{E}[S_{2}]<\infty$
and $\mathbb{E}[S_{2}]\,\mathbb{P}[S_{1}=s]=\mathbb{P}[S_{2}\geq s]$ for every
$s\geq 1$.

Assume now that $\mathbb{E}[S_{2}]<\infty$ and
$\mathbb{E}[S_{2}]\,\mathbb{P}[S_{1}=s]=\mathbb{P}[S_{2}\geq s]$ for all
$s\geq 1$. Let us prove that $(X_{2},\ldots,X_{t+1})$ is distributed as
$(X_{1},\ldots,X_{t})$ for any given $t\geq 1$. Pick binary numbers
$x_{1},\ldots,x_{t}$. By writing $X_{k+1}$ as
$\mathds{1}_{\\{k+1\in\\{T_{n}\\}_{n\geq 1}\\}}$ and by observing that $S_{1}$
is independent of $\\{T_{n}-S_{1}\\}_{n\geq 1}$ we find

$\displaystyle\mathbb{P}\big{[}X_{2}=x_{1},\ldots,X_{t+1}=x_{t}\big{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\mathds{1}_{\\{S_{1}=1\\}}\prod_{k=1}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k+1\in\\{T_{n}\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\Bigg{]}$
$\displaystyle+\mathbb{E}\Bigg{[}\mathds{1}_{\\{S_{1}>1\\}}\prod_{k=1}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k+1\in\\{T_{n}\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\mathds{1}_{\\{S_{1}=1\\}}\prod_{k=1}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}-S_{1}\\}_{n\geq
2}\\}}=x_{k}\big{\\}}}\Bigg{]}$ $\displaystyle+\sum_{s\geq
1}\mathbb{E}\Bigg{[}\mathds{1}_{\\{S_{1}=s+1\\}}\prod_{k=1}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}-S_{1}+s\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\Bigg{]}$
$\displaystyle=\mathbb{P}[S_{1}=1]\,\mathbb{E}\Bigg{[}\prod_{k=1}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}-S_{1}\\}_{n\geq
2}\\}}=x_{k}\big{\\}}}\Bigg{]}$ $\displaystyle+\sum_{s\geq
1}\mathbb{P}[S_{1}=s+1]\,\mathbb{E}\Bigg{[}\prod_{k=1}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}-S_{1}+s\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\Bigg{]}.$

At this point, we use the formula
$\mathbb{P}[S_{1}=s+1]=\mathbb{P}[S_{1}=s]-\mathbb{P}[S_{1}=1]\,\mathbb{P}[S_{2}=s]$
valid for each $s$, which is an immediate consequence of the hypothesis
$\mathbb{E}[S_{2}]\,\mathbb{P}[S_{1}=s]=\mathbb{P}[S_{2}\geq s]$. This way, by
also noticing that $\\{T_{n}-S_{1}\\}_{n\geq 1}$ is distributed as
$\\{T_{n}-S_{1}-S_{2}\\}_{n\geq 2}$, we get

$\displaystyle\mathbb{P}\big{[}X_{2}=x_{1},\ldots,X_{t+1}=x_{t}\big{]}$
$\displaystyle=\mathbb{P}[S_{1}=1]\,\mathbb{E}\Bigg{[}\prod_{k=1}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}-S_{1}\\}_{n\geq
2}\\}}=x_{k}\big{\\}}}\Bigg{]}$ $\displaystyle+\sum_{s\geq
1}\mathbb{P}[S_{1}=s]\,\mathbb{E}\Bigg{[}\prod_{k=1}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}-S_{1}+s\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\Bigg{]}$ $\displaystyle-\mathbb{P}[S_{1}=1]\sum_{s\geq
1}\mathbb{P}[S_{2}=s]\,\mathbb{E}\Bigg{[}\prod_{k=1}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}-S_{1}-S_{2}+s\\}_{n\geq
2}\\}}=x_{k}\big{\\}}}\Bigg{]}.$

The third term of the r.h.s. cancels with the first one since the independence
between $S_{2}$ and $\\{T_{n}-S_{1}-S_{2}+s\\}_{n\geq 2}$ shows that the
latter is an expanded version of the former. Then

$\displaystyle\mathbb{P}\big{[}X_{2}=x_{1},\ldots,X_{t+1}=x_{t}\big{]}$
$\displaystyle=\sum_{s\geq
1}\mathbb{P}[S_{1}=s]\,\mathbb{E}\Bigg{[}\prod_{k=1}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}-S_{1}+s\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\prod_{k=1}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\Bigg{]}$
$\displaystyle=\mathbb{P}\big{[}X_{1}=x_{1},\ldots,X_{t}=x_{t}\big{]}.$

##  Appendix B Proof of Proposition 2.1

Pick an integer $t\geq 1$ and arbitrary numbers $x_{1},x_{2},\ldots,x_{t}$ in
$\mathbb{N}_{2}$. If $x_{1}=x_{2}=\cdots=x_{t}=0$, then

$\displaystyle\pi_{t}(x_{1},x_{2},\ldots,x_{t}):$
$\displaystyle=\mathbb{P}\big{[}X_{1}=x_{1},X_{2}=x_{2},\ldots,X_{t}=x_{t}\big{]}$
$\displaystyle=\mathbb{P}\big{[}T_{1}>t\big{]}=\mathbb{P}\big{[}S_{1}>t\big{]}=\frac{1}{\mu}\sum_{s\geq
t}Q(s).$

If $x_{1},x_{2},\ldots,x_{t}$ account for exactly $N\geq 1$ ones in positions
$1\leq i_{1}<i_{2}<\cdots<i_{N}\leq t$, then

$\displaystyle\pi_{t}(x_{1},x_{2},\ldots,x_{t})$
$\displaystyle=\mathbb{P}\big{[}T_{1}=i_{1},T_{2}=i_{2},\ldots,T_{N}=i_{N},T_{N+1}>t\big{]}$
$\displaystyle=\mathbb{P}\big{[}S_{1}=i_{1},S_{2}=i_{2}-i_{1},\ldots,S_{N}=i_{N}-i_{N-1},S_{N+1}>t-i_{N}\big{]}$
$\displaystyle=\mathbb{P}\big{[}S_{1}=i_{1}\big{]}\prod_{n=2}^{N}\mathbb{P}\big{[}S_{n}=i_{n}-i_{n-1}\big{]}\,\mathbb{P}\big{[}S_{N+1}>t-i_{N}\big{]}$
$\displaystyle=\frac{1}{\mu}Q(i_{1}-1)\prod_{n=2}^{N}p(i_{n}-i_{n-1})\,Q(t-i_{N}).$

These formulas together with the convention $0^{0}:=1$ show that

$\displaystyle\pi_{t}(x_{1},x_{2},\ldots,x_{t})$
$\displaystyle=\frac{1}{\mu}\bigg{[}\sum_{s\geq
t}Q(s)\bigg{]}^{\prod_{n=1}^{t}(1-x_{n})}\prod_{i=1}^{t}\big{[}Q(i-1)\big{]}^{\prod_{n=1}^{i-1}(1-x_{n})x_{i}}$
$\displaystyle\,\,\cdot\,\,\prod_{i=1}^{t-1}\prod_{j=i+1}^{t}\big{[}p(j-i)\big{]}^{x_{i}\prod_{n=i+1}^{j-1}(1-x_{n})x_{j}}\prod_{j=1}^{t}\big{[}Q(t-j)\big{]}^{x_{j}\prod_{n=j+1}^{t}(1-x_{n})}.$

Finally, by changing $i$ with $t-j+1$ and $j$ with $t-i+1$ in the above
products we realize that

$\pi_{t}(x_{1},x_{2},\ldots,x_{t})=\pi_{t}(x_{t},\ldots,x_{2},x_{1}).$

##  Appendix C Proof of Corollary 2.1

Thanks to the independence between $S_{1}$ and $S_{2}$, for all $t\geq 1$ we
have

$\mathbb{P}\big{[}X_{1}=1,X_{2}=0,\ldots,X_{t+1}=0\big{]}=\mathbb{P}\big{[}T_{1}=1,T_{2}>t+1\big{]}=\mathbb{P}\big{[}S_{1}=1,S_{2}>t\big{]}=\frac{Q(t)}{\mu}.$

Thus, if $X$ is a sequence of i.i.d. binary random variables with mean
$1/\mu$, then for each $t$

$Q(t)=\bigg{(}1-\frac{1}{\mu}\bigg{)}^{t}.$

Setting $\lambda:=1-1/\mu\in[0,1)$, this identity shows that
$p(s+1)=\lambda^{s}p(1)$ for all $s\geq 1$. On the contrary, if
$p(s+1)=\lambda^{s}p(1)$ for all $s\geq 1$ with some real number
$\lambda\in[0,1)$, then Proposition 2.1 demonstrates that $X$ is a sequence of
i.i.d. random variables after some simple algebra.

Let us move to discuss Markovianity of order $M\geq 1$. The sequence $X$ is a
Markov chain of order $M\geq 1$ if for all $t>M$ and $x_{1},\ldots,x_{t+1}$
such that $\mathbb{P}[X_{1}=x_{1},\ldots,X_{t}=x_{t}]>0$

$\mathbb{P}\big{[}X_{t+1}=x_{t+1}\big{|}X_{t}=x_{t},\ldots,X_{1}=x_{1}\big{]}=\mathbb{P}\big{[}X_{t+1}=x_{t+1}\big{|}X_{t}=x_{t},\ldots,X_{t-M+1}=x_{t-M+1}\big{]}.$

The constraint $\mathbb{P}[X_{1}=x_{1},\ldots,X_{t}=x_{t}]>0$ can be dropped
by multiplying both sides by $\mathbb{P}[X_{1}=x_{1},\ldots,X_{t}=x_{t}]$ and
$\mathbb{P}[X_{1}=x_{1},\ldots,X_{M}=x_{M}]$. In fact, the above condition is
tantamount to ask the for all $t>M$ and $x_{1},\ldots,x_{t+1}$

$\displaystyle\mathbb{P}\big{[}X_{1}=x_{1},\ldots,X_{t+1}=x_{t+1}\big{]}\,\mathbb{P}\big{[}X_{t-M+1}=x_{t-M+1},\ldots,X_{t}=x_{t}\big{]}$
$\displaystyle=\mathbb{P}\big{[}X_{1}=x_{1},\ldots,X_{t}=x_{t}\big{]}\,\mathbb{P}\big{[}X_{t-M+1}=x_{t-M+1},\ldots,X_{t+1}=x_{t+1}\big{]},$

which, due to stationarity, reads

$\displaystyle\mathbb{P}\big{[}X_{1}=x_{1},\ldots,X_{t+1}=x_{t+1}\big{]}\,\mathbb{P}\big{[}X_{1}=x_{t-M+1},\ldots,X_{M}=x_{t}\big{]}$
$\displaystyle=\mathbb{P}\big{[}X_{1}=x_{1},\ldots,X_{t}=x_{t}\big{]}\,\mathbb{P}\big{[}X_{1}=x_{t-M+1},\ldots,X_{M+1}=x_{t+1}\big{]}.$
(C.1)

By making the choice $x_{1}=1$ and $x_{2}=\cdots=x_{t+1}=0$ in (C.1) we get
for each $t>M$

$\mathbb{P}\big{[}S_{1}=1,S_{2}>t\big{]}\,\mathbb{P}\big{[}S_{1}>M\big{]}=\mathbb{P}\big{[}S_{1}=1,S_{2}>t-1\big{]}\,\mathbb{P}\big{[}S_{1}>M+1\big{]},$

which, by appealing to the independence between $S_{1}$ and $S_{2}$ once more,
reduces to

$Q(t)\,Q(M)=Q(t-1)\,Q(M+1).$ (C.2)

This is a necessary condition for Markovianity of order $M\geq 1$.

In order to find a sufficient condition, we plug in (C.1) the explicit
expression of finite-dimensional distributions given by Proposition 2.1. By
equating the factors that the two sides of the equation do not have in common
we reach the condition

$p(t)\sum_{s\geq M}Q(s)=Q(t-1)\,Q(M)$ (C.3)

to be satisfied for every $t>M$.

Condition (C.2) imposes that either $Q(M)=0$ or $p(M+s+1)=\lambda^{s}p(M+1)$
for all $s\geq 1$ with $\lambda:=Q(M+1)/Q(M)\in[0,1)$. Since $Q(M)=0$ implies
$p(M+s+1)=0$ for each $s\geq 0$, in any case we can state that (C.2) entails
that there exists a real number $\lambda\in[0,1)$ such that
$p(M+s+1)=\lambda^{s}p(M+1)$ for all $s\geq 1$. A waiting time distribution
that fulfills such relation with some $\lambda\in[0,1)$ solves (C.3), as one
can easily verify.

##  Appendix D Proof of Proposition 3.1

Fix positive integers $s\leq t$ and arbitrary binary numbers
$x_{1},\ldots,x_{t}$. The proposition is trivial if $s=1$, $s=t$, or $1<s<t$
and $x_{s}=0$. Then, assume $1<s<t$ and $x_{s}=1$. Since the condition
$X_{s}=1$ implies that $s\in\\{T_{m}\\}_{m\geq 1}$ and since
$T_{1}<T_{2}<\cdots$, we can write

$\displaystyle\mathbb{P}\big{[}X_{1}=x_{1},\ldots,X_{t}=x_{t}\big{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\prod_{k=1}^{s-1}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\mathds{1}_{\\{s\in\\{T_{m}\\}_{m\geq
1}\\}}\prod_{k=s+1}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\Bigg{]}$ $\displaystyle=\sum_{m\geq
1}\mathbb{E}\Bigg{[}\prod_{k=1}^{s-1}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}\\}_{n=1}^{m}\\}}=x_{k}\big{\\}}}\mathds{1}_{\\{T_{m}=s\\}}\prod_{k=s+1}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k-s\in\\{T_{n}-T_{m}\\}_{n\geq
m}\\}}=x_{k}\big{\\}}}\Bigg{]}.$

For each $m\geq 1$, the sequence $\\{T_{n}-T_{m}\\}_{n\geq m}$ is independent
of $\\{T_{n}\\}_{n=1}^{m}$ and distributed as $\\{T_{n}-T_{1}\\}_{n\geq
1}\\}$, so that

$\displaystyle\mathbb{P}\big{[}X_{1}=x_{1},\ldots,X_{t}=x_{t}\big{]}$
$\displaystyle=\sum_{m\geq
1}\mathbb{E}\Bigg{[}\prod_{k=1}^{s-1}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}\\}_{n=1}^{m}\\}}=x_{k}\big{\\}}}\mathds{1}_{\\{T_{m}=s\\}}\Bigg{]}\,\mathbb{E}\Bigg{[}\prod_{k=s}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k-s\in\\{T_{n}-T_{1}\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\prod_{k=1}^{s-1}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k\in\\{T_{n}\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\mathds{1}_{\\{s\in\\{T_{m}\\}_{m\geq
1}\\}}\Bigg{]}\,\mathbb{E}\Bigg{[}\prod_{k=s}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k-s\in\\{T_{n}-T_{1}\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\Bigg{]}$
$\displaystyle=\mathbb{P}\big{[}X_{1}=x_{1},\ldots,X_{s}=x_{s}\big{]}\,\mathbb{E}\Bigg{[}\prod_{k=s}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k-s\in\\{T_{n}-T_{1}\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\Bigg{]}.$

This identity proves the proposition since by taking the sum over
$x_{1},\ldots,x_{s-1}$ we realize that

$\mathbb{E}\Bigg{[}\prod_{k=s}^{t}\mathds{1}_{\big{\\{}\mathds{1}_{\\{k-s\in\\{T_{n}-T_{1}\\}_{n\geq
1}\\}}=x_{k}\big{\\}}}\Bigg{]}=\mathbb{P}\big{[}X_{s}=x_{s},\ldots,X_{t}=x_{t}\big{|}X_{s}=1\big{]}.$

##  Appendix E Proof of Proposition 3.2

Pick $t\geq 1$. The identity
$1=\sum_{s=1}^{t}X_{t-s+1}\prod_{k=t-s+2}^{t}(1-X_{k})+\prod_{k=1}^{t}(1-X_{k})$
results in the formula
$X_{1}=\sum_{s=1}^{t}X_{1}X_{t-s+1}\prod_{k=t-s+2}^{t}(1-X_{k})$, which allows
us to write down

$\displaystyle c_{t}:=\mathbb{E}\big{[}X_{1}X_{t+1}\big{]}$
$\displaystyle=\sum_{s=1}^{t}\mathbb{E}\Bigg{[}X_{1}X_{t-s+1}\prod_{k=t-s+2}^{t}(1-X_{k})X_{t+1}\Bigg{]}$
$\displaystyle=\sum_{s=1}^{t}\mathbb{E}\Bigg{[}X_{1}\prod_{k=t-s+2}^{t}(1-X_{k})X_{t+1}\Bigg{|}X_{t-s+1}=1\Bigg{]}\,\mathbb{E}[X_{1}].$

This way, Proposition 3.1 shows that

$\displaystyle c_{t}$
$\displaystyle=\sum_{s=1}^{t}\mathbb{E}\big{[}X_{1}\big{|}X_{t-s+1}=1\big{]}\,\mathbb{E}\Bigg{[}\prod_{k=t-s+2}^{t}(1-X_{k})X_{t+1}\Bigg{|}X_{t-s+1}=1\Bigg{]}\,\mathbb{E}[X_{1}]$
$\displaystyle=\sum_{s=1}^{t}\frac{\mathbb{E}[X_{t-s+1}\prod_{k=t-s+2}^{t}(1-X_{k})X_{t+1}]}{\mathbb{E}[X_{1}]}\,c_{t-s}.$

Finally, stationarity yields

$\displaystyle c_{t}$
$\displaystyle=\sum_{s=1}^{t}\frac{\mathbb{E}[X_{1}\prod_{k=2}^{s}(1-X_{k})X_{s+1}]}{\mathbb{E}[X_{1}]}\,c_{t-s}$
$\displaystyle=\sum_{s=1}^{t}\frac{\mathbb{P}[T_{1}=1,T_{2}=s+1]}{\mathbb{P}[T_{1}=1]}\,c_{t-s}=\sum_{s=1}^{t}\mathbb{P}[S_{2}=s]\,c_{t-s}=\sum_{s=1}^{t}p(s)\,c_{t-s}.$

##  Appendix F Proof of Lemma 3.1

Set for brevity $Y:=f(X_{1},\ldots,X_{m})$,
$\Phi_{i}:=X_{m-i+1}\prod_{k=m-i+2}^{m}(1-X_{k})$ for $1\leq i\leq m$, and
$\Psi_{j}(t):=\prod_{k=1}^{j-1}(1-X_{m+t+k-1})X_{m+t+j-1}$ for $j\geq 1$ and
$t\geq 1$. We are going to show that for all $t\geq 1$

$\mathrm{cov}\big{[}Y,Z_{m+t}\big{]}=\sum_{i=1}^{m}\sum_{j=1}^{n}\mathrm{cov}\big{[}\Phi_{i},\Psi_{j}(t)\big{]}\,\frac{\mathbb{E}[f(X_{m},\ldots,X_{1})\mathds{1}_{\\{S_{1}=i\\}}]}{\mathbb{P}[S_{1}=i]}\,\frac{\mathbb{E}[\mathds{1}_{\\{S_{1}=j\\}}Z_{1}]}{\mathbb{P}[S_{1}=j]}$
(F.1)

and, for every $i\geq 1$ and $j\geq 1$,

$\mathrm{cov}\big{[}\Phi_{i},\Psi_{j}(t)\big{]}=C_{i,j}(t).$ (F.2)

We verify (F.1) at first. Pick $t\geq 1$. The identities
$1=\sum_{i=1}^{m}\Phi_{i}+\prod_{k=1}^{m}(1-X_{k})$ and
$1=\sum_{j=1}^{n}\Psi_{j}(t)+\prod_{k=0}^{n-1}(1-X_{m+t+k})$ give
$Y=\sum_{i=1}^{m}Y\Phi_{i}$ and $Z_{m+t}=\sum_{j=1}^{n}\Psi_{j}(t)Z_{m+t}$ as
$f(0,\ldots,0)=0$ and $g(0,\ldots,0)=0$ by hypothesis. Then, we can write down
the formula

$\mathrm{cov}\big{[}Y,Z_{m+t}\big{]}=\sum_{i=1}^{m}\sum_{j=1}^{n}\bigg{\\{}\mathbb{E}\big{[}Y\Phi_{i}\Psi_{j}(t)Z_{m+t}\big{]}-\mathbb{E}\big{[}Y\Phi_{i}\big{]}\mathbb{E}\big{[}\Psi_{j}(t)Z_{m+t}\big{]}\bigg{\\}}.$
(F.3)

Let us manipulate $\mathbb{E}[Y\Phi_{i}\Psi_{j}(t)Z_{m+t}]$ for two given
indices $i\leq m$ and $j\leq n$. The condition $\Phi_{i}\neq 0$ implies
$X_{m-i+1}=1$ and $X_{m-i+2}=\cdots=X_{m}=0$. This way, Proposition 3.1 yields

$\displaystyle\frac{\mathbb{E}[Y\Phi_{i}]}{\mathbb{E}[X_{m-i+1}]}$
$\displaystyle=\mathbb{E}\Big{[}f(X_{1},\ldots,X_{m-i+1},0,\ldots,0)\Phi_{i}\Big{|}X_{m-i+1}=1\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}f(X_{1},\ldots,X_{m-i+1},0,\ldots,0)\Big{|}X_{m-i+1}=1\Big{]}\,\mathbb{E}\Big{[}\Phi_{i}\Big{|}X_{m-i+1}=1\Big{]}$
$\displaystyle=\frac{\mathbb{E}[f(X_{1},\ldots,X_{m-i+1},0,\ldots,0)|X_{m-i+1}=1]\,\mathbb{E}[\Phi_{i}]}{\mathbb{E}[X_{m-i+1}]},$

that is

$\mathbb{E}\big{[}Y\Phi_{i}\big{]}=\mathbb{E}\big{[}f(X_{1},\ldots,X_{m-i+1},0,\ldots,0)\big{|}X_{m-i+1}=1\big{]}\,\mathbb{E}\big{[}\Phi_{i}\big{]}.$

Similarly, as the random quantity $\Psi_{j}(t)Z_{m+t}$ is a function of
$X_{m+t},\ldots,X_{m+t+n-1}$ only, we have

$\mathbb{E}\big{[}Y\Phi_{i}\Psi_{j}(t)Z_{m+t}\big{]}=\mathbb{E}\big{[}f(X_{1},\ldots,X_{m-i+1},0,\ldots,0)\big{|}X_{m-i+1}=1\big{]}\,\mathbb{E}\big{[}\Phi_{i}\Psi_{j}(t)Z_{m+t}\big{]}.$

By continuing with these arguments, since the condition $\Psi_{j}(t)\neq 0$
entails $X_{m+t}=\cdots=X_{m+t+j-2}=0$ and $X_{m+t+j-1}=1$, we realize that

$\mathbb{E}\big{[}\Psi_{j}(t)Z_{m+t}\big{]}=\mathbb{E}\big{[}\Psi_{j}(t)\big{]}\,\mathbb{E}\big{[}g(0,\ldots,0,X_{m+t+j-1},\ldots,X_{m+t+n-1})\big{|}X_{m+t+j-1}=1\big{]}$

and

$\mathbb{E}\big{[}\Phi_{i}\Psi_{j}(t)Z_{m+t}\big{]}=\mathbb{E}\big{[}\Phi_{i}\Psi_{j}(t)\big{]}\,\mathbb{E}\big{[}g(0,\ldots,0,X_{m+t+j-1},\ldots,X_{m+t+n-1})\big{|}X_{m+t+j-1}=1\big{]}.$

These four relations show that

$\mathbb{E}\big{[}Y\Phi_{i}\Psi_{j}(t)Z_{m+t}\big{]}=\frac{\mathbb{E}[Y\Phi_{i}]\,\mathbb{E}[\Phi_{i}\Psi_{j}(t)]\,\mathbb{E}[\Psi_{j}(t)Z_{m+t}]}{\mathbb{E}[\Phi_{i}]\,\mathbb{E}[\Psi_{j}(t)]}.$
(F.4)

On the other hand, reversibility of $X$ gives

$\mathbb{E}[Y\Phi_{i}]=\mathbb{E}\Bigg{[}f(X_{m},\ldots,X_{1})\prod_{k=1}^{i-1}(1-X_{k})X_{i}\Bigg{]}=\mathbb{E}\big{[}f(X_{m},\ldots,X_{1})\mathds{1}_{\\{S_{1}=i\\}}\big{]}$
(F.5)

and

$\mathbb{E}[\Phi_{i}]=\mathbb{P}[S_{1}=i].$ (F.6)

Stationarity of $X$ implies

$\mathbb{E}\big{[}\Psi_{j}(t)Z_{m+t}\big{]}=\mathbb{E}\Bigg{[}\prod_{k=1}^{j-1}(1-X_{k})X_{j}Z_{1}\Bigg{]}=\mathbb{E}\big{[}\mathds{1}_{\\{S_{1}=j\\}}Z_{1}\big{]}$
(F.7)

and

$\mathbb{E}[\Psi_{j}(t)]=\mathbb{P}[S_{1}=j].$ (F.8)

Formula (F.3) in combination with (F.4), (F.5), (F.6), (F.7), and (F.8)
results in (F.1).

Let us move to (F.2), which we prove by induction with respect to $t$. To
begin with, let us verify that $\mathrm{cov}[\Phi_{i},\Psi_{j}(1)]=C_{i,j}(1)$
for each $i\geq 1$ and $j\geq 1$. By recalling (F.6) and (F.8) and by invoking
stationarity of $X$ we find

$\displaystyle\mathrm{cov}\big{[}\Phi_{i},\Psi_{j}(1)\big{]}$
$\displaystyle=\mathbb{E}\Bigg{[}X_{m-i+1}\prod_{k=m-i+2}^{m+j-1}(1-X_{k})X_{m+j}\Bigg{]}-\mathbb{E}[\Phi_{i}]\,\mathbb{E}[\Psi_{j}(1)]$
$\displaystyle=\mathbb{E}\Bigg{[}X_{1}\prod_{k=2}^{i+j-1}(1-X_{k})X_{i+j}\Bigg{]}-\mathbb{P}[S_{1}=i]\,\mathbb{P}[S_{1}=j]$
$\displaystyle=\mathbb{P}[S_{1}=1,S_{2}=i+j-1]-\mathbb{P}[S_{1}=i]\,\mathbb{P}[S_{1}=j]$
$\displaystyle=\mathbb{P}[S_{1}=1]\,p(i+j-1)-\mathbb{P}[S_{1}=i]\,\mathbb{P}[S_{1}=j].$
(F.9)

On the other hand, by definition we have

$\displaystyle C_{i,j}(1)$
$\displaystyle=\sum_{u=1}^{i}\sum_{v=1}^{j}p(i-u)\,\rho_{u+v-1}\,p(j-v)$
$\displaystyle=\sum_{u=1}^{i}\sum_{v=1}^{j}p(i-u)\,c_{u+v-1}\,p(j-v)-\sum_{u=1}^{i}\sum_{v=1}^{j}p(i-u)\,c_{0}^{2}\,p(j-v)$
$\displaystyle=\sum_{u=0}^{i-1}p(u)\sum_{v=0}^{j-1}c_{i+j-u-1-v}\,p(v)-\frac{1}{\mu}\sum_{u=0}^{i-1}p(u)\,\frac{1}{\mu}\sum_{v=0}^{j-1}p(v).$

Proposition 3.2 tells us that
$\sum_{v=1}^{i+j-u-1}c_{i+j-u-1-v}\,p(v)=c_{i+j-u-1}$ if $u\leq i-1$. Then, by
recalling that $p(0):=-1$, we realize that
$\sum_{v=0}^{j-1}c_{i+j-u-1-v}\,p(v)=-\sum_{v=j}^{i+j-u-1}c_{i+j-u-1-v}\,p(v)$
for $u\leq i-1$. The fact that $p(0):=-1$ also gives
$\sum_{u=0}^{i-1}p(u)=-\mathbb{P}[S_{2}\geq i]$ and
$\sum_{v=0}^{j-1}p(v)=-\mathbb{P}[S_{2}\geq j]$. Since
$(1/\mu)\mathbb{P}[S_{2}\geq i]=\mathbb{P}[S_{1}=i]$ and
$(1/\mu)\mathbb{P}[S_{2}\geq j]=\mathbb{P}[S_{1}=j]$ by Theorem 2.1, we obtain

$\displaystyle C_{i,j}(1)$
$\displaystyle=-\sum_{u=0}^{i-1}p(u)\sum_{v=j}^{i+j-u-1}c_{i+j-u-1-v}\,p(v)-\mathbb{P}[S_{1}=i]\,\mathbb{P}[S_{1}=j]$
$\displaystyle=-\sum_{v=j}^{i+j-1}p(v)\sum_{u=0}^{i+j-v-1}c_{i+j-v-1-u}\,p(u)-\mathbb{P}[S_{1}=i]\,\mathbb{P}[S_{1}=j].$

Another application of Proposition 3.2 yields
$\sum_{u=0}^{i+j-v-1}c_{i+j-v-1-u}\,p(u)=0$ if $v<i+j-1$ and
$\sum_{u=0}^{i+j-v-1}c_{i+j-v-1-u}\,p(u)=-c_{0}$ if $v=i+j-1$. Then

$\displaystyle C_{i,j}(1)$
$\displaystyle=p(i+j-1)c_{0}-\mathbb{P}[S_{1}=i]\,\mathbb{P}[S_{1}=j]$
$\displaystyle=\mathbb{P}[S_{1}=1]\,p(i+j-1)-\mathbb{P}[S_{1}=i]\,\mathbb{P}[S_{1}=j].$
(F.10)

Formulas (F.9) and (F.10) demonstrate that
$\mathrm{cov}[\Phi_{i},\Psi_{j}(1)]=C_{i,j}(1)$ for each $i\geq 1$ and $j\geq
1$.

To conclude, let us show that if
$\mathrm{cov}[\Phi_{i},\Psi_{j}(t)]=C_{i,j}(t)$ for all positive indices $i$
and $j$ and some $t\geq 1$, then
$\mathrm{cov}[\Phi_{i},\Psi_{j}(t+1)]=C_{i,j}(t+1)$. Fix $i\geq 1$ and $j\geq
1$. By using the identity
$\Psi_{j}(t+1)=\Psi_{j+1}(t)+X_{m+t}\prod_{k=1}^{j-1}(1-X_{m+t+k})X_{m+t+j}$
and the induction hypothesis we get

$\displaystyle\mathrm{cov}\big{[}\Phi_{i},\Psi_{j}(t+1)\big{]}$
$\displaystyle=C_{i,j+1}(t)+\mathrm{cov}\Bigg{[}\Phi_{i},X_{m+t}\prod_{k=1}^{j-1}(1-X_{m+t+k})X_{m+t+j}\Bigg{]}.$

On the other hand, Proposition 3.1 allows the factorization

$\mathbb{E}\Bigg{[}\Phi_{i}X_{m+t}\prod_{k=1}^{j-1}(1-X_{m+t+k})X_{m+t+j}\Bigg{]}=\frac{\mathbb{E}[\Phi_{i}X_{m+t}]\,\mathbb{E}[X_{m+t}\prod_{k=1}^{j-1}(1-X_{m+t+k})X_{m+t+j}]}{\mathbb{E}[X_{m+t}]},$

which results in

$\displaystyle\mathrm{cov}\Bigg{[}\Phi_{i},X_{m+t}\prod_{k=1}^{j-1}(1-X_{m+t+k})X_{m+t+j}\Bigg{]}$
$\displaystyle=\frac{\mathbb{E}[\Phi_{i}X_{m+t}]\,\mathbb{E}[X_{m+t}\prod_{k=1}^{j-1}(1-X_{m+t+k})X_{m+t+j}]}{\mathbb{E}[X_{m+t}]}$
$\displaystyle-\mathbb{E}[\Phi_{i}]\Bigg{[}X_{m+t}\prod_{k=1}^{j-1}(1-X_{m+t+k})X_{m+t+j}\Bigg{]}$
$\displaystyle=\frac{\mathrm{cov}[\Phi_{i},X_{m+t}]\,\mathbb{E}[X_{m+t}\prod_{k=1}^{j-1}(1-X_{m+t+k})X_{m+t+j}]}{\mathbb{E}[X_{m+t}]}.$

Since $X_{m+t}=\Psi_{1}(t)$, the induction hypothesis and stationarity of $X$
give

$\displaystyle\mathrm{cov}\Bigg{[}\Phi_{i},X_{m+t}\prod_{k=1}^{j-1}(1-X_{m+t+k})X_{m+t+j}\Bigg{]}$
$\displaystyle=\frac{C_{i,1}(t)\,\mathbb{E}[X_{1}\prod_{k=2}^{j}(1-X_{k})X_{j+1}]}{\mathbb{E}[X_{1}]}$
$\displaystyle=\frac{C_{i,1}(t)\,\mathbb{P}[S_{1}=1,S_{2}=j]}{\mathbb{P}[S_{1}=1]}=C_{i,1}(t)\,p(j).$

It follows that

$\displaystyle\mathrm{cov}\big{[}\Phi_{i},\Psi_{j}(t+1)\big{]}$
$\displaystyle=C_{i,j+1}(t)+C_{i,1}(t)\,p(j)$
$\displaystyle=\sum_{u=1}^{i}\sum_{v=1}^{j+1}p(i-u)\,\rho_{u+t+v-2}\,p(j-v+1)-\sum_{u=1}^{i}p(i-u)\,\rho_{u+t-1}\,p(j)$
$\displaystyle=\sum_{u=1}^{i}\sum_{v=1}^{j}p(i-u)\,\rho_{u+t+1+v-2}\,p(j-v)=C_{i,j}(t+1).$

##  Appendix G Proof of Corollary 3.2

Set $\sigma(a):=\sup_{z\geq a}\\{|z\ell^{\prime}(z)/\ell(z)|\\}$ and observe
that $\lim_{a\uparrow\infty}\sigma(a)=0$ by hypothesis. The inequality
$|\ln\ell(b)-\ln\ell(a)|\leq\int_{a}^{b}|\ell^{\prime}(z)/\ell(z)|dz\leq\sigma(a)(\ln
b-\ln a)$ gives for all sufficiently large $a\leq b$ the bound

$\bigg{(}\frac{a}{b}\bigg{)}^{\sigma(a)}\leq\frac{\ell(b)}{\ell(a)}\leq\bigg{(}\frac{b}{a}\bigg{)}^{\sigma(a)}.$
(G.1)

This bound shows that $\ell$ is slowly varying since
$\lim_{a\uparrow\infty}\sigma(a)=0$. It also shows that $\beta
z^{\beta-1}\ell(z)/2\leq(z+1)^{\beta}\ell(z+1)-z^{\beta}\ell(z)\leq 2\beta
z^{\beta-1}\ell(z)$ for each $z$ large enough, so that
$\lim_{z\uparrow\infty}[(z+1)^{\beta}\ell(z+1)-z^{\beta}\ell(z)]=0$ due to the
fact that $\ell$ is dominated by polynomials according to Proposition 1.3.6 of
[34]. Then, $Q(t+1)\sim e^{-(t+1)^{\beta}\ell(t+1)}\sim
e^{-t^{\beta}\ell(t)}\sim Q(t)$.

Let $h$ be the continuously differentiable real function on a neighborhood of
infinity that maps $z$ in $h(z):=z^{\beta-1}\ell(z)$. We now demonstrate that
$-z^{2}h^{\prime}(z)$ is increasing to infinity with respect to $z$ and that
$\int_{\tau}^{\infty}e^{\frac{1}{2}z^{2}h^{\prime}(z)}dz<\infty$ for some
$\tau>0$. It follows that $\\{Q(t)\\}_{t\geq 0}\in\mathscr{S}$ by the
condition for subexponentiality given in [32], so that Theorem 3.1 ensures us
that $\rho_{t}\sim(1/\mu^{3})\sum_{n>t}Q(n)$. As
$\lim_{z\uparrow\infty}z\ell^{\prime}(z)/\ell(z)=0$ by hypothesis, the formula

$\frac{z^{2}h^{\prime}(z)}{z^{\beta}\ell(z)}=\beta-1+\frac{z\ell^{\prime}(z)}{\ell(z)}$

yields

$\lim_{z\uparrow\infty}\frac{z^{2}h^{\prime}(z)}{z^{\beta}\ell(z)}=\beta-1<0.$

Since $\ell$ is dominated by polynomials, this limit entails
$\lim_{z\uparrow\infty}-z^{2}h^{\prime}(z)=\infty$ and at the same time shows
that $\int_{\tau}^{\infty}e^{\frac{1}{2}z^{2}h^{\prime}(z)}dz<\infty$ for some
$\tau$ large enough. It remains to verify that $-z^{2}h^{\prime}(z)$ is
increasing with respect to $z$. The condition
$\lim_{z\uparrow\infty}z\ell^{\prime}(z)/\ell(z)=0$ implies
$\lim_{z\uparrow\infty}z^{2}\ell^{\prime\prime}(z)/\ell(z)=0$ by L’Hôpital’s
rule as $\lim_{z\uparrow\infty}z^{2}\ell^{\prime\prime}(z)/\ell(z)$ is assumed
to exist. Then, the formula

$\displaystyle\frac{[-z^{2}h^{\prime}(z)]^{\prime}}{z^{\beta-1}\ell(z)}$
$\displaystyle=\beta(1-\beta)-2\beta\frac{z\ell^{\prime}(z)}{\ell(z)}-\frac{z^{2}\ell^{\prime\prime}(z)}{\ell(z)}$

results in

$\lim_{z\uparrow\infty}\frac{[-z^{2}h^{\prime}(z)]^{\prime}}{z^{\beta-1}\ell(z)}=\beta(1-\beta)>0.$

This suffices to state that $-z^{2}h^{\prime}(z)$ is increasing with respect
to $z$.

To conclude, let us prove that

$\sum_{n>t}Q(n)\sim\frac{t^{1-\beta}}{\beta\ell(t)}e^{-t^{\beta}\ell(t)}.$
(G.2)

Pick $\epsilon\in(0,\beta\wedge 1-\beta)$ and recall that
$\lim_{a\uparrow\infty}\sigma(a)=0$ by hypothesis. The fact that $Q(t)\sim
e^{-t^{\beta}\ell(t)}$ and (G.1) imply that there exists $t_{o}>0$ such that
$(1-\epsilon)e^{-n^{\beta}\ell(n)}\leq
Q(n)\leq(1+\epsilon)e^{-n^{\beta}\ell(n)}$ and
$t^{\epsilon}n^{\beta-\epsilon}\ell(t)\leq n^{\beta}\ell(n)\leq
n^{\beta+\epsilon}(t+1)^{-\epsilon}\ell(t+1)$ for $n>t>t_{o}$. This way, for
every $t>t_{o}$ we get

$\displaystyle\sum_{n>t}Q(n)\leq(1+\epsilon)\sum_{n>t}e^{-n^{\beta}\ell(n)}$
$\displaystyle\leq(1+\epsilon)\sum_{n>t}e^{-n^{\beta-\epsilon}t^{\epsilon}\ell(t)}$
$\displaystyle\leq(1+\epsilon)\int_{z>t}e^{-z^{\beta-\epsilon}t^{\epsilon}\ell(t)}dz$
$\displaystyle=\frac{1+\epsilon}{\beta-\epsilon}\bigg{[}\frac{1}{t^{\epsilon}\ell(t)}\bigg{]}^{\frac{1}{\beta-\epsilon}}\int_{\zeta>t^{\beta}\ell(t)}\zeta^{\frac{1-\beta+\epsilon}{\beta-\epsilon}}e^{-\zeta}d\zeta$

and

$\displaystyle\sum_{n>t}Q(n)\geq(1-\epsilon)\sum_{n>t}e^{-n^{\beta}\ell(n)}$
$\displaystyle\geq(1-\epsilon)\sum_{n>t}e^{-n^{\beta+\epsilon}(t+1)^{-\epsilon}\ell(t+1)}$
$\displaystyle\geq(1-\epsilon)\int_{z>t+1}e^{-z^{\beta+\epsilon}(t+1)^{-\epsilon}\ell(t+1)}dz$
$\displaystyle=\frac{1-\epsilon}{\beta+\epsilon}\bigg{[}\frac{(t+1)^{\epsilon}}{\ell(t+1)}\bigg{]}^{\frac{1}{\beta+\epsilon}}\int_{\zeta>(t+1)^{\beta}\ell(t+1)}\zeta^{\frac{1-\beta-\epsilon}{\beta+\epsilon}}e^{-\zeta}d\zeta.$

An integration by part shows that
$a^{\gamma}e^{-a}\leq\int_{\zeta>a}\zeta^{\gamma}e^{-\zeta}d\zeta\leq
a^{\gamma}e^{-a}/(1-\gamma/a)$ for every real numbers $\gamma>0$ and
$a>\gamma$. Then

$\sum_{n>t}Q(n)\leq\frac{1+\epsilon}{\beta-\epsilon}\frac{t^{1-\beta}}{\ell(t)}\frac{e^{-t^{\beta}\ell(t)}}{1-\frac{1-\beta+\epsilon}{\beta-\epsilon}\frac{1}{t^{\beta}\ell(t)}}$

and

$\sum_{n>t}Q(n)\geq\frac{1-\epsilon}{\beta+\epsilon}\frac{(t+1)^{1-\beta}}{\ell(t+1)}e^{-(t+1)^{\beta}\ell(t+1)}.$

By recalling that $\ell$ is dominated by polynomials and that
$\lim_{z\uparrow\infty}[(z+1)^{\beta}\ell(z+1)-z^{\beta}\ell(z)]=0$ and by
observing that $\ell(t+1)\sim\ell(t)$ by the bound
$(1+1/t)^{-\sigma(t)}\leq\ell(t+1)/\ell(t)\leq(1+1/t)^{\sigma(t)}$ valid for
sufficiently large $t$, we find

$\frac{1-\epsilon}{\beta+\epsilon}\leq\liminf_{t\uparrow\infty}\ell(t)t^{\beta-1}e^{t^{\beta}\ell(t)}\sum_{n>t}Q(n)\leq\limsup_{t\uparrow\infty}\ell(t)t^{\beta-1}e^{t^{\beta}\ell(t)}\sum_{n>t}Q(n)\leq\frac{1+\epsilon}{\beta-\epsilon}.$

From here, we obtain (G.2) by sending $\epsilon$ to zero.

##  Appendix H Proof of Theorem 3.2

The renewal equation defines a unique function $p$ according to the scheme
$p(1):=c_{1}/c_{0}$ and
$p(t+1):=c_{t+1}/c_{0}-\sum_{s=1}^{t}p(s)c_{t-s+1}/c_{0}$ for $t\geq 1$. We
must verify that $p(s)\geq 0$ for all $s\geq 1$ and that $\sum_{s\geq
1}p(s)=1$.

We verify non-negativity of $p$ by induction. We have $p(1):=c_{1}/c_{0}>0$.
Pick $t\geq 1$ and assume that $p(s)\geq 0$ for every $s\leq t$. To say that
$c$ is a Kaluza sequence means to say that $\\{c_{n}/c_{n-1}\\}_{n\geq 1}$ is
non-decreasing, so that $c_{t-s+1}/c_{t-s}\leq c_{t+1}/c_{t}$ for each $s\leq
t$. Then, the renewal equation yields

$p(t+1)=c_{t+1}/c_{0}-\sum_{s=1}^{t}p(s)\,c_{t-s+1}/c_{0}\geq
c_{t+1}[c_{t}-\sum_{s=1}^{t}p(s)\,c_{t-s}]/(c_{0}c_{t})=0.$

Let us now show that $p$ sums to 1. By combining non-negativity of $p$ with
the renewal equation we get $\sum_{s=1}^{n}p(s)\,c_{t-s}\leq c_{t}$ for all
$t\geq n\geq 1$. This bound gives $\sum_{s\geq 1}p(s)\leq 1$ by sending $t$ to
infinity and by recalling that $\lim_{t\uparrow\infty}c_{t}=c_{0}^{2}$ by
hypothesis. Then, the fact that $\sum_{s\geq 1}p(s)<\infty$ allows us an
application of the dominated convergence theorem to the renewal equation,
which shows that $\sum_{s\geq 1}p(s)=1$ by using
$\lim_{t\uparrow\infty}c_{t}=c_{0}^{2}$ once again.

##  Appendix I Proof of Lemma 4.1

Since $\mathscr{B}$ is the $\sigma$-algebra generated by cylinder subsets of
$\mathbb{N}_{2}^{\infty}$, Theorem 1.17 of [35] tells us that it suffices to
verify the lemma for cylinder subsets. Pick two cylinder subsets $\mathcal{A}$
and $\mathcal{B}$ in $\mathbb{N}_{2}^{\infty}$, so that there exist integers
$m\geq 1$ and $n\geq 1$ and sets $A\subseteq\mathbb{N}_{2}^{m}$ and
$B\subseteq\mathbb{N}_{2}^{n}$ such that
$\mathcal{A}=\\{x\in\mathbb{N}_{2}^{\infty}:(x_{1},\ldots,x_{m})\in A\\}$ and
$\mathcal{B}=\\{x\in\mathbb{N}_{2}^{\infty}:(x_{1},\ldots,x_{n})\in B\\}$. By
introducing the functions $f$ on $\mathbb{N}_{2}^{m}$ and $g$ on
$\mathbb{N}_{2}^{n}$ defined respectively by
$f(x_{1},\ldots,x_{m}):=\mathds{1}_{\\{(x_{1},\ldots,x_{m})\in
A\\}}-\mathds{1}_{\\{(0,\ldots,0)\in A\\}}$ and
$g(x_{1},\ldots,x_{n}):=\mathds{1}_{\\{(x_{1},\ldots,x_{n})\in
B\\}}-\mathds{1}_{\\{(0,\ldots,0)\in B\\}}$, we can write for every $t\geq 1$

$\displaystyle\mathbb{P}_{o}\big{[}\mathcal{A}\cap\mathcal{T}^{-t-m+1}\mathcal{B}\big{]}-\mathbb{P}_{o}\big{[}\mathcal{A}\big{]}\,\mathbb{P}_{o}\big{[}\mathcal{B}\big{]}$
$\displaystyle=\mathbb{P}\big{[}X\in\mathcal{A},\mathcal{T}^{t+m-1}X\in\mathcal{B}]-\mathbb{P}\big{[}X\in\mathcal{A}\big{]}\,\mathbb{P}\big{[}X\in\mathcal{B}\big{]}$
$\displaystyle=\mathbb{P}\big{[}(X_{1},\ldots,X_{m})\in
A,(X_{t+m},\ldots,X_{t+m+n-1})\in B]$
$\displaystyle-\mathbb{P}\big{[}(X_{1},\ldots,X_{m})\in
A\big{]}\,\mathbb{P}\big{[}(X_{1},\ldots,X_{n})\in B\big{]}$
$\displaystyle=\mathrm{cov}\big{[}f(X_{1},\ldots,X_{m}),g(X_{m+t},\ldots,X_{m+t+n-1})\big{]}.$

Since $f(0,\ldots,0)=g(0,\ldots,0)=0$, we can invoke Lemma 3.1 to conclude
that for all $t\geq 1$

$\displaystyle\\!\\!\mathbb{P}_{o}\big{[}\mathcal{A}\cap\mathcal{T}^{-t-m+1}\mathcal{B}\big{]}-\mathbb{P}_{o}\big{[}\mathcal{A}\big{]}\,\mathbb{P}_{o}\big{[}\mathcal{B}\big{]}$
$\displaystyle=\sum_{i=1}^{m}\sum_{j=1}^{n}C_{i,j}(t)\,\frac{\mathbb{E}[\mathds{1}_{\\{S_{1}=i\\}}f(X_{m},\ldots,X_{1})]}{\mathbb{P}[S_{1}=i]}\,\frac{\mathbb{E}[\mathds{1}_{\\{S_{1}=j\\}}g(X_{1},\ldots,X_{n})]}{\mathbb{P}[S_{1}=j]},$
(I.1)

where for $i\geq 1$ and $j\geq 1$

$C_{i,j}(t):=\sum_{u=1}^{i}\sum_{v=1}^{j}p(i-u)\,\rho_{u+t+v-2}\,p(j-v)$

with $p(0):=-1$. The only dependence on $t$ is contained in the
autocovariance. Formula I.1 proves the lemma since aperiodicity of $p$ entails
$\lim_{t\uparrow\infty}\rho_{t}=0$.

##  Appendix J Proof of Corollary 4.1

Set
$\mathcal{Y}_{t}:=\\{(x_{1},\ldots,x_{t})\in\mathbb{N}_{2}^{t}:|(\mu/t)\ln\pi_{t}(x_{1},\ldots,x_{t})+\mathcal{H}(p)|\leq\epsilon\\}$
for every integer $t\geq 1$. Theorem 4.1 yields
$\lim_{t\uparrow\infty}\mathbb{P}[(X_{1},\ldots,X_{t})\in\mathcal{Y}_{t}]=1$,
so that $\mathbb{P}[(X_{1},\ldots,X_{t})\in\mathcal{Y}_{t}]\geq 1-\delta$ for
all sufficiently large $t$. On the other hand, the bounds
$\sum_{(x_{1},\ldots,x_{t})\in\mathcal{Y}_{t}}\pi_{t}(x_{1},\ldots,x_{t})\leq
1$ and $\pi_{t}(x_{1},\ldots,x_{t})\geq e^{-(t/\mu)[\mathcal{H}(p)+\epsilon]}$
for $(x_{1},\ldots,x_{t})\in\mathcal{Y}_{t}$ result in $|\mathcal{Y}_{t}|\leq
e^{(t/\mu)[\mathcal{H}(p)+\epsilon]}$. Thus, $(i)$ is proved by taking
$\mathcal{X}_{o}=\mathcal{Y}_{t}$.

Let us verify $(ii)$. Pick a typical set $\mathcal{X}$ of length $t$ and set
$\mathcal{Y}_{t}:=\\{(x_{1},\ldots,x_{t})\in\mathbb{N}_{2}^{t}:|(\mu/t)\ln\pi_{t}(x_{1},\ldots,x_{t})+\mathcal{H}(p)|\leq\epsilon/2\\}$
for $t\geq 1$. Since $\mathbb{P}[(X_{1},\ldots,X_{t})\in\mathcal{X}]\geq
1-\delta$ by definition with $\delta\in(0,1)$ and
$\lim_{t\uparrow\infty}\mathbb{P}[(X_{1},\ldots,X_{t})\in\mathcal{Y}_{t}]=1$
by Theorem 4.1, for all sufficiently large $t$ we have

$\displaystyle\mathbb{P}\big{[}(X_{1},\ldots,X_{t})\in\mathcal{Y}_{t}\cap\mathcal{X}\big{]}$
$\displaystyle=\mathbb{P}\big{[}(X_{1},\ldots,X_{t})\in\mathcal{Y}_{t}\big{]}+\mathbb{P}\big{[}(X_{1},\ldots,X_{t})\in\mathcal{X}\big{]}$
$\displaystyle-\mathbb{P}\big{[}(X_{1},\ldots,X_{t})\in\mathcal{Y}_{t}\cup\mathcal{X}\big{]}$
$\displaystyle\geq\mathbb{P}\big{[}(X_{1},\ldots,X_{t})\in\mathcal{Y}_{t}\big{]}-\delta\geq
e^{-(t/\mu)(\epsilon/2)}.$

At the same time

$\displaystyle\mathbb{P}\big{[}(X_{1},\ldots,X_{t})\in\mathcal{Y}_{t}\cap\mathcal{X}\big{]}$
$\displaystyle=\sum_{(x_{1},\ldots,x_{t})\in\mathcal{Y}_{t}\cap\mathcal{X}}\pi_{t}(x_{1},\ldots,x_{t})$
$\displaystyle\leq|\mathcal{X}|e^{-(t/\mu)[\mathcal{H}(p)-\epsilon/2]}.$

These two bounds prove $(ii)$.

##  Appendix K Proof of Proposition 4.1

Fix $t\geq 1$ and assume that $\sum_{n\geq t}|\rho_{n+1}-\rho_{n}|<\infty$ and
$\sum_{n\geq t}n\,|\rho_{n+1}-2\rho_{n}+\rho_{n-1}|<\infty$, otherwise there
is nothing to prove. We verify first that for all positive integers $m$ and
$n$ and all sets $\mathcal{A}\in\mathscr{F}_{1}^{m}$ and
$\mathcal{B}\in\mathscr{F}_{m+t}^{m+t+n-1}$

$\Big{|}\mathbb{P}[\mathcal{A}\cap\mathcal{B}]-\mathbb{P}[\mathcal{A}]\,\mathbb{P}[\mathcal{B}]\Big{|}\leq\sum_{i\geq
1}\sum_{j\geq 1}|C_{i,j}(t)|.$ (K.1)

Coefficients $C_{i,j}(t)$ were introduced by Lemma 3.1. A monotone class
argument [36] allows us to extend the bound (K.1) to all
$\mathcal{B}\in\mathscr{F}_{m+t}^{\infty}$, so that $\alpha(t)\leq\sum_{i\geq
1}\sum_{j\geq 1}|C_{i,j}(t)|$. Then we demonstrate that

$\sum_{i\geq 1}\sum_{j\geq 1}|C_{i,j}(t)|\leq 3\mu^{2}\sum_{n\geq
t}|\rho_{n+1}-\rho_{n}|+4\mu^{2}\sum_{n\geq
t}n\,|\rho_{n+1}-2\rho_{n}+\rho_{n-1}|.$ (K.2)

Let us verify (K.1). Pick $m\geq 1$, $n\geq 1$,
$\mathcal{A}\in\mathscr{F}_{1}^{m}$, and
$\mathcal{B}\in\mathscr{F}_{m+t}^{m+t+n-1}$. Since $\mathcal{A}$ is measurable
with respect to $\mathscr{F}_{1}^{m}$, there exists a set
$A\subseteq\mathbb{N}_{2}^{m}$ such that
$\mathcal{A}=\\{\omega\in\Omega:(X_{1}(\omega),\ldots,X_{m}(\omega))\in A\\}$.
In the same way, there exists $B\subseteq\mathbb{N}_{2}^{n}$ with the property
that
$\mathcal{B}=\\{\omega\in\Omega:(X_{m+t}(\omega),\ldots,X_{m+t+n-1}(\omega))\in
B\\}$. Set $f(x_{1},\ldots,x_{m}):=\mathds{1}_{\\{(x_{1},\ldots,x_{m})\in
A\\}}-\mathds{1}_{\\{(0,\ldots,0)\in A\\}}$ and
$g(x_{1},\ldots,x_{n}):=\mathds{1}_{\\{(x_{1},\ldots,x_{n})\in
B\\}}-\mathds{1}_{\\{(0,\ldots,0)\in B\\}}$. Then,
$f(0,\ldots,0)=g(0,\ldots,0)=0$ and Lemma 3.1 yields

$\displaystyle\mathbb{P}[\mathcal{A}\cap\mathcal{B}]-\mathbb{P}[\mathcal{A}]\,\mathbb{P}[\mathcal{B}]$
$\displaystyle=\mathbb{P}\big{[}(X_{1},\ldots,X_{m})\in
A,(X_{m+t},\ldots,X_{m+t+n-1})\in B\big{]}$
$\displaystyle-\mathbb{P}\big{[}(X_{1},\ldots,X_{m})\in
A\big{]}\,\mathbb{P}\big{[}(X_{m+t},\ldots,X_{m+t+n-1})\in B\big{]}$
$\displaystyle=\mathrm{cov}\big{[}f(X_{1},\ldots,X_{m}),g(X_{m+t},\ldots,X_{m+t+n-1})\big{]}$
$\displaystyle=\sum_{i=1}^{m}\sum_{j=1}^{n}C_{i,j}(t)\,\frac{\mathbb{E}[\mathds{1}_{\\{S_{1}=i\\}}f(X_{m},\ldots,X_{1})]}{\mathbb{P}[S_{1}=i]}\,\frac{\mathbb{E}[\mathds{1}_{\\{S_{1}=j\\}}g(X_{1},\ldots,X_{n})]}{\mathbb{P}[S_{1}=j]},$

where for $i\geq 1$ and $j\geq 1$

$C_{i,j}(t):=\sum_{u=1}^{i}\sum_{v=1}^{j}p(i-u)\,\rho_{u+t+v-2}\,p(j-v)$

with $p(0):=-1$. As $f$ and $g$ can only take the values $-1$, $0$, and $1$,
this formula results in

$\Big{|}\mathbb{P}[\mathcal{A}\cap\mathcal{B}]-\mathbb{P}[\mathcal{A}]\,\mathbb{P}[\mathcal{B}]\Big{|}\leq\sum_{i=1}^{m}\sum_{j=1}^{n}|C_{i,j}(t)|\leq\sum_{i\geq
1}\sum_{j\geq 1}|C_{i,j}(t)|.$

Let us move now to (K.2). Simple algebra shows that for all $i\geq 1$ and
$j\geq 1$

$\displaystyle C_{i,j}(t)$
$\displaystyle=\rho_{i+t+j-2}-\sum_{u=1}^{i-1}p(i-u)\,\rho_{u+t+j-2}-\sum_{v=1}^{j-1}\rho_{i+t+v-2}\,p(j-v)$
$\displaystyle+\sum_{u=1}^{i-1}\sum_{v=1}^{j-1}p(i-u)\,\rho_{u+t+v-2}\,p(j-v)$
$\displaystyle=\rho_{i+t+j-2}\,Q(i-1)Q(j-1)$
$\displaystyle+\sum_{u=1}^{i-1}p(u)\,\big{(}\rho_{i+t+j-2}-\rho_{i+t+j-2-u}\big{)}\,Q(j-1)+\sum_{v=1}^{j-1}Q(i-1)\,\big{(}\rho_{i+t+j-2}-\rho_{i+t+j-2-v}\big{)}\,p(v)$
$\displaystyle+\sum_{u=1}^{i-1}\sum_{v=1}^{j-1}p(u)\,\big{(}\rho_{i+t+j-2}-\rho_{i+t+j-2-v}-\rho_{i+t+j-2-u}+\rho_{i+t+j-2-u-v}\big{)}\,p(v).$

We recall that $Q$ is the tail of the probability distribution $p$. This
identity leads to the bound

$\sum_{i\geq 1}\sum_{j\geq 1}|C_{i,j}(t)|\leq K_{1}+2K_{2}+K_{3}$ (K.3)

with

$K_{1}:=\sum_{i\geq 0}\sum_{j\geq 0}|\rho_{i+t+j}|\,Q(i)Q(j),$
$K_{2}:=\sum_{i\geq 1}\sum_{j\geq
0}\sum_{u=1}^{i}p(u)\,\big{|}\rho_{i+t+j}-\rho_{i+t+j-u}\big{|}\,Q(j),$

and

$K_{3}:=\sum_{i\geq 1}\sum_{j\geq
1}\sum_{u=1}^{i}\sum_{v=1}^{j}p(u)\,\big{|}\rho_{i+t+j}-\rho_{i+t+j-v}-\rho_{i+t+j-u}+\rho_{i+t+j-u-v}\big{|}\,p(v).$

We address $K_{1}$, $K_{2}$, and $K_{3}$ separately.

To begin with, we stress that the condition $\sum_{n\geq
t}|\rho_{n+1}-\rho_{n}|<\infty$ implies $\lim_{n\uparrow\infty}\rho_{n}=0$. In
fact, if $p$ is not aperiodic, then there exists an integer $\tau>1$ such that
$p(s)=0$ unless $s$ is a multiple of $\tau$. The renewal equation gives
$c_{n}=0$ unless $n$ is a multiple of $\tau$, and the renewal theorem [31]
shows that $\lim_{k\uparrow\infty}c_{k\tau}=1/\mu$. In this situation,
$|\rho_{k\tau+1}-\rho_{k\tau}|=|c_{k\tau+1}-c_{k\tau}|=|c_{k\tau}|\geq
1/(2\mu)$ for all sufficiently large $k$, which contradicts the hypothesis
$\sum_{n\geq t}|\rho_{n+1}-\rho_{n}|<\infty$. Thus, $\sum_{n\geq
t}|\rho_{n+1}-\rho_{n}|<\infty$ requires that $p$ is aperiodic, and hence that
$\lim_{n\uparrow\infty}\rho_{n}=0$. The limit
$\lim_{n\uparrow\infty}\rho_{n}=0$ justifies the identity
$\rho_{i+t+j}=\sum_{n\geq i+t+j}(\rho_{n}-\rho_{n+1})$, which yields the
inequality $|\rho_{i+t+j}|\leq|\sum_{n\geq t}|\rho_{n+1}-\rho_{n}|$, which
results in the bound

$K_{1}\leq\mu^{2}\sum_{n\geq t}|\rho_{n+1}-\rho_{n}|.$ (K.4)

As far as $K_{2}$ is concerned, by rearranging indices we get

$K_{2}=\sum_{u\geq 1}\sum_{l\geq
t}p(u)\,|\rho_{l+u}-\rho_{l}|\sum_{j=0}^{l-t}Q(j)\leq\mu\sum_{u\geq
1}\sum_{l\geq t}p(u)\,|\rho_{l+u}-\rho_{l}|.$

At this point, the bound
$|\rho_{l+u}-\rho_{l}|\leq\sum_{n=l}^{l+u-1}|\rho_{n+1}-\rho_{n}|$ shows that

$\displaystyle K_{2}$ $\displaystyle\leq\mu\sum_{u\geq 1}\sum_{l\geq
t}p(u)\sum_{n=l}^{l+u-1}|\rho_{n+1}-\rho_{n}|$ $\displaystyle=\mu\sum_{n\geq
t}\sum_{u\geq 1}(n-t+1\wedge u)\,p(u)\,|\rho_{n+1}-\rho_{n}|$
$\displaystyle\leq\mu\sum_{n\geq t}\sum_{u\geq
1}up(u)\,|\rho_{n+1}-\rho_{n}|=\mu^{2}\sum_{n\geq t}|\rho_{n+1}-\rho_{n}|.$
(K.5)

Finally, let us consider $K_{3}$. By rearranging indices we can write

$\displaystyle K_{3}$ $\displaystyle=\sum_{l\geq t}\sum_{u\geq 1}\sum_{v\geq
1}(l-t+1)\,p(u)\,\big{|}\rho_{l+u+v}-\rho_{l+u}-\rho_{l+v}+\rho_{l}\big{|}\,p(v)$
$\displaystyle\leq 2\sum_{l\geq t}l\sum_{u\geq 1}\sum_{v\geq
u}p(u)\,\big{|}\rho_{l+u+v}-\rho_{l+u}-\rho_{l+v}+\rho_{l}\big{|}\,p(v).$

In order to go one step further, setting
$\Delta_{n}:=\rho_{n+1}-2\rho_{n}+\rho_{n-1}$ for brevity, we resort to the
identity

$\rho_{l+u+v}-\rho_{l+u}-\rho_{l+v}+\rho_{l}=\sum_{k=v+1}^{u+v}(u+v-k)\,\Delta_{k+l}+\sum_{k=1}^{v}u\wedge
k\,\Delta_{k+l},$

which holds for $u\leq v$ as one can easily verify. This identity gives

$K_{3}\leq 2M_{1}+2M_{2}$ (K.6)

with

$M_{1}:=\sum_{l\geq t}l\sum_{u\geq 1}\sum_{v\geq
u}p(u)\sum_{k=v+1}^{u+v}(u+v-k)\,|\Delta_{k+l}|\,p(v)$

and

$M_{2}:=\sum_{l\geq t}l\sum_{u\geq 1}\sum_{v\geq u}p(u)\sum_{k=1}^{v}u\wedge
k\,|\Delta_{k+l}|\,p(v).$

By rearranging indices we can write

$\displaystyle M_{1}$ $\displaystyle=\sum_{n\geq
t+2}|\Delta_{n}|\sum_{u=1}^{n-t-1}\sum_{v=u}^{n-t-1}p(u)\,p(v)\sum_{l=t\vee(n-u-v)}^{n-v-1}l(u+v-n+l)$
$\displaystyle\leq\sum_{n\geq
t+2}|\Delta_{n}|\sum_{u=1}^{n-t-1}\sum_{v=u}^{n-t-1}p(u)\,p(v)\,nu\big{[}n-v-t\vee(n-u-v)\big{]}.$

Under the condition $u\leq v$, if $n-u-v\geq t$, then $n-v-t\vee(n-u-v)=u\leq
v$ and if $n-u-v<t$, then $n-v-t\vee(n-u-v)=n-v-t<u\leq v$. We thus have

$M_{1}\leq\sum_{n\geq
t+2}|\Delta_{n}|\sum_{u=1}^{n-t-1}\sum_{v=u}^{n-t-1}p(u)\,p(v)\,nuv\leq\mu^{2}\sum_{n\geq
t}n\,|\Delta_{n}|.$ (K.7)

Moving to $M_{2}$, by rearranging indices we find

$\displaystyle M_{2}$ $\displaystyle\leq\sum_{l\geq t}l\sum_{u\geq
1}\sum_{v\geq u}up(u)\sum_{k=1}^{v}|\Delta_{k+l}|\,p(v)$
$\displaystyle=\sum_{n\geq t+1}|\Delta_{n}|\sum_{u\geq 1}\sum_{v\geq
u}up(u)\,p(v)\sum_{l=t\vee(n-v)}^{n-1}l$ $\displaystyle\leq\sum_{n\geq
t+1}|\Delta_{n}|\sum_{u\geq 1}\sum_{v\geq
u}up(u)\,p(v)\,n\big{[}n-t\vee(n-v)\big{]}.$

If $n-v\geq t$, then $n-t\vee(n-v)=v$ and if $n-v<t$, then
$n-t\vee(n-v)=n-t<v$. It follows that

$M_{2}\leq\sum_{n\geq t+1}|\Delta_{n}|\sum_{u\geq 1}\sum_{v\geq
u}up(u)\,p(v)\,nv\leq\mu^{2}\sum_{n\geq t}n\,|\Delta_{n}|.$ (K.8)

Bound (K.2) follows by combining (K.3) with (K.4), (K.5), (K.6), (K.7), and
(K.8).

##  Appendix L Proof of Lemma 4.2

Assume that $p$ is aperiodic. To begin with, we demonstrate that there exists
a real sequence $\\{\gamma_{t}\\}_{t\geq 0}$ such that $\sum_{t\geq
0}|\gamma_{t}|<\infty$ and

$\frac{1}{\sum_{t\geq 0}Q(t)z^{t}}=\sum_{t\geq 0}\gamma_{t}z^{t}$ (L.1)

for all complex numbers $z$ in the open unit disk, $Q$ being the tail of the
waiting time distribution $p$. Consider the function $f$ defined by
$f(z):=\sum_{t\geq 0}Q(t)z^{t}$ for $|z|\leq 1$. We have $1-\sum_{s\geq
1}p(s)z^{s}=(1-z)f(z)$ for all $|z|\leq 1$. We claim that $f$ has no zeros for
$|z|\leq 1$. In fact, $|z|<1$ entails $|\sum_{s\geq 1}p(s)z^{s}|<1$, so that
any zeros of $f$ must occur on the circle $|z|=1$. The point $z=1$ cannot be a
zero since $f(1)=\mu\neq 0$. If $f(e^{{\rm i}\theta})=0$ for some
$\theta\in(0,2\pi)$, then $\sum_{s\geq 1}p(s)e^{{\rm i}s\theta}=1$, which
gives $\cos(s\theta)=1$ for all $s\geq 1$ such that $p(s)>0$. But this is
impossible because $p$ is aperiodic. Then, the function that maps $z$ in
$1/f(z)$ has no singularities in the open unit disk and is continuous in the
closed unit disk. As a consequence, for $|z|<1$ it can be expanded in a power
series as $1/f(z)=\sum_{t\geq 0}\gamma_{t}z^{t}$ with $\gamma_{t}$ defined for
every $t\geq 0$ by

$\gamma_{t}:=\frac{1}{2\pi{\rm
i}}\int_{|z|=r}\frac{z^{-t-1}}{f(z)}dz=\frac{1}{2\pi
r^{t}}\int_{0}^{2\pi}\frac{e^{-{\rm i}t\theta}}{f(re^{{\rm
i}\theta})}d\theta.$

Here $r$ is any number in $(0,1)$. As $1/f$ is bounded on the closed unit disk
by continuity, we can invoke the dominated convergence theorem to set $r=1$ in
the last integral:

$\gamma_{t}=\frac{1}{2\pi}\int_{0}^{2\pi}\frac{e^{-{\rm i}t\theta}}{f(e^{{\rm
i}\theta})}d\theta.$ (L.2)

At the same time, since $f(e^{{\rm i}\theta})=\sum_{t\geq 0}Q(t)e^{{\rm
i}t\theta}$ converges absolutely and has no zeros for real values of $\theta$,
Theorem 18.21 of [42] states that $1/f(e^{{\rm
i}\theta})=\sum_{t=-\infty}^{\infty}\xi_{t}e^{{\rm i}t\theta}$ for all
$\theta\in[0,2\pi]$ with coefficients that fulfills
$\sum_{t=-\infty}^{\infty}|\xi_{t}|<\infty$. By plugging this expansion in
(L.2) we get $\gamma_{t}=\xi_{t}$ for every $t\geq 0$, and hence $\sum_{t\geq
0}|\gamma_{t}|<\infty$.

We now observe that by taking a Cauchy product, formula (L.1) shows that the
sequence $\\{\gamma_{t}\\}_{t\geq 0}$ solves the problem $\gamma_{0}=1$ and
$\gamma_{t}=-\sum_{s=1}^{t}Q(s)\gamma_{t-s}$ for all $t\geq 1$. Simple
manipulations of the renewal equation demonstrate that the same problem is
solved by the sequence $\\{\gamma_{t}^{\prime}\\}_{t\geq 0}$ with entries
$\gamma_{0}^{\prime}=1$ and $\gamma_{t}^{\prime}=\mu(\rho_{t}-\rho_{t-1})$ for
$t\geq 1$. Since this problem has a unique solution, we get
$\gamma_{t}=\mu(\rho_{t}-\rho_{t-1})$ for $t\geq 1$ and

$\frac{1}{\sum_{t\geq 0}Q(t)z^{t}}=1+\mu\sum_{t\geq
1}(\rho_{t}-\rho_{t-1})z^{t}$

for every $|z|<1$. Derivative with respect to $z$ gives

$\frac{\sum_{t\geq 1}tQ(t)z^{t}}{[\sum_{t\geq 0}Q(t)z^{t}]^{2}}=\mu\sum_{t\geq
1}t(\rho_{t-1}-\rho_{t})z^{t}.$ (L.3)

This formula is what we need to prove the equivalence between points $(i)$ and
$(ii)$ of the lemma. In fact, if $p$ is aperiodic and $\sum_{s\geq
1}s^{2}p(s)<\infty$, then $1/\sum_{t\geq 0}Q(t)z^{t}=\sum_{t\geq
0}\gamma_{t}z^{t}$ with $\sum_{t\geq 0}|\gamma_{t}|<\infty$ and $\sum_{t\geq
1}tQ(t)=\sum_{s\geq 1}(1/2)(s-1)sp(s)<\infty$. This way, since the Cauchy
product of absolutely convergent series is absolutely convergent, by expanding
the l.h.s. of (L.3) in a power series and by making a comparison with the
r.h.s. we realize that $\sum_{t\geq 1}t|\rho_{t}-\rho_{t-1}|<\infty$. If
instead $\sum_{t\geq 1}t|\rho_{t}-\rho_{t-1}|<\infty$, then $p$ is aperiodic
as we have seen in the proof of Proposition 4.1, so that (L.3) holds. It
follows that $\sum_{t=1}^{n}tQ(t)\leq\mu^{3}\sum_{t\geq
1}t|\rho_{t}-\rho_{t-1}|<\infty$ for all positive $n$, which suffices to prove
that $\sum_{s\geq 1}s^{2}p(s)<\infty$.

Suppose now that $p$ is aperiodic and that $\sum_{s\geq 1}s^{2}p(s)<\infty$.
Let us demonstrate that $\sum_{t\geq 1}\alpha_{t}<\infty$. Proposition 4.1
tells us that $\sum_{t\geq 1}\alpha_{t}\leq 3\mu^{2}\sum_{t\geq
1}t|\rho_{t}-\rho_{t-1}|+4\mu^{2}\sum_{t\geq
1}t^{2}|\rho_{t+1}-2\rho_{t}+\rho_{t-1}|$. We already know that $\sum_{t\geq
1}t|\rho_{t}-\rho_{t-1}|<\infty$ and it remains to verify that $\sum_{t\geq
1}t^{2}|\rho_{t+1}-2\rho_{t}+\rho_{t-1}|<\infty$. By taking the derivative of
(L.3) with respect to $z$ we get

$\frac{\sum_{t\geq 1}t^{2}Q(t)z^{t}}{[\sum_{t\geq
0}Q(t)z^{t}]^{2}}-2\frac{[\sum_{t\geq 1}tQ(t)z^{t}]^{2}}{[\sum_{t\geq
0}Q(t)z^{t}]^{3}}=\mu\sum_{t\geq 1}t^{2}(\rho_{t-1}-\rho_{t})z^{t}.$ (L.4)

A shift of the index of the last series yields

$\frac{\sum_{t\geq 1}t^{2}Q(t)z^{t-1}}{[\sum_{t\geq
0}Q(t)z^{t}]^{2}}-2z\frac{[\sum_{t\geq 1}tQ(t)z^{t-1}]^{2}}{[\sum_{t\geq
0}Q(t)z^{t}]^{3}}=\mu\sum_{t\geq 0}(t+1)^{2}(\rho_{t}-\rho_{t+1})z^{t}.$ (L.5)

By subtracting (L.5) from (L.4) we reach the result

$\displaystyle\frac{\sum_{t\geq 1}t^{2}p(t+1)z^{t}+\sum_{t\geq
1}(1-2t)Q(t)z^{t-1}}{[\sum_{t\geq 0}Q(t)z^{t}]^{2}}+2z(1-z)\frac{[\sum_{t\geq
1}tQ(t)z^{t-1}]^{2}}{[\sum_{t\geq 0}Q(t)z^{t}]^{3}}$
$\displaystyle=\mu\sum_{t\geq
1}t^{2}(\rho_{t-1}-2\rho_{t}+\rho_{t+1})z^{t}+\mu\sum_{t\geq
1}(1-2t)(\rho_{t-1}-\rho_{t})z^{t-1}.$ (L.6)

As before, using $1/\sum_{t\geq 0}Q(t)z^{t}=\sum_{t\geq 0}\gamma_{t}z^{t}$ and
bearing in mind that the Cauchy product of absolutely convergent series is
absolutely convergent, by expanding the l.h.s. of (L.6) in a power series and
by making a comparison with the r.h.s. we find $\sum_{t\geq
1}t^{2}|\rho_{t-1}-2\rho_{t}+\rho_{t+1}|<\infty$.

At last, let us verify the formula $\sum_{s\geq
1}s^{2}p(s)=\mu+2\mu^{3}\sum_{t\geq 0}\rho_{t}$. If $p$ is aperiodic and
$\sum_{s\geq 1}s^{2}p(s)<\infty$, or equivalently if $\sum_{t\geq
1}t|\rho_{t}-\rho_{t-1}|<\infty$, then we can apply Abel’s theorem to (L.3) to
obtain $\sum_{s\geq 1}s^{2}p(s)=\mu+2\mu^{3}\sum_{t\geq
1}t(\rho_{t-1}-\rho_{t})$. We have $\sum_{t\geq 0}|\rho_{t}|<\infty$ since
$\rho_{t}=\sum_{n>t}(\rho_{n-1}-\rho_{n})$ as
$\lim_{n\uparrow\infty}\rho_{n}=0$ and $\sum_{t\geq
1}t|\rho_{t}-\rho_{t-1}|<\infty$. Thus, the identity
$\sum_{t=1}^{n}t(\rho_{t-1}-\rho_{t})=\sum_{t=0}^{n-1}\rho_{t}-n\rho_{n}$ for
$n\geq 1$ tells us that $\lim_{n\uparrow\infty}n|\rho_{n}|$ exists, and the
fact that $\sum_{t\geq 0}|\rho_{t}|<\infty$ implies
$\lim_{n\uparrow\infty}n|\rho_{n}|=0$. At this point, the same identity
$\sum_{t=1}^{n}t(\rho_{t-1}-\rho_{t})=\sum_{t=0}^{n-1}\rho_{t}-n\rho_{n}$ for
$n\geq 1$ leads to $\sum_{t\geq 1}t(\rho_{t-1}-\rho_{t})=\sum_{t\geq
0}\rho_{t}$, which proves that $\sum_{s\geq
1}s^{2}p(s)=\mu+2\mu^{3}\sum_{t\geq 0}\rho_{t}$.

## References

  * [1] H.C. Nguyen, R. Zecchina, and J. Berg, Inverse statistical problems: from the inverse Ising problem to data science, Adv. Phys. 66 197-261 (2017)
  * [2] H. De Jong, Modeling and simulation of genetic regulatory systems: a literature review, J. Comput. Biol. 9 67-103 (2002)
  * [3] R.E. Kass, S.I. Amari, K. Arai, E.N. Brown, C.O. Diekman, M. Diesmann, B. Doiron, U.T. Eden, A.L. Fairhall, G.M. Fiddyment, T. Fukai, S. Grün, M.T. Harrison, M. Helias, H. Nakahara, J. Teramae, P.J. Thomas, M. Reimers, J. Rodu, H.G. Rotstein, E. Shea-Brown, H. Shimazaki, S. Shinomoto, B.M. Yu, and M.A. Kramer, Computational neuroscience: Mathematical and statistical perspectives, Annu. Rev. Stat. Appl. 5 183-214 (2018)
  * [4] E.W. Frees, Regression modeling with actuarial and financial applications (Cambridge University Press, New York, 2010)
  * [5] H. Qin, R. Gong, X. Liu, X. Bai, J. Song, N. Sebe, Binary neural networks: A survey, Pattern Recognit. 105 107281 (2020)
  * [6] M.J. Wainwright and M.I. Jordan, Graphical models, exponential families, and variational inference, Found. Trends Mach. Learn. 1 1-305 (2008)
  * [7] F.K. Fokianos and B. Kedem, Regression models for time series analysis (Wiley & Sons, New Jersey, 2002)
  * [8] O.V. Usatenko and V.A. Yampol’skii, Binary N-step Markov chains and long-range correlated systems, Phys. Rev. Lett. 90 110601 (2003)
  * [9] O.V. Usatenko, V.A. Yampol’skii, K.E. Kechedzhy, and S.S. Melnyk, Symbolic stochastic dynamical systems viewed as binary N-step Markov chains, Phys. Rev. E 68 061107 (2003)
  * [10] S. Hod and U. Keshet, Phase transition in random walks with long-range correlations, Phys. Rev. E 70 015104(R) (2004)
  * [11] S.S. Melnyk, O.V. Usatenko, and V.A. Yampol’skii, and V.A. Golick, Competition between two kinds of correlations in literary texts, Phys. Rev. E 72 026140 (2005)
  * [12] S.S. Melnyk, O.V. Usatenko, V.A. Yampol’skii, Memory functions of the additive Markov chains: applications to complex dynamic systems, Physica A 361 405-415 (2006)
  * [13] S.S. Melnyk, O.V. Usatenko, V.A. Yampol’skii, S.S. Apostolov, and Z.A. Maiselis, Memory functions and correlations in additive binary Markov chains, J. Phys. A: Math. Gen. 39 14289-14301 (2006)
  * [14] F.M. Izrailev, A.A. Krokhin, N.M. Makarov, S.S. Melnyk, O.V. Usatenko, and V.A. Yampol’skii, Memory function versus binary correlator in additive Markov chains, Physica A 372 279-297 (2006)
  * [15] Z.A. Lomnicki and S.K. Zaremba, Applications of zero-one processes, J. R. Stat. Soc. Series B Stat. Methodol. 17 243-255 (1955)
  * [16] D.M. Keenan, A time series analysis of binary data, J. Am. Stat. Assoc. 77 816-821 (1982)
  * [17] F.M. Izrailev, A.A. Krokhin, N.M. Makarov, and O. V. Usatenko, Generation of correlated binary sequences from white noise, Phys. Rev. E 76 027701 (2007)
  * [18] S.S. Apostolov, F.M. Izrailev, N.M. Makarov, Z.A. Mayzelis, S.S. Melnyk, and O.V. Usatenko, The signum function method for the generation of correlated dichotomic chains, J. Phys. A: Math. Theor. 41 175101 (2008)
  * [19] O.V. Usatenko, S.S. Melnik, S.S. Apostolov, N.M. Makarov, and A.A. Krokhin, Iterative method for generating correlated binary sequences, Phys. Rev. E 90 053305 (2014)
  * [20] C.L. Sung, Y. Hung, W. Rittase, C. Zhu, and J. Wu, A generalized Gaussian process model for computer experiments with binary time series, J. Am. Statist. Assoc. 115 1-24 (2019)
  * [21] R.C. Bradley, Basic properties of strong mixing conditions. A survey and some open questions, Probab. Surv. 2 107-144 (2005)
  * [22] L.J. Emrich and M.R. Piedmonte, A Method for generating high-dimensional multivariate binary variates, Am. Stat. 45 302-304 (1991)
  * [23] F. Serinaldi and F. Lombardo, General simulation algorithm for autocorrelated binary processes, Phys. Rev. E 95 023312 (2017)
  * [24] F. Serinaldi and F. Lombardo, BetaBit: A fast generator of autocorrelated binary processes for geophysical research, Europhys. Lett. 118 30007 (2017)
  * [25] W. Jiang, S. Song, L. Hou, and H. Zhao, A set of efficient methods to generate high-dimensional binary data with specified correlation structures, Am. Stat. 1-13 (2020)
  * [26] S. Asmussen, Applied probability and queues 2nd edn (Springer, New York, 2003)
  * [27] J.F.C. Kingman, Regenerative phenomena (Wiley, London, 1972)
  * [28] E. Jaynes, Information theory and statistical mechanics, Phys. Rev. 106 620-630 (1957)
  * [29] E. Jaynes, Information theory and statistical mechanics. II, Phys. Rev. 108 171-190 (1957)
  * [30] A. Galves and E. Löcherbach, Stochastic chains with memory of variable length, TICSP Series 38 117-133 (2008)
  * [31] P. Erdös, W. Feller, and H. Pollard, A property of power series with positive coefficients, Bull. Amer. Math. Soc. 55 201-204 (1949)
  * [32] J. Chover, P. Ney, and S. Wainger, Functions of probability measures, J. Anal. Math. 26 255-302 (1972)
  * [33] P. Embrechts and E. Omey, Functions of power series, Yokohama Math. J. 32 77-88 (1984)
  * [34] N.H. Bingham, C.M. Goldie, and J.L. Teugels, Regular variation (Cambridge University Press, Cambridge, 1989)
  * [35] P. Walters, An introduction to ergodic theory (Springer-Verlag, New York, 1982)
  * [36] A.N. Shiryaev, Probability 2nd edn (Springer, New York, 1996)
  * [37] T.M. Cover and J.A. Thomas, Elements of information theory 2nd ed. (Wiley-Interscience, New Jersey, 2006)
  * [38] M. Zamparo, Large deviations in renewal models of statistical mechanics, J. Phys. A: Math. Theor. 52 495004 (2019)
  * [39] M. Zamparo, Large deviations in discrete-time renewal theory, Stoch. Process. Their Appl. 139 80-109 (2021)
  * [40] I.A. Ibragimov and Y.V. Linnik, Independent and stationary sequences of random variables (Wolters-Noordhoff, Groningen, 1971)
  * [41] H. Berbee, Convergence rates in the strong law for bounded mixing sequences, Probab. Theory Relat. Fields 74 255-270 (1987)
  * [42] W. Rudin, Real and Complex Analysis 3rd edn (McGraw-Hill, New York, 1987)