The logistic map is the most basic recurrence formula exhibiting various levels of chaos depending on its parameter. It has been used in population demographics to model chaotic behavior. Here we explore this model in the context of randomness simulation and revisit a bizarre non-periodic random number generator discovered 70 years ago, based on the logistic map equation. We then discuss flaws and strengths in widely used random number generators, as well as how to reverse-engineer such algorithms. Finally, we discuss quantum algorithms, as they are appropriate in our context.
Source for animated picture: click here
The logistic map is defined by the following recursion
X(k) = r X(k-1) (1 – X(k-1))
with one positive parameter r less or equal to 4. The starting value X(0) is called the seed, and must be in [0, 1]. The higher r, the more chaotic the behavior. At r = 3.56995… is the onset of chaos. At this point, from almost all seeds, we no longer see oscillations of finite period. In other words, slight variations in the initial population yield dramatically different results over time, a prime characteristic of chaos.
When r=4, an exact solution is known, see here. In that case, the explicit formula is
The case r=4 was used …