5
$\begingroup$

This functional equation appears in the following context. Let $\alpha\in[0,1]$ be an irrational number (called seed) and consider the sequence $x_n=\{2^n \alpha\}$. Here the brackets represent the fractional part function. In particular, $\lfloor 2x_n\rfloor$ is the $n$-th digit of $\alpha$ in base $2$.

The values $x_n$ are distributed in a certain way due to the ergodicity of the underlying process. The density associated with this distribution is the function $f$, and for the immense majority of seeds $\alpha$ that density is uniform on $[0, 1]$, that is, $f(x) = 1, x \in [0, 1]$. Such seeds $\alpha$ producing the uniform density are sometimes called normal numbers; their digit distribution is also uniform.

However, the functional equation $f(x) = \frac{1}{2}\Big(f(\frac{x}{2}) + f(\frac{1+x}{2})\Big)$ may have plenty of other solutions. Such solutions are called non-standard solutions. Can you find a seed $\alpha$ producing a non-standard solution, with an explicit form for $f$? Maybe a step-wise uniform function? The set of seeds producing non-standard solutions is known to have Lebesgue measure zero, but there are infinitely many such seeds.

All rational seeds $\alpha$ work, but they produce a discrete distribution. Thus their density is of the discrete type. Here however, I am interested in a continuous function $f$, even if it has infinitely many points of discontinuity (that is, a function $f$ continuous almost everywhere: the set of discontinuity points has Lebesgue measure zero.)

Update

I am looking for a function $f$ that is a density on $[0, 1]$, so there are additional constraints here: $\int_0^1 f(x)\,dx = 1$ and $f(x) \geq 0$. However, note that if $f$ is a solution, then $cf$ is also a solution regardless of the constant $c$. So any solution can be normalized to integrate to one. Also, $cf+d$ is also a solution ($c, d$ constants).

Second update

Below is a density satisfying all the requirements. Actually, the plot below represents its percentile distribution. It was produced with a seed $\alpha$ built as follows: its $n$-th binary digit is $1$ if $\mbox{Rand}(n) < 0.75$, and $0$ otherwise, using a pseudo random number generator. Note that $P._{25} = 0.5$ and corresponds to a dip ($P._{25}$ denotes the $25$-th percentile.) Dips are everywhere, only the big ones are visible. By contrast, the percentile distribution for the uniform case (if you replace $0.75$ by $0.50$ in $\mbox{Rand}(n) < 0.75$) is a straight line, with no dips.

enter image description here

Note: I eventually answered my question, see the second answer.

$\endgroup$
  • $\begingroup$ $f(x)=0$ is a solution, but it's not clear to me how that would relate to the seed mechanism. $\endgroup$ – Adrian Keister Aug 21 at 16:57
  • 1
    $\begingroup$ One thing we know: $f(0)=f(1/2)=f(1),$ regardless of the solution elsewhere. $\endgroup$ – Adrian Keister Aug 21 at 17:12
  • $\begingroup$ $f(x)=\text{const}$ works for any constant actually. $\endgroup$ – Adrian Keister Aug 21 at 17:17
  • 1
    $\begingroup$ Have you looked at any of the numbers whose digits are known not to be normal or equidistributed, e.g. Liouville numbers? $\endgroup$ – Steven Stadnicki Aug 21 at 17:28
  • $\begingroup$ @StevenStadnicki: it is on my "to do" list, thanks. $\endgroup$ – Vincent Granville Aug 21 at 17:39
4
$\begingroup$

Not an answer, just some thoughts.

Let's try applying Fourier transform:

$$f(x)=\frac{1}{\sqrt{2 \pi}}\int_{-\infty}^\infty e^{i k x} g(k) dk$$

The equation becomes:

$$\int_{-\infty}^\infty \left(2 e^{i k x}-e^{i k x/2} (1+e^{i k /2}) \right) g(k) dk=0$$

Making a simple substitution:

$$\int_{-\infty}^\infty e^{i k x} \left(g(k)- (1+e^{i k }) g(2k) \right) dk=0$$

We can consider a particular case (or is this the general case?):

$$g(k)=(1+e^{i k }) g(2k)$$

Examples:

$$g(0)=0$$

For any $a \neq 0$:

$$g(a)=C$$

$$g(2a)= \frac{C}{1+e^{ia}}$$

$$g(2^n a)= C \prod_{q=1}^{n-1} \frac{1}{1+e^{i q a}}$$

In the same way we can find $g(2^{-n} a)$.

For $a$ not being a rational multiple of $\pi$ the infinite product doesn't converge, and the function itself is not nice.

If we call:

$$G_n= -\log g(2^n), \qquad g(1)=1$$

Then the plot $G_n$ looks like this:

enter image description here

Not sure if this could lead to a non-trivial solution to the original equation though.

$\endgroup$
  • $\begingroup$ I will check this out. Also the constraint that $\int_0^1 f(x) dx = 1$ is not important after all: if $f$ is a solution, then $c\cdot f$ is also a solution regardless of the constant $c$. $\endgroup$ – Vincent Granville Aug 21 at 18:46
  • $\begingroup$ Sounds very interesting and inspiring. I updated my post and included an example of a special function (continuous everywhere it seems, but maybe differentiable nowhere) that satisfies the equation. $\endgroup$ – Vincent Granville Aug 22 at 5:53
2
$\begingroup$

Here I discuss in more detail the case mentioned in the section "second update". This special distribution was produced with a seed $\alpha$ built as follows: its $n$-th binary digit is $1$ if $\mbox{Rand}(n)< p$, and $0$ otherwise, using a pseudo random number generator. I used $p=0.75$ in my example.

Now $x_n$ (introduced in the first paragraph in my question) is a random variable, and we have:

$$x_n=\sum_{k=1}^\infty \frac{d_{n+k}}{b^k}.$$

Here $b$ is the base ($b=2$), and $d_{n+k}$ is the $(n+k)$-th digit of $\alpha$ in base $b$. Furthermore, by construction, these digits are identically and independently distributed with a Bernouilli distribution of parameter $p$. Thus, using the convolution theorem, the characteristic function of $x_n$ is

$$\phi(t; p, b) = \prod_{k=1}^\infty \Big(1-p(1-\exp \frac{it}{b^k})\Big).$$

Take the derivative of the inverse Fourier transform (see section inverse formula here) and you obtain

$$f(x) = \frac{1}{2\pi} \int_{-\infty}^{\infty} e^{-ity} \phi(t; p,b) dy.$$

If $p=0.5$ and $b=2$ we are back to the uniform case. If $p\neq 0.5$ then the solution is quite special: the density $f$ is nowhere continuous it seems. See picture below for $p=0.55, b=2$.

enter image description here

Now we should prove that this case is ergodic, for the functional equation to apply. I also tried to check with some sampled values of $x$ to see whether $f(x) = \frac{1}{2}\Big(f(\frac{x}{2}) + f(\frac{1+x}{2})\Big)$, but the function being discontinuous everywhere, and since I got its value approximated probably to no more than two decimals, it is not easy. The distribution attached to this density has the following moments:

  • Expectation: $\frac{p}{b-1}.$
  • Variance: $\frac{p(1-p)}{b^2-1}.$

An Excel spreadsheet with the computation of $x_n$ up to $n=200,000$ and with a precision of 14 decimals, is available upon request. You can interactively change $b$ or $p$ and see the result on the chart. Despite dealing with more than 200K digits, the computations are done very efficiently. Finally, the functional equation can be adapted to base $b$, provided $b$ is an integer. It becomes:

$$f(x) = \frac{1}{b}\sum_{m=0}^{b-1}f\Big(\frac{x+m}{b}\Big).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.