%\documentstyle[aps,twocolumn]{revtex}
%\documentstyle[aps,preprint]{revtex}
\documentstyle[12pt]{article}

\begin{document}

\author{Thiago S. Fleury, 
Carmen P. C. Prado\\
Departamento de F\'{\i}sica Geral, Instituto de F\'{\i}sica\\
Universidade de S\~ao Paulo\\
Caixa Postal 66318, CEP 05315-970, S\~ao Paulo, SP, Brazil}
\title{Approximate Entropies}
\maketitle

\begin{abstract}

PACS number(s): 05.40.+j, 05.70.Ln, 64.60.Lx, 91.30.Bi.

\end{abstract}

%\twocolumn[\hsize\textwidth\columnwidth\hsize\csname 
%@twocolumnfalse\endcsname
%]

\section{Introduction}

The paradigm of chaos has influenced many fields of science. From the 
theoretical point of view, there is the  recognition that
imprevisibility can be
a propertie of very simple deterministic systems. For the
experimentalists, the framework of  deterministic chaos offers a new
possibility of explanation for irregular behavior and anomalies in
systems which do not seem to be inherently stochastic. Also, great efforts
are being made to exploit ideas of chaos theory, such as embeddings, 
generalized dimensions, Lyapunov exponents and entropies, in cases 
where the
system is not necessary deterministic, but the data displays more
 structure than can be captured by traditional methods. Problems of 
this kind are typical in biology and
physiology, but are also present in many other fields.

The link between the eventually nonlinear dynamics that underlies the
behavior of a given
system,  and the measured scalar time series through which 
we observe it, has become
possible since Takens proposed a way to reconstruct the whole vector 
phase space from a single scalar component. This method became known
as the method of delays.  

If ${x_i}$ is a sequence of $N$ experimental measurements taken at a
regular time interval $\Delta t$, the reconstructed  attractor in
an embedding space of dimension $m$ is given by the vectors 
$$
\vec{\xi}_i = (x_i, x_{i+p}, \ldots, x_{i + (m-1)p)}
$$

\noindent where $p$ is a time delay or time-step.

A lot of mathematical work has been done in the
attempt to clarify under which circumstances and to what extent the
geometrical trajectory reconstructed by means of the method of delays is
equivalent to the real trajectory of the  system.
It can
be proven that, under quite  general circumstances, the reconstructed
attractor is equivalent to the attractor in the unknown space in which
the original system is living, if the embedding dimension  $m$ is
sufficiently large, more precisely, larger than twice the fractal
dimension of the attractor.  However, in practice,  
depending on the case, much
smaller values of $m$ can lead to a very precise reconstruction. This
is an important point, because, in practice, reconstruct attractors in
high dimensional spaces is time consuming and requires long stationary
time series, what is not always the case of experimental data.

The determination of the time step $p$ is also a problem. It can be
proven that, if we work with infinite sets of data, the choice of $p$
is arbitrary.  But when dealing with finite data sets
(what is always the case in experiments and simulations) we do 
have to care about
the right choice of $p$. It cannot be so
short that the  components of $\vec{\xi}_{i}$ are correlated, 
neither too big to
miss the fine structure of the dynamics,  generating uncorrelated
vectors. Of course, $p$ also 
depends on the
sampling frequency of the time series, so it is never an absolute
value, even for the same dynamical system. An adequate time-step is
usually of the order of the auto-correlation time of the signal.

The reconstruction of the attractor in an adequate
embedding space, with an correct time delay, is the first step to 
the calculation of any other
quantity, such as generalized dimensions and entropies. 
As often we does not know,
{\it a priori}, what is the dimension of the phase space of the real
 system, to define a correct value for $m$,  we carry out
the calculations for
increasing values of $m$, until a typical behavior of deterministic
data appears. 
 
In this context, one of the concepts that has received a lot of
attention recently, among physiologists, is the concept of 
Approximate Entropies (ApEn),
introduced by Pincus in 1991\cite{pincus}. ApEn is a family of
statistics, that  measures the change,
in the Kolmogorov-Sinai entropy (calculated from a time series by
means of an  algorithm proposed
by Eckmann and Ruelle\cite{eckmann}) in two consecutive embedding
dimensions. 
According to Pincus\cite{Pincus2}, this new method allows
to distinguish distinct degrees of complexity of similar time
series, complexity here meaning the presence of an stocastic
component. Besides, it would be very convenient because it is almost not
affected by the noise in the data, is more robust than usual
methods and, most important, can be employed with success in very
short time series (about 100 points)  giving always finite results
even for random data. Since 1991, Approximate Entropies 
has been increasingly employed among physiologists\cite{diversos}, 
with small embedding dimensions (typically $m=2$ and $3$) 
and a fixed time step $p=1$.
 However, no one has done a detailed
study  to show how sensitive the results are to those choices, or the
validity of ApEn as a measure of complexity. Also,
there is no attempt to evaluate the error involved in such
calculations, so that any comparison can indeed make sense. In this paper we
will deal with those points, and show that they cannot be put aside.
The paper is organized as follows. In section two we briefly review
the  concept of Kolmogorov-Sinai entropy and the algorithm to calculate
it. In section three we introduce the concept of Approximate Entropies
and review briefly some results of  previous works. In section 4 we study the
consequences of the choices of $m$ and $p$ in four special {\it time
series}, generated by: (a) random numbers, (b) logistic map with 
a chaotic behavior
(c) a quasi-periodic function and (d) a non-regular sampling of a 
periodic function. In section 5 we propose a method to estimate the
error in the calculation of ApEn, and finally, in section 6, we
summarize our conclusions.

\section{Kolmogorov-Sinai entropy and Eckmann and Ruelle algorithm}
     

 	For a dissipative system, the attractor  ocuppies 
a finite region of the phase space. If we  cover this region with a 
{\it partition} of $n$ $m$-dimensional boxes of size $\ell$, 
(for instance, for $m=3$ cubes of side $\ell$), 
consider a sequence of $n$ boxes  
 ${i_1, i_2, \ldots, i_n}$, and define
$p(i_1,i_2 \ldots i_n)$ as the probability of
finding the system sucessivelly in boxes $i_1, i_2, \ldots \i_n$, in
regular time intervals  $\tau$, then the information needed to locate
the system in a particular trajectory $i^*_1, i^*_2, \ldots, i^*_n$
with precision $\ell$ is given by Shannon formula, 

$$
I_n=-\sum_{i_1,i_2, \ldots, \i_n}\;p(i_1,i_2 \ldots i_n) 
\log p(i_1,i_2 \ldots i_n).
$$

Then, $I_{n+1}(\ell)-I_n(\ell)$  is the additional information needed to
predict in which $i^*_{n+1}$ box will the system be, after a time
interval $\tau$, knowing that it was in $i^*_1, i^*_2, \ldots, i^*_n$
before. So, $I_{n+1}(\ell)-I_n(\ell)$ measures the loss of information
of the observer (or rather, the generation of information in the
system) between times $n\tau$ and $(n+1)\tau$. The Kolmogorov-Sinai
entropy, or metric entropy, is defined as the average rate of
information generation  in the system (or the average loss of
information of the observer), that is:

\begin{eqnarray}
K & = & \lim_{\tau \to 0} \lim_{\ell \to 0} \lim_{n \to \infty}
\frac{1}{n\tau} I_n(\ell) \\
  & = & \frac{1}{n\tau}
\sum _{i_1, i_2, \ldots, i_n} p(i_1,i_2 \ldots i_n)\ln (p(i_1,i_2 \ldots i_n))
\end{eqnarray}

The Kolmogorov-Sinai entropy $K$ is a characteristic of the attractor
and is very useful in distinguishing regular ($K=0$), chaotic ($K>0$,
but finite) and stochastic ($K=\infty$) processes.  $K>0$ (or
$\infty$) implies that, even if, at some moment,
 we know all the values of a given
variable that characterizes the system, it is not possible to know,
after a while, where the system will be with precision. It can be
calculated for a time series by means of an algorithm 
proposed by Eckmann and Ruelle\cite{eckmann} in 1985. 


In order to calculate the Kolmogorov-Sinai entropy from a time
series of experimental data, usually the Eckman-Ruelle algorithm
is employed\cite{eckmann}. Consider the experimental set of 
data ${x_1, x_2, \ldots , X_N}$. We
construct  $N + m -1$ m-dimensional vectors $\vec{\xi}_i$ 

\begin{equation}
\vec{\xi}_i = (x_i, x_{i+1}, \ldots, x_{i + (m-1)} \qquad 
\mbox{ (Takens procedure with time delay $p=1$)}
\end{equation}

\noindent and define the distance between  vectors
$\vec{\xi}_i, \vec{\xi}_j$ as

\begin{equation}
d[\vec{\xi}_i, \vec{\xi}_j] = \mbox{max} [|u_j - u_i|, |u_{j+1} -
 u_{i+1}|, \ldots,
|u_{j+m-1} - u_{i+m-1}|]; \qquad \mbox{(the maximum difference 
among components)}
\end{equation}

\noindent Then choose a real constant $r$ (a filter) and define the
function $C^m_i(r)$ as 

\begin{equation}
C^m_i(r) = \frac{\mbox{the number of vectors} \vec{\xi}_j \mbox{ so that
} d[\vec{\xi}_i, \vec{\xi}_j] \leq r}{\(N-m+1)} 
\end{equation}

The function  $C^m_i(r)$ is usually interpreted as the probability that
$\vec{\xi}_j$ satisfies the condition $d[\vec{\xi}_i, \vec{\xi}_j]
\leq r$. An alternative interpretation, however, is that it
represents the probability that the experimental signal $x(j+k)$ stays in an 
interval of length $2\;r$ (where  $x(j+k)$ is the average point in the
interval), for $m$ consecutive sampling intervals. It is based on this
second interpretation that this function can be used to calculate KS
entropy. If consider  $\Phi^m(r)$ as  the average of the logarithm of  
  $C^m_i(r)$,

\begin{equation}
\Phi^m(r) = \frac{\log \; \sum_{i=1}^{N-m+1}\; C^m_i(r)}{N-m+1}
\end{equation}

\noindent it is possible to interpret the difference $\Phi^{m+1}(r) -
\Phi^m(r)$ as the average (over $i$)of the logarithm of the
conditional probability that $x(j+m)$ belongs to the interval $[x(i+m)
- r, x(i+m) + r]$ once  $x(j+m)$ belongs to the interval  $[x(i+k)
- r, x(i+k) + r]$, for $k=0,1, \ldots, m-1$. With those definitions it
is possible to show that 

\begin{equation}
\label{ER}
\mbox{E-R} = \lim_{r \to 0}\; \lim_{m \to \infty} \: \lim_{N \to
\infty} [\Phi^{m+1}(r) - \Phi^m(r)] = \Delta t\; K,
\end{equation}

\noindent where $\Delta t$ is the sampling interval. In a computer,
however, it is not possible to calculate the limits present in  
equation (\ref{ER}). What is done, in practic,e is to assume that $N$
is constant and
big enough {\it a priori}, and calculate E-R for
many values of $m$ and $r$, and get the value of the limits with a
graphical approach. Typically, we calculate  $C^m_i(r)$ for different
values of $m$ and $r$, looking for the same  linear behavior when $r$
is small and $m$ large. In order to estimate K through Eckmann-Ruelle
algorithm one needs long stationary time series and almost no noise. 

\section{Approximate entropy} 

In an attempt to overcome those restrictions, and find a method able
to quantify regularity in relatively short, noisy data sets,  
S. Pincus introduced, 
in 1991, the concept of Approximate Entropy (ApEn). 















{\bf Acknowledgments:} 

\begin{thebibliography}{99}
\bibitem{Bak}  P. Bak, {\em How Nature Works\/} (Copernicus, New York, 1996).


\pagebreak

{\Large {\bf FIGURE CAPTIONS}}

\bigskip

{\bf Figure 1:} Distribution of states $p_\infty (E)$ for $k=4$, $J=0.235$
and $\epsilon =0.05$: theoretical (solid) and simulation (circles) with $N =
10^4$ sites.



\end{document}
