# Complex Systems, Emergence, and Multiscale Analysis: A Tutorial and Brief Survey
## 2 Basics of Complex Systems and Emergence
### Estimation of fractal dimension and Kolmogorov entropy  
There is an elegant algorithm, the Grassberger-Procaccia algorithm [64; 84], that takes care of both. To fully understand the algorithm, we first extend the box-counting dimension defined in Equation (23). Recall that when we defined the box-counting or capacity dimension of a chaotic attractor, we partitioned the phase space where the attractor locates into many small regions called cells or boxes of linear size \(\epsilon\), and we counted the number of non-empty cells or boxes. We can monitor the non-empty boxes more precisely by counting how many points of the attractor have fallen into each of them. We can then assign a probability \(p_{i}\) to the \(i\)th cell that is not empty. The simplest way to compute \(p_{i}\) is by using \(n_{i}/N\), where \(n_{i}\) is the number of points that fall within the \(i\)th cell, and \(N\) is the total number of points. Then  
\[D_{q}=\frac{1}{q-1}\lim_{\epsilon\to 0}\bigg{(}\frac{\log\sum_{i=1}^{n}p_{i}^{q}}{ \log\epsilon}\bigg{)}, \tag{45}\]  
where \(n\) is the total number of nonempty cells, and \(q\) is real. Generally speaking, \(D_{q}\) is a nonincreasing function of \(q\). \(D_{0}\) is the very box-counting or capacity dimension we have already discussed, since \(\sum_{i=1}^{n}p_{i}^{q}=n\). \(D_{1}\) gives the information dimension \(D_{I}\),  
\[D_{I}=\lim_{\epsilon\to 0}\frac{\sum_{i=1}^{n}p_{i}\log p_{i}}{\log \epsilon}. \tag{46}\]  
Typically, \(D_{I}\) is equivalent to the pointwise dimension \(\alpha\) defined as  
\[p(l)\sim l^{\alpha},\ \ \ l\to 0, \tag{47}\]  
where \(p(l)\) is the measure (i.e., probability) for the trajectory to fall within a neighborhood of size \(l\) centered at a reference point. \(D_{2}\) is called the correlation dimension. It is what the Grassberger-Procaccia algorithm calculates. It involves computing the correlation integral  
\[C(\epsilon)=\lim_{N\to\infty}\frac{1}{N^{2}}\sum_{i,j=1}^{N}H(\epsilon-||V_{i }-V_{j}||), \tag{48}\]  
where \(V_{i}\) and \(V_{j}\) are the embedding vectors, \(H(y)\) is the Heaviside function, which is \(1\) if \(y\geq 0\) and \(0\) if \(y<0\). \(N\) is the number of points randomly chosen from the reconstructed vectors. The term involving the Heaviside function amounts to counting the number of points falling within a cell of radius \(\epsilon\) that is centered around \(V_{i}\). Therefore, \(C(\epsilon)\) estimates the average fraction of points within a distance of \(\epsilon\). One then checks the following scaling behavior:  
\[C(\epsilon)\sim\epsilon^{D_{2}},\ \ \ \ as\ \ \ \epsilon\to 0. \tag{49}\]  
When calculating the correlation integral, one may compute pairwise distances, excluding points \(V_{i}\) and \(V_{j}\) that are too close in time (i.e., \(i\) and \(j\) are too close). A rule of thumb suggested by [PERSON] [85] is to remove the decorrelation time, which is equivalent to Inequality (43). This issue is best understood dynamically [74]: when \(V_{i}\) and \(V_{j}\) are close in time, they may be on the same orbit. The dimension corresponding to such tangential motion is \(1\), while the Lyapunov exponent is \(0\). Without removing them, the correlation dimension will be underestimated. Next we consider entropy. First, let us precisely define the KS entropy. To be general, we consider a high dimensional dynamical system with \(F\) degrees of freedom. We partition the \(F\)-dimensional phase space into boxes of size \(\epsilon^{F}\). Assume the system has an attractor in the phase space. Let us focus on a transient-free trajectory \(\vec{x}(t)\). Concretely, let us monitor the the state of the system at times \(\tau,2\tau,3\tau,\cdots\). Let \(p(i_{1},i_{2},\cdots,i_{d})\) be the joint probabilitythat the trajectory is in box \(i_{1}\) at time \(\tau\), in box \(i_{2}\) at time \(2\tau\), \(\cdots\), and in box \(i_{d}\) at time \(d\tau\).