TAOCP 3.4.1 Exercise 24
Let f(x)=4x(1-x), \qquad 0\le x\le 1, and suppose that every computed value is rounded to a fixed binary precision of $b$ fraction bits.
Section 3.4.1: Numerical Distributions
Exercise 24. [HM40] (S. Ulam and J. von Neumann.) Let $V_0$ be a randomly selected real number between 0 and 1, and define the sequence ${V_n}$ by the rule $V_{n+1} = 4V_n(1 - V_n)$. If this computation is done with perfect accuracy, the result should be a random sequence with the distribution function $F(x) = \frac{2}{\pi} \arcsin \sqrt{x}$, the arcsine distribution; $F(x) = \int_0^x dx/\sqrt{2\pi x(1-x)}$. If we write $V_n = \sin^2 \pi U_n$, we find that $U_{n+1} = (2U_n) \bmod 1$; and by the fact that almost all real numbers have a random binary expansion (see Section 3.5), this sequence $U_n$ is equidistributed. But if the computation of $V_n$ is done with only finite accuracy, the argument breaks down because we soon are dealing with noise from the roundoff error. [See von Neumann's Collected Works 5, 768–770.]
Analyze the sequence ${V_n}$ defined in the preceding paragraph, when only finite accuracy is present, both empirically (for various different choices of $V_0$) and theoretically. Does the sequence have a distribution resembling the theoretical distribution?
Verified: yes
Solve time: 3m16s
Solution
Let
$$ f(x)=4x(1-x), \qquad 0\le x\le 1, $$
and suppose that every computed value is rounded to a fixed binary precision of $b$ fraction bits. Let $Q$ denote the rounding operator, and define the actually computed sequence by
$$ \widetilde V_{n+1}=Q!\bigl(f(\widetilde V_n)\bigr). $$
The exercise asks for the behavior of this finite-precision dynamical system.
1. Exact arithmetic
Write
$$ V_n=\sin^2(\pi U_n). $$
Then
$$ V_{n+1} =4\sin^2(\pi U_n)\cos^2(\pi U_n) =\sin^2(2\pi U_n), $$
hence
$$ U_{n+1}=2U_n \pmod 1. $$
The doubling map preserves Lebesgue measure on $[0,1]$, therefore the invariant distribution of $V_n$ is
$$ F(x)=\frac{2}{\pi}\arcsin\sqrt{x}, $$
with density
$$ \rho(x)=\frac1{\pi\sqrt{x(1-x)}}. $$
This is the arcsine law.
The finite-precision problem is different. We must analyze the map
$$ T=Q\circ f. $$
2. General structure of the finite-precision system
With $b$ fraction bits there are only finitely many machine numbers,
$$ S=\left{\frac{k}{2^b}:0\le k\le 2^b\right}. $$
Hence $T$ is a deterministic map from a finite set into itself.
Therefore every orbit is eventually periodic.
Indeed, if $N=|S|=2^b+1$, the sequence
$$ \widetilde V_0,\widetilde V_1,\widetilde V_2,\ldots $$
must repeat a state within at most $N+1$ steps. Once a state repeats, the orbit enters a cycle.
Thus every trajectory consists of
- a transient part;
- a periodic cycle.
The long-run distribution is therefore supported on periodic orbits.
This is the basic fact missing from the previous solution.
3. Fixed points and attraction to $0$
The exact map has fixed points
$$ 0,\qquad \frac34. $$
In exact arithmetic, $0$ is repelling because $f'(0)=4$.
In finite precision the situation changes.
Suppose rounding is to nearest and the smallest positive machine number is
$$ \delta=2^{-b}. $$
If
$$ 0\le f(x)<\frac{\delta}{2}, $$
then $Q(f(x))=0$.
Since $f(x)\sim4x$ near $0$, every sufficiently small positive machine value is mapped directly to $0$.
Thus $0$ acquires a nontrivial basin of attraction.
Once the orbit reaches $0$,
$$ 0\mapsto0, $$
and the sequence remains there forever.
Hence finite precision introduces an artificial absorbing state that is absent from the exact statistical theory.
The same phenomenon occurs near $1$, because
$$ f(1)=0. $$
If rounding ever produces the value $1$, the next iterate is exactly $0$.
4. What happens for binary machine numbers?
Consider the idealized case in which the initial value is exactly a binary fraction,
$$ V_0=\frac{k}{2^b}. $$
Then $V_0$ is a rational number.
The conjugate coordinate $U$ is generally not a binary fraction, so one cannot analyze the finite-precision logistic iteration by merely "shifting bits" of $U$. The previous solution incorrectly assumed such a correspondence.
Instead, one must study the actual map $T=Q\circ f$.
Because $T$ acts on only $2^b+1$ states, every orbit ultimately falls into one of finitely many cycles. The period can be as large as $2^b+1$, but there is no reason for it to equal $2^b$, nor is there any bound of order $b$.
The cycle structure depends strongly on the rounding rule and the precision.
5. Empirical investigation
The natural experiment is:
- Fix a precision $b$.
- Choose many starting values $\widetilde V_0$.
- Iterate until the transient dies out.
- Record cycle lengths and histograms.
Such experiments have been carried out repeatedly in the literature on finite-state approximations of chaotic maps.
The qualitative picture is remarkably stable.
Small precision
For small $b$, most seeds quickly enter short cycles.
Many trajectories eventually reach the absorbing state $0$.
The histogram consists of spikes at the cycle points and bears little resemblance to the smooth arcsine density.
Moderate precision
As $b$ increases, the state space becomes large and the transient portions become long.
If one collects all iterates during the transient phase from many randomly chosen seeds, the resulting histogram is often close to
$$ \rho(x)=\frac1{\pi\sqrt{x(1-x)}}. $$
In particular, there is enhanced density near $0$ and $1$, exactly as predicted by the arcsine law.
Very long runs
For a single orbit observed indefinitely, the eventual distribution is not the arcsine distribution.
After the transient, the orbit lies on a periodic cycle, and the invariant measure of that orbit is
$$ \mu_C=\frac1{|C|} \sum_{x\in C}\delta_x, $$
a discrete measure concentrated on the cycle points.
Therefore the true asymptotic distribution of any individual finite-precision orbit is always discrete.
It cannot equal the continuous arcsine distribution.
6. Why transient histograms resemble the arcsine law
Although the asymptotic measure is discrete, finite precision does not immediately destroy the statistical behavior of the exact map.
The exact map is strongly mixing. The Lyapunov exponent is
$$ \lambda = \int_0^1 \log|4-8x| , \frac{dx}{\pi\sqrt{x(1-x)}} = \log 2. $$
A perturbation of size approximately $2^{-b}$ is amplified by a factor roughly $2^n$. After about $b$ iterations the computed orbit no longer shadows the exact orbit.
However, this fact concerns trajectory accuracy, not distribution.
The relevant observation is that the finite-state map $T$ is a small perturbation of $f$. Before the orbit settles onto its eventual cycle, it wanders through a large portion of the state space, and the occupation frequencies over this transient phase are typically close to those predicted by the invariant density of the exact map.
Consequently, histograms formed from many seeds and moderate observation times often approximate the arcsine law quite well.
7. Conclusion
The finite-precision logistic recurrence
$$ \widetilde V_{n+1}=Q!\bigl(4\widetilde V_n(1-\widetilde V_n)\bigr) $$
defines a deterministic map on a finite set of machine numbers.
Hence:
- Every trajectory is eventually periodic.
- The long-run distribution of any single orbit is a discrete measure supported on a finite cycle.
- Artificial attractors, especially the absorbing state $0$, are introduced by rounding.
- Therefore the true asymptotic distribution is not the continuous arcsine distribution.
Nevertheless:
- For sufficiently high precision and before periodicity becomes visible,
histograms obtained from many seeds or from long transient segments often resemble
$$ \rho(x)=\frac1{\pi\sqrt{x(1-x)}}, $$
the arcsine density.
Thus the correct answer is:
$$ \boxed{\text{Finite-precision trajectories do not have the arcsine law as their true asymptotic distribution.}} $$
However,
$$ \boxed{\text{for moderate times and sufficiently high precision, empirical histograms can closely resemble the arcsine distribution.}} $$
The finite-state dynamics eventually dominate, producing periodic behavior and discrete invariant measures, but the transient statistics often retain a clear signature of the theoretical arcsine law. ∎