Editing Logistic map (section)

=== Special cases of the map ===

====Upper bound when {{math|0 ≤ ''r'' ≤ 1}}====
Although exact solutions to the recurrence relation are only available in a small number of cases, a closed-form upper bound on the logistic map is known when {{math|0 ≤ ''r'' ≤ 1}}.<ref>{{cite arXiv|eprint=1710.05053|class=stat.ML|first1=Trevor|last1=Campbell|first2=Tamara|last2=Broderick|title=Automated scalable Bayesian inference via Hilbert coresets|date=2017}}</ref> There are two aspects of the behavior of the logistic map that should be captured by an upper bound in this regime: the asymptotic geometric decay with constant {{mvar|r}}, and the fast initial decay when {{math|''x''<sub>0</sub>}} is close to 1, driven by the {{math|(1 − ''x<sub>n</sub>'')}} term in the recurrence relation. The following bound captures both of these effects:

<math display="block"> \forall n \in \{0, 1, \ldots \} \quad \text{and} \quad x_0, r \in [0, 1], \quad x_n \le \frac{x_0}{r^{-n} + x_0n}. </math>

====Solution when {{math|1=''r'' = 4}}====
The special case of {{math|1=''r'' = 4}} can in fact be solved exactly, as can the case with {{math|1=''r'' = 2}};<ref name="schr" /> however, the general case can only be predicted statistically.<ref>{{cite journal | last1 = Little | first1 = M. | last2 = Heesch | first2 = D. | year = 2004 | title = Chaotic root-finding for a small class of polynomials | url = http://www.maxlittle.net/publications/GDEA41040.pdf | journal = Journal of Difference Equations and Applications | volume = 10 | issue = 11| pages = 949–953 | doi = 10.1080/10236190412331285351 | arxiv = nlin/0407042 | s2cid = 122705492 }}</ref> 
The solution when {{math|1=''r'' = 4}} is:<ref name="schr">{{cite journal |last=Schröder |first=Ernst |author-link=Ernst Schröder (mathematician) |year=1870 |title=Ueber iterirte Functionen|journal=Mathematische Annalen |volume=3 |issue= 2|pages=296–322 | doi=10.1007/BF01443992 |s2cid=116998358 }}</ref><ref name=":2">{{cite journal|last=Lorenz |first=Edward |date=1964 |title=The problem of deducing the climate from the governing equations |journal=Tellus |volume=16 |issue=February |pages=1–11|doi=10.3402/tellusa.v16i1.8893 |bibcode=1964Tell...16....1L |doi-access=free }}</ref>

<math display="block">x_{n}=\sin^{2}\left(2^{n} \theta \pi\right),</math>

where the initial condition parameter {{mvar|θ}} is given by

<math display="block">\theta = \tfrac{1}{\pi}\sin^{-1}\left(\sqrt{x_0}\right).</math>

For rational {{mvar|θ}}, after a finite number of iterations {{mvar|x<sub>n</sub>}} maps into a periodic sequence. But almost all {{mvar|θ}} are irrational, and, for irrational {{mvar|θ}}, {{mvar|x<sub>n</sub>}} never repeats itself – it is non-periodic. This solution equation clearly demonstrates the two key features of chaos – stretching and folding: the factor {{math|2<sup>''n''</sup>}} shows the exponential growth of stretching, which results in [[sensitive dependence on initial conditions]], while the squared sine function keeps {{mvar|x<sub>n</sub>}} folded within the range {{math|[0,1]}}.

For {{math|1=''r'' = 4}} an equivalent solution in terms of [[complex number]]s instead of trigonometric functions is<ref name="schr" />

<math display="block">x_n=\frac{-\alpha^{2^n} -\alpha^{-2^n} +2}{4}</math>

where {{mvar|α}} is either of the complex numbers

<math display="block">\alpha = 1 - 2x_0 \pm \sqrt{\left(1 - 2x_0\right)^2 - 1}</math>

with [[absolute value#Complex numbers|modulus]] equal to 1. Just as the squared sine function in the trigonometric solution leads to neither shrinkage nor expansion of the set of points visited, in the latter solution this effect is accomplished by the unit modulus of {{mvar|α}}.

By contrast, the solution when {{math|1=''r'' = 2}} is<ref name="schr" />

<math display="block">x_n = \tfrac{1}{2} - \tfrac{1}{2}\left(1-2x_0\right)^{2^n}</math>

for {{math|''x''<sub>0</sub> ∈ [0,1)}}. Since {{math|(1 − 2''x''<sub>0</sub>) ∈ (−1,1)}} for any value of {{math|''x''<sub>0</sub>}} other than the unstable fixed point 0, the term {{math|(1 − 2''x''<sub>0</sub>)<sup>2<sup>''n''</sup></sup>}} goes to 0 as {{mvar|n}} goes to infinity, so {{mvar|x<sub>n</sub>}} goes to the stable fixed point {{sfrac|1|2}}.

====Finding cycles of any length when {{math|''r'' {{=}} 4}}====
For the {{math|''r'' {{=}} 4}} case, from almost all initial conditions the iterate sequence is chaotic. Nevertheless, there exist an infinite number of initial conditions that lead to cycles, and indeed there exist cycles of length {{mvar|k}} for ''all'' integers {{math|''k'' > 0}}. We can exploit the relationship of the logistic map to the [[dyadic transformation]] (also known as the ''bit-shift map'') to find cycles of any length. If {{mvar|x}} follows the logistic map {{math|''x''<sub>''n'' + 1</sub> {{=}} 4''x<sub>n</sub>''(1 − ''x<sub>n</sub>'')}} and {{mvar|y}} follows the ''dyadic transformation''

<math display="block">y_{n+1}=\begin{cases}2y_n & 0 \le y_n < \tfrac12 \\2y_n -1 & \tfrac12 \le y_n < 1, \end{cases}</math>

then the two are related by a [[homeomorphism]]

<math display="block">x_{n}=\sin^{2}\left(2 \pi y_{n}\right).</math>

The reason that the dyadic transformation is also called the bit-shift map is that when {{mvar|y}} is written in binary notation, the map moves the binary point one place to the right (and if the bit to the left of the binary point has become a "1", this "1" is changed to a "0"). A cycle of length 3, for example, occurs if an iterate has a 3-bit repeating sequence in its binary expansion (which is not also a one-bit repeating sequence): 001, 010, 100, 110, 101, or 011. The iterate 001001001... maps into 010010010..., which maps into 100100100..., which in turn maps into the original 001001001...; so this is a 3-cycle of the bit shift map. And the other three binary-expansion repeating sequences give the 3-cycle 110110110... → 101101101... → 011011011... → 110110110.... Either of these 3-cycles can be converted to fraction form: for example, the first-given 3-cycle can be written as {{sfrac|1|7}} → {{sfrac|2|7}} → {{sfrac|4|7}} → {{sfrac|1|7}}. Using the above translation from the bit-shift map to the <math>r = 4</math> logistic map gives the corresponding logistic cycle 0.611260467... → 0.950484434... → 0.188255099... → 0.611260467.... We could similarly translate the other bit-shift 3-cycle into its corresponding logistic cycle. Likewise, cycles of any length {{mvar|k}} can be found in the bit-shift map and then translated into the corresponding logistic cycles.

However, since almost all numbers in {{math|[0,1)}} are irrational, almost all initial conditions of the bit-shift map lead to the non-periodicity of chaos. This is one way to see that the logistic {{math|''r'' {{=}} 4}} map is chaotic for almost all initial conditions.

The number of cycles of (minimal) length {{math|''k'' {{=}} 1, 2, 3,…}} for the logistic map with {{math|''r'' {{=}} 4}} ([[tent map]] with {{math|''μ'' {{=}} 2}}) is a known integer sequence {{OEIS|id=A001037}}: 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161.... This tells us that the logistic map with {{math|''r'' {{=}} 4}} has 2 fixed points, 1 cycle of length 2, 2 cycles of length 3 and so on. This sequence takes a particularly simple form for prime {{mvar|k}}: {{math|2 ⋅ {{sfrac|2<sup>''k'' − 1</sup> − 1|''k''}}}}. For example: 2&nbsp;⋅&nbsp;{{sfrac|2<sup>13 − 1</sup> − 1|13}} = 630 is the number of cycles of length 13. Since this case of the logistic map is chaotic for almost all initial conditions, all of these finite-length cycles are unstable.