# Complex Systems, Emergence, and Multiscale Analysis: A Tutorial and Brief Survey
## 2 Basics of Complex Systems and Emergence
### Going from Distinguishing Chaos from Noise to Fully Understanding the System Dynamics
The Kolmogorov-Chaitin complexity is also called descriptive complexity, Kolmogorov complexity, algorithmic complexity, algorithmic entropy, and program-size complexity. It is a key measure in algorithmic information theory. The Kolmogorov-Chaitin complexity of a string of numbers or a text file is the length of the shortest computer program that generates the the string of numbers or the text file. Therefore, it measures the computational resources needed for specifying an object. To make the above discussions concrete, one can think of a completely random string. It is impossible to compress the string into a program with length shorter than the length of the string itself; the simplest program is to just read out the string. Although the lower bound for the Kolmogorov-Chaitin complexity of an object is difficult to obtain [20], the upper bound is easy to get, which are just the Shannon entropy or the LZ complexity. For dynamical systems and Markov information sources, this upper bound can almost surely be achieved [170]. Next, we explain a widely used entropy measure, the approximate entropy. The approximate entropy amounts to taking \(q=1\) in Equation (55) at a fixed scale \(\epsilon\) and two small embedding dimensions (say \(m_{0}\) and \(m_{0}+1\)) instead of taking the limits of \(\lim_{\epsilon\to 0}\) and \(\lim_{m\to 0}\). While it is closely related to the sample entropy, it is not as effective as the sample entropy in resolving the scaling behavior. This is part of the reason that multiscale entropy is built op top of the sample entropy. For more details, we refer to [171]. Finally, we explain the permutation entropy (PE) [172]. Due to its simplicity, it has found numerous applications in time series analysis. Here, we describe PE following the notations of [173]. We start from an \(m\)-dimensional embedding vector, \(X_{i}=[x(i),x(i+L),\cdots,\)\(x(i+(m-1)L)]\). Let us sort the elements of the vector in ascending order, \([x(i+(j_{1}-1)L)\leq x(i+(j_{2}-1)L)\leq\cdots\leq x(i+(j_{m}-1)L]\). When an equality occurs, e.g., \(x(i+(j_{1}-1)L)=x(i+(j_{2}-1)L)\), we choose their natural order, i.e., if \(j_{1}<j_{2}\), then \(x(i+(j_{1}-1)L)\leq x(i+(j_{2}-1)L)\). This way, the vector \(X_{i}\) is mapped onto a sequence of numbers, \((j_{1},j_{2},\cdots,j_{m})\). Permutating it, we see that there are a total of \(m!\) distinct combinations of \((j_{1},j_{2},\cdots,j_{m})\). Each permutation can be considered as an \(m\)-dimensional symbol. Therefore, the reconstructed trajectory in the \(m\)-dimensional space is mapped to a \(m\)-dimensional symbol sequence. Let \(P_{1},P_{2},\cdots,P_{K}\) be the probability for the \(K\leq m!\) distinct symbols. The PE, denoted by \(E_{p}\), for the time series \(\{x(i),i=1,2,\cdots\}\) is defined as  
\[E_{p}(m)=-\sum_{j=1}^{K}P_{j}\ln P_{j}. \tag{94}\]  
The maximum of \(E_{p}(m)\) is \(\ln(m! )\) when \(P_{j}=1/(m!)\). It is convenient to normalize it to obtain  
\[0\leq E_{p}=E_{p}(m)/\ln(m!)\leq 1. \tag{95}\]  
\(E_{p}\) essentially measures the randomness of the time series under study: with the passing of time, if data measured from a system become more regular, then \(E_{p}\) of the corresponding data becomes smaller. This statement suggests that if one wishes to detect dynamical changes in a system, one can partition a time series into short windows, compute PE for each window, and examine how PE changes with the window [173]. The construction of PE may be considered a generalization of symbolic dynamics of dynamical systems for finite data, recalling that the essence of symbolic dynamics is to map a trajectory in certain space to a few subspaces, such as a trajectory defined in the unit interval \([0\ 1]\) to two sub-intervals, \([0\ 1/2)\) and \([1/2\ 1]\). The usefulness of symbolic dynamics is a strong hint that PE is often very useful for analyzing complex time series. While the connections among some of the complexity measures discussed here are obvious, a more comprehensive answer also exists.