# Tossing a continuous coin

To generate a random number ${X}$ uniformly distributed on the interval ${[0,1]}$, one can keep tossing a fair coin, record the outcomes as an infinite sequence ${(d_k)}$ of 0s and 1s, and let ${X=\sum_{k=1}^\infty 2^{-k} d_k}$. Here is a histogram of ${10^6}$ samples from the uniform distribution… nothing to see here, except maybe an incidental interference pattern.

Let’s note that ${X=\frac12 (d_1+x_1)}$ where ${X_1=\sum_{k=1}^\infty 2^{-k} d_{k+1}}$ has the same distribution as ${X}$ itself, and ${d_1}$ is independent of ${X_1}$. This has an implication for the (constant) probability density function of ${X}$:

$\displaystyle p(x) = p(2x) + p(2x-1)$

because ${2 p(2x)}$ is the p.d.f. of ${\frac12 X_1}$ and ${2p(2x-1)}$ is the p.d.f. of ${\frac12(1+X_1)}$. Simply put, ${p}$ is equal to the convolution of the rescaled function ${2p(2x)}$ with the discrete measure ${\frac12(\delta_0+\delta_1)}$.

Let’s iterate the above construction by letting each ${d_k}$ be uniformly distributed on ${[0,1]}$ instead of being constrained to the endpoints. This is like tossing a “continuous fair coin”. Here is a histogram of ${10^6}$ samples of ${X=\sum_{k=1}^\infty 2^{-k} d_k}$; predictably, with more averaging the numbers gravitate toward the middle.

This is not a normal distribution; the top is too flat. The plot was made with this Scilab code, putting n samples put into b buckets:

n = 1e6
b = 200
z = zeros(1,n)
for i = 1:10
z = z + rand(1,n)/2^i
end
c = histplot(b,z)


If this plot too jagged, look at the cumulative distribution function instead:

It took just more line of code: plot(linspace(0,1,b),cumsum(c)/sum(c))

Compare the two plots: the c.d.f. looks very similar to the left half of the p.d.f. It turns out, they are identical up to scaling.

Let’s see what is going on here. As before, ${X=\frac12 (d_1+X_1)}$ where ${X_1=\sum_{k=1}^\infty 2^{-k} d_{k+1}}$ has the same distribution as ${X}$ itself, and the summands ${d_1,X_1}$ are independent. But now that ${d_1}$ is uniform, the implication for the p.d.f of ${X}$ is different:

$\displaystyle p(x) = \int_0^{1} 2p(2x-t)\,dt$

This is a direct relation between ${p}$ and its antiderivative. Incidentally, if shows that ${p}$ is infinitely differentiable because the right hand side always has one more derivative than the left hand side.

To state the self-similarity property of ${X}$ in the cleanest way possible, one introduces the cumulative distribution function ${F}$ (the Fabius function) and extends it beyond ${[0,1]}$ by alternating even and odd reflections across the right endpoint. The resulting function satisfies the delay-differential equation ${F\,'(x)=2F(2x)}$: the derivative is a rescaled copy of the function itself.

Since ${F}$ vanishes at the even integers, it follows that at every dyadic rational, all but finitely many derivatives of ${F}$ are zero. The Taylor expansion at such points is a polynomial, while ${F}$ itself is not. Thus, ${F}$ is nowhere analytic despite being everywhere ${C^\infty}$.

This was, in fact, the motivation for J. Fabius to introduce this construction in 1966 paper Probabilistic Example of a Nowhere Analytic ${C^\infty}$-Function.