I present here some innovative results in my most recent research on stochastic processes. chaos modeling, and dynamical systems, with applications to Fintech, cryptography, number theory, and random number generators. While covering advanced topics, this article is accessible to professionals with limited knowledge in statistical or mathematical theory. It introduces new material not covered in my recent book (available\u00a0here<\/a>) on applied stochastic processes. You don’t need to read my book to understand this article, but the book is a nice complement and introduction to the concepts discussed here.<\/p>\n None of the material presented here is covered in standard textbooks on stochastic processes or dynamical systems. In particular, it has nothing to do with the classical logistic map or Brownian motions, though the systems investigated here exhibit very similar behaviors and are related to the classical models. This cross-disciplinary article is targeted to professionals with interests in statistics, probability, mathematics, machine learning, simulations, signal processing, operations research, computer science, pattern recognition, and physics. Because of its tutorial style, it should also appeal to beginners learning about Markov processes, time series, and data science techniques in general, offering fresh, off-the-beaten-path content not found anywhere else, contrasting with the material covered again and again in countless, identical books, websites, and classes catering to students and researchers alike.\u00a0<\/p>\n Some problems discussed here could be used by college professors in the classroom, or as original exam questions, while others are extremely challenging questions that could be the subject of a PhD thesis or even well beyond that level. This article constitutes (along with my book) a stepping stone in my endeavor to solve one of the biggest mysteries in the universe: are the digits of mathematical constants such as Pi, evenly distributed? To this day, no one knows if these digits even have a distribution to start with, let alone whether that distribution is uniform or not. Part of the discussion is about statistical properties of numeration systems in a non-integer base (such as the golden ratio base) and its applications. All systems investigated here, whether deterministic or not, are treated as stochastic processes, including the digits in question. They all exhibit strong chaos, albeit easily manageable due to their ergodicity<\/a>.\u00a0 .<\/p>\n Interesting connections with the golden ratio, special polynomials, and other special mathematical constants, are discussed in section 2. Finally, all the analyses performed during this work were done in Excel. I share my spreadsheets in this article, as well as many illustration, and all the results are replicable.<\/p>\n 1. General framework, notations and terminology<\/strong><\/span><\/p>\n We are dealing here with sequences { x<\/em>(n<\/em>) }, starting with n<\/em> = 1, recursively defined by an iterative formula\u00a0x<\/em>(n\u00a0<\/em>+ 1) = g<\/em>(x<\/em>(n<\/em>)). We will explore various functions g<\/em> in the next sections. Typically, x<\/em>(n<\/em>) is a real number in [0, 1], and g<\/em> is a mapping such that g<\/em>(x<\/em>(n + 1<\/em>)) is also in\u00a0[0, 1]. The first, value, x<\/em>(1), is called the seed<\/em>. In short, x<\/em>(n<\/em>) is a time series or stochastic process, and the index n<\/em> denotes the (discrete) time or iteration.\u00a0<\/p>\n Typically, the values x<\/em>(n<\/em>) appear to be distributed somewhat randomly, according to some statistical distribution called the equilibrium distribution<\/em>, and generally, the x<\/em>(n<\/em>)’s are auto-correlated.\u00a0 So x<\/em>(n<\/em>) can be seen as a realization or observation of a random variable X<\/em>, whose distribution is the equilibrium distribution. That is, the empirical distribution of the x<\/em>(n<\/em>)’s, when computed on a large number of terms, tends to the theoretical equilibrium distribution in question.\u00a0 Also, in practice, the vast majority of seeds yield the same exact equilibrium distribution. Such seeds are known as good seeds<\/em>, the other ones are called bad seeds<\/em>.\u00a0<\/p>\n 1.1. Finding the equilibrium distribution<\/strong><\/p>\n The equilibrium distribution can be obtained by solving the equation P(X<\/em> < y<\/em>) = P(g<\/em>(X<\/em>) < y) with y<\/em> in [0, 1]. This is actually a stochastic integral equation: the probability distribution P is the solution, and corresponds to the distribution of X<\/em>. This distribution is sometimes denoted as F<\/em>. Whether the equilibrium distribution exists or not, and whether it is unique or not (for good seeds), is not discussed here. However, we will provide several examples with unique equilibrium distribution, throughout this article, including how to solve the stochastic integral equation. The density attached to the equilibrium distribution is called the equilibrium density<\/em>\u00a0and is denoted as f<\/em>.<\/p>\n 1.2. Auto-correlation and spectral analysis<\/strong><\/p>\n The theoretical auto-correlation between successive values of x<\/em>(n<\/em>) can be computed as follows:<\/p>\n Once computed, it is interesting to compare its value with the observed auto-correlation measured on the first few thousand terms of the sequence { x<\/em>(n<\/em>) }. Longer-term\u00a0auto-correlations (lag-2, lag-3 and so on) can be computed using the same principle, either theoretically or empirically (on data). The entire auto-correlation structure, given the equilibrium distribution, uniquely characterizes the stochastic process. The study of these auto-correlations is called spectral analysis<\/em>.<\/p>\n 1.3. Ergodicity, convergence, and attractors<\/strong><\/p>\n So far we have looked at one instance or realization { x(n) } of the underlying process, characterized by a mapping g<\/em> and a seed x<\/em>(1). This provides enough information to determine the auto-correlation structure and equilibrium distribution, which do not depend on the good seed.\u00a0<\/p>\n There is another way to look at things. You can simulate m<\/em> deviates of a random variable Z<\/em>(1) with any pre-specified distribution, say uniform on [0, 1]. Then apply the mapping g<\/em> to each of these deviates, to obtain another set of m<\/em>\u00a0values. These new values are m<\/em> deviates of a random variable denoted as\u00a0Z<\/em>(2), also with known\u00a0statistical distribution. Repeat this step over and over, to obtain Z<\/em>(3), Z<\/em>(4), and so on. For large n<\/em>, Z<\/em>(n<\/em>) converges in distribution to the equilibrium distribution, regardless of the initial distribution chosen for Z<\/em>(1<\/i>). We illustrate how it works on an example, later in this article. Because convergence to the same equilibrium distribution occurs regardless of the initial distribution, the equilibrium distribution, in the language of dynamical systems, is called an attractor distribution<\/em>. The method described here can be used to identify these attractors.\u00a0<\/p>\n A stochastic process where the equilibrium distribution does not depend on Z<\/em>(1) nor on the good seed, is called ergodic<\/em>. All the processes studied here are ergodic. An example of non-ergodic process can be found here<\/a>.\u00a0<\/p>\n 1.4. Space state, time state, and Markov chain approximations<\/strong><\/p>\n The space state<\/em> is the space where {\u00a0x<\/em>(n<\/em>) } takes its values; here it is [0, 1] and is thus continuous. The time space<\/em> is attached to the index n<\/em>, and it is discrete here. However, in some of our examples,\u00a0x<\/em>(n<\/em>) can be written explicitly as a function of n<\/em>, thus it can easily be extended to real values of n<\/em>, making it a time-continuous process.\u00a0<\/p>\n We can also divide the continuous space state [0, 1] into a finite number of disjoint intervals S<\/em>(1), S<\/em>(2), … , S<\/em>(k<\/em>). Rather than studying the full equilibrium distribution, we could compute the probabilities<\/p>\n Then we are dealing with a state-discrete Markov chain with k<\/em> states, and p<\/em>(i<\/em>,\u00a0j<\/em>) represents the transition probability for moving from state i<\/em> to state j<\/em>, estimated on n<\/em> observations x<\/em>(1), …, x<\/em>(n<\/em>). One can compute the steady state probability vector<\/a>, by solving a linear system of k<\/em> equations; it represents the stable state of the system. As k<\/em>\u00a0and n<\/em> tend to infinity and the intervals S<\/em>(1), …, S<\/em>(k<\/em>) become infinitesimal, the steady state probability vector converges to the equilibrium density. This is another way to approximate the equilibrium distribution.\u00a0\u00a0<\/p>\n 1.5. Examples<\/strong><\/p>\n The most well known examples of { x<\/em>(n<\/em>) } are random walks (n<\/em> discrete) and Brownian motions (n<\/em> continuous). However, since the space state considered in this article is [0, 1], a better suited example would be a random walk constrained to stay within [0, 1]. Such processes are discussed in my book<\/a>, in chapter 3.<\/p>\n Let us now introduce the example that we will discuss in detail throughout the remaining of this article. It is defined with the following mapping:\u00a0<\/p>\n Here the curly brackets represent the fractional part function, also denoted as FRAC. The straight brackets on the right-hand side, represent the integer part or floor function, also denoted as INT. Since the seed is between 0 and 1, we also have this interesting property: INT(b<\/em> x<\/em>(n<\/em>)) is the n<\/em>-th digit of the seed x<\/em>(1), in base b<\/em>. Thus the parameter b<\/em> is called the base<\/em>, and it can be any real number greater than 1. In the next section, we consider the case where b<\/em> is in ]1, 2]. Non-integer bases are also discussed here<\/a> and here<\/a>, and also extensively in my book. While this process looks very peculiar, there is a mapping between the base-2 system, and the very popular logistic map system<\/a>: see chapter 10 in my book for details, or here<\/a> for a summary.\u00a0\u00a0<\/p>\n It makes sense to call this process the base-b process<\/em>. If b<\/em> is an integer, its equilibrium distribution is uniform on [0, 1] assuming you use a good seed. Also, if b<\/em> is an integer, the auto-correlation between successive values of x<\/em>(n<\/em>) is 1 \/ b<\/em>. This fact was probably mentioned for the first time, in my book. It was never proved, but assumed based on simulations and a lot of data crunching. The proof is actually quite simple and worth reading; it shows how to compute such auto-correlations, and constitutes an interesting classroom problem or exam question. You will find it in the appendix in this article.\u00a0\u00a0<\/p>\n Pretty much all numbers in [0, 1] are good seeds for the b<\/em>-process. However, there are infinitely many exceptions: in particular, none of the rational numbers is a good seed. Identifying the class of good seeds is an incredibly complicated problem, still unsolved today. If we knew which numbers are good seeds, we would know whether or not the digits of Pi or any popular mathematical constant, are evenly distributed. Another question is whether or not a good seed is just a normal number<\/a>, and conversely. The two concepts are closely related, and possibly identical. Later in this article, we will discuss a stochastic process where all seeds are good seeds.\u00a0<\/p>\n Finally, the most interesting values of\u00a0b<\/em> are those that are less than two. In some ways, the associated stochastic processes are also much easier to study. But most interestingly, the similarities between these b<\/em>-processes and stochastic dynamical systems, are easier to grasp, for instance regarding branching behavior, and attractors. This is the subject of the next section. The second fundamental theorem in the next section is one of the fascinating results published here for the first time, and still a work in progress.\u00a0<\/p>\n Note that if b<\/em> is an integer, it is easy to turn the time-discrete b<\/em>-process into a time-continuous one. We have<\/p>\n Thus the formula can be extended to values of n<\/em> that are not integers.\u00a0<\/p>\n 2. Case study<\/strong><\/span><\/p>\n In this section, we consider the b<\/em>-process introduced as an example at the bottom of the first section, with b<\/em> in ]1, 2]. We now jump right away to the two fundamental theorems, and cool applications will follow afterwards. The function g<\/em> is the fractional part function, as introduced in the first section.\u00a0\u00a0<\/p>\n 2.1. First fundamental theorem<\/strong><\/p>\n Let Z<\/i>\u00a0be a random variable with an arbitrary distribution F<\/em>, admitting a density function f<\/em>\u00a0on [0, 1]. Let Y<\/em> = g<\/em>(Z<\/i>) be the fractional part of bZ<\/em>, and b<\/em> in ]1, 2]. Then we have:<\/p>\n The algorithm, already discussed in the first section (see the ergodicity, convergence and attractors subsection), consists in iteratively computing the distribution of g<\/em>(Z<\/em>), g<\/em>(g<\/em>(Z<\/em>)), g<\/em>(g<\/em>(g<\/em>(Z<\/em>))), and so on, until the difference between two successive iterates is small enough. Here, the difference is measured as the distance between two distributions, using one of the many distance metrics discussed in the literature (see here<\/a>.)<\/p>\n The next theorem tells you in more details what happens if you choose a uniform distribution on [0, 1], for Z.<\/em>\u00a0This was our favorite choice in most of our simulations.\u00a0 \u00a0<\/p>\n 2.2. Second fundamental theorem<\/strong><\/p>\n We use the same assumptions as in the first theorem, but here Z<\/em>\u00a0has a uniform distribution on [0, 1]. The following theorem can be used to find the equilibrium density, as illustrated in the appendix on\u00a0the supergolden ratio<\/a> constant.\u00a0<\/p>\n Let Z<\/em>(1) = Z<\/em>, and\u00a0Z<\/em>(n<\/em>+1) = g<\/em>(Z<\/em>(n<\/em>)). Then Z<\/em>(n+<\/em>1) has a piece-wise uniform distribution, more precisely, a mixture<\/a> of\u00a0n<\/em>+1 uniform distributions on n<\/em>+1 intervals. These intervals are denoted as\u00a0<\/p>\n [0, c<\/em>(1)[,\u00a0 \u00a0 \u00a0[c<\/em>(1), c<\/em>(2)[,\u00a0 \u00a0 \u00a0[c<\/em>(2), c<\/em>(3)[, … , [c<\/em>(n<\/em>), 1],<\/p>\n and the constant value of the density of Z(n<\/em>+1) on the\u00a0k<\/em>-th interval (k<\/em> = 1, … ,\u00a0n<\/em>\u00a0+1) is denoted as d<\/em>(k<\/em>). The distribution of Z<\/em>(n<\/em>+1) has the following features:\u00a0<\/p>\n<\/a><\/p>\n
<\/a><\/p>\n
<\/a><\/p>\n
<\/a><\/p>\n
<\/a><\/p>\n
<\/a>This result is easy to obtain and constitutes an interesting classroom problem, or exam question. The proof is in the appendix. This theorem allows you to design a simple iterative algorithm to approximate the equilibrium distribution, and to asses how fast it converges to the solution. The result is valid even if the density function of Z<\/em> has an infinite but countable number of discontinuities. This will be the case in the examples discussed here, in which a uniform distribution on [0, 1] is chosen for Z<\/em>.\u00a0<\/p>\n
\n