On random variables made up of independent random digits

Question

Some random variables can be expressed as a binary expansion whose digits are chosen independently at random; this is called a convolution. One example of this kind of random variable is the one for an exponential distribution truncated to the interval $[0, 1]$ (Devroye and Gravel 2020).

However, there seem to be limits on how practical this approach is to describe random variables.

The following is part of Kakutani's theorem (Kakutani 1948): Let $a_j$ be the $j$th binary digit probability in a random variable's binary expansion (starting with $j=1$ for the first digit after the point), where the variable is in $[0, 1]$ and each digit is independently set (that is, each digit is an independent Bernoulli random variable). Then the random variable is absolutely continuous if and only if the sum of squares of $(a_j - 1/2)$ converges. In other words, the digits in the binary expansion become less and less biased as they move farther and farther from the binary point.

An absolutely continuous random variable in $[0, 1]$ can thus be built if we can find an infinite sequence $a_j$ that converges to 1/2. Then that variable could be formed by setting the digits after the point in its infinite binary expansion to 1 with probability equal to the corresponding $a_j$ (that is, the variable's digits are independent Bernoulli random variables with parameter equal to the corresponding $a_j$). However, experiments show that the resulting variable will have a discontinuous probability density function (PDF) in general.

I conjecture the following:

1. For β = 2, the random variable's PDF will be continuous only if—

   • the probabilities of the first half, interval (0, 1/2), are proportional to those of the second half, interval (1/2, 1), and
   • the probabilities of each quarter, eighth, etc. Are proportional to those of every other quarter, eighth, etc.

2. The random variable's PDF will be continuous only if the sequence has the form—$$a_j=\frac{\exp(w/\beta^j)}{1+\exp(w/\beta^j)}, $$ where β = 2 and w is a constant. Special cases of this include the uniform distribution (w = 0), the truncated exponential(1) distribution (w = −1; (Devroye and Gravel 2020)), and the more general truncated exponential(λ) distribution (w = −$\lambda$). We also have the special case of 1 minus a truncated exponential(w) random variable when w > 0, as well as the special case a_j = y^v/βj/(1 + y^v/βj), with w = ln(y)*v where y > 0 and v are constants. As evidence in favor of this conjecture, experiments show that sequences z(j)/(1 + z(j)), other than sequences of the form just given, will generally result in a discontinuous PDF even if z(j) converges to 1 and even if β is other than 2.

3. A similar behavior to (1) applies for β other than 2 (non-base-2 or non-binary cases) as it does to β = 2 (the base-2 or binary case).

My question is: Is there a proof for these conjectures? My attempts at trying to prove them using SymPy have failed, notably because it can't yet evaluate the infinite products needed to check my tries. (One example is (exp(2**(-j)*(I*x - 1)) + 1)/(1 + exp(-2**(-j))).) And I suspect that proving these conjectures might involve studying the distribution's characteristic function or Fourier transform, as Claude Gravel told me (see also Devroye and Gravel 2020, section 3.8).

Note: All statements about random variables, etc., are with respect to Lebesgue measure.

REFERENCES:

• S. Kakutani, "On equivalence of infinite product measures", Annals of Mathematics 1948.
• Devroye, L., Gravel, C., "Random variate generation using only finitely many unbiased, independently and identically distributed random bits", arXiv:1502.02539v6 [cs.IT], 2020.

Answer 1

I have found a paper by George Marsaglia on this question. In effect, the only absolutely continuous distributions of the kind given in the question are one of the following:

• The distribution is piecewise exponential (and thus has a piecewise continuous density).
• The distribution's density function vanishes somewhere in every open interval (and is thus not continuous).

REFERENCES:

• George Marsaglia. "Random Variables with Independent Binary Digits." Ann. Math. Statist. 42 (6) 1922 - 1929, December, 1971. https://doi.org/10.1214/aoms/1177693058

Answer 2

This is an answer for conjecture $2$, not conjecture $3$.

---

As aschepler says in the comments, conjecture $1$ is true because the binary digits are chosen independently. This answer is entirely dependent on that conjecture. In order for that to be satisfied, you need that $$P\left(\frac{a}{2^n}\le X< x+\frac{a}{2^n}\mid\frac{a}{2^n}\le X<\frac{a+1}{2^n}\right)$$

is equal for all $a$ such that $0 \le a \le 2^n-1$, where $0 < x < \frac{1}{2^n}$ and $X$ is the randomly generated number. Let $F(x)$ be the CDF of $X$. This expression is then equal to

$$\frac{F\left(x+\frac{a}{2^n}\right)-F\left(\frac{a}{2^n}\right)}{F\left(\frac{a+1}{2^n}\right)-F\left(\frac{a}{2^n}\right)}$$

This means that it must be true that

$$\frac{F(x)}{F\left(\frac{1}{2^n}\right)} = \frac{F\left(x+\frac{a}{2^n}\right)-F\left(\frac{a}{2^n}\right)}{F\left(\frac{a+1}{2^n}\right)-F\left(\frac{a}{2^n}\right)} \to \frac{F(x)}{F\left(\frac{1}{2^n}\right)}\left(F\left(\frac{a+1}{2^n}\right)-F\left(\frac{a}{2^n}\right)\right)+F\left(\frac{a}{2^n}\right) = F\left(x+\frac{a}{2^n}\right)$$

In order for the derivative to be continuous at $\frac{a}{2^n}$, it must be true that $$f\left(\frac{a}{2^n}\right) = \frac{f(0)}{F\left(\frac{1}{2^n}\right)}\left(F\left(\frac{a+1}{2^n}\right)-F\left(\frac{a}{2^n}\right)\right)$$

Using the fact that $F\left(\frac{1}{2^n}\right) = (1-a_1)(1-a_2)\cdots(1-a_n)$ and $f\left(\frac{2a}{2^{n+1}}\right) = f\left(\frac{a}{2^n}\right)$, this can be simplified to $$f\left(\frac{2a+1}{2^{n+1}}\right) = f\left(\frac{a}{2^{n}}\right)\left(\frac{1}{1-a_{n+1}}-1\right)$$

which means that $$\frac{f\left(x + \frac{1}{2^{n}}\right)}{f(x)}=c_n$$

Since this must be true for all $x$ of the form $\frac{a}{2^n}$ and all $n$ and because $f(x)$ must be continuous, $f(x)$ must be an exponential function (i.e. $f(x) = c\cdot e^{bx}$) such that $\int_0^1 f(x)dx = 1$. If $f(x)$ didn't have to be continuous, the function could take any value at numbers not of the form $\frac{a}{2^n}$. But because it does have to be continuous, $$f(x) = \frac{b}{e^b-1}e^{bx}$$

This then means that $$c_n= e^{b/2^n} \to a_n = 1-\frac{1}{1+e^{b/2^n}}=\frac{\exp\left( b/2^n \right)}{1+\exp\left( b/2^n \right)}$$

which is the same as your result.