8
$\begingroup$

Consider the following process. For each integer $i \geq 0$, independently sample a Bernoulli distribution with probability $p = 1/2$, obtaining sample $x_i$. Then calculate $x = \sum_{i=0}^\infty x_i \theta^i,$ where $(\theta < 1)$. What is the distribution over $x$?

I see that if θ = 0.5 then this is a uniformly generated binary number between 0 and 2. This post is closely related, but I don't see how the method given there (with θ = 0.5) generalizes to arbitrary $\theta$. I am interested in values of $\theta$ close to 1, such as $\theta = 0.95$.

I am ultimately interested in a hypothesis test: $H_0=$ "$p = 0.5$" against the alternative $H_A=$ "$p \neq 0.5$". The motivation is, I am receiving an infinite sequence of 0s and 1s for which I only retain an exponentially weighted average (not recording the whole sequence). And based on this weighted average I want to decide whether the 0s and 1s were generated with equal probability or not.

Edit: based on an empirical test it appears to be roughly normally distributed. The following was generated by performing a 100,000 sample run with $\theta = 0.95$. It has mean 10 and variance 2.5.

 5.9 
 6.0 
 6.1 *
 6.2 *
 6.3 *
 6.4 *
 6.5 **
 6.6 **
 6.7 **
 6.8 ***
 6.9 ***
 7.0 ****
 7.1 *****
 7.2 *****
 7.3 ******
 7.4 ******
 7.5 ********
 7.6 ********
 7.7 *********
 7.8 *********
 7.9 **********
 8.0 ************
 8.1 ************
 8.2 *************
 8.3 **************
 8.4 ***************
 8.5 ****************
 8.6 *****************
 8.7 ******************
 8.8 *******************
 8.9 *******************
 9.0 ********************
 9.1 *********************
 9.2 **********************
 9.3 ***********************
 9.4 **********************
 9.5 ***********************
 9.6 ***********************
 9.7 *************************
 9.8 ************************
 9.9 ************************
10.0 ************************
10.1 ************************
10.2 *************************
10.3 ************************
10.4 ***********************
10.5 ***********************
10.6 **********************
10.7 ***********************
10.8 **********************
10.9 *********************
11.0 *******************
11.1 *******************
11.2 ******************
11.3 ******************
11.4 ****************
11.5 ***************
11.6 ***************
11.7 *************
11.8 ************
11.9 ************
12.0 ***********
12.1 **********
12.2 *********
12.3 ********
12.4 ********
12.5 *******
12.6 ******
12.7 *****
12.8 *****
12.9 *****
13.0 ****
13.1 ***
13.2 ***
13.3 **
13.4 **
13.5 **
13.6 *
13.7 *
13.8 *
13.9 *
14.0 
14.1 

Normal quantile plot for $\theta=0.90$: Normal quantile plot for theta=0.90 Normal quantile plot for $\theta=0.95$: Normal quantile plot for theta=0.95

Looks like it has thin tails.

$\endgroup$
9
  • $\begingroup$ Maybe work with different, not decimal, system? When it is 1\2, you can use binary code. If it is 1\n i suppose you can do something similiar? $\endgroup$ Apr 2 at 20:28
  • 2
    $\begingroup$ $\theta = \frac12$ is a critical value: below $\frac12$ there will either be a unique $(x_1,x_2,\ldots)$ giving the sum $x$ or no such sequence, while above $\frac12$ there will be multiple $(x_1,x_2,\ldots)$ corresponding to plausible $x$ $\endgroup$
    – Henry
    Apr 2 at 20:28
  • $\begingroup$ @AaronHendrickson Suppose $\theta =0.1$. Then you are suggesting the support is $[0,1.1111\ldots]$ and that does give the range of potential values. But I think for example no values in the open interval $(0.1111\ldots,1)$ are in the support. $\endgroup$
    – Henry
    Apr 2 at 20:34
  • $\begingroup$ @OliverDiaz Yes, but what to do after that? $\endgroup$
    – Clement C.
    Apr 2 at 20:58
  • $\begingroup$ Maybe some CLT with non-iid variables can be used? $\endgroup$ Apr 2 at 21:22
3
$\begingroup$

This type of distribution has a long history. If you apply an affine map $x \mapsto 2x-1$, you may assume the Bernoulli variables take values $\pm 1$. Then the laws of these sums have been studied under the name "Infinite Bernoulli convolutions", see [1], [2] for surveys. The basic result is that for a.e. $\theta \in (1/2,1)$ the laws are absolutely continuous; the exceptions have Hausdorff dimension zero, and all known exceptions are algebraic numbers (in fact, inverse Pisot numbers.)

[1] Peres, Yuval, Wilhelm Schlag, and Boris Solomyak. "Sixty years of Bernoulli convolutions." In Fractal geometry and stochastics II, pp. 39-65. Birkhäuser, Basel, 2000.

[2] Varjú, Péter P. "Recent progress on Bernoulli convolutions." arXiv preprint arXiv:1608.04210 (2016).

$\endgroup$
1
  • $\begingroup$ Is there a good way to efficiently calculate or approximate the cumulative distribution function for $\theta$ near 1? $\endgroup$
    – causative
    Apr 3 at 6:15
2
$\begingroup$

Edit: Here I address the main concern of the OP with regards the behavior of the distribution of $X^{(\theta)}=\sum_{n\geq1}\varepsilon_n\theta^n$ for $0<\theta<1$ close to $1$, where with $(\varepsilon_n)$ and i.i.d sequence of Bernoulli 0-1 random variables.

A few observations:

The law $\mu_\theta$ of $X^{(\theta)}$, $0<\theta<1$, may exhibit quite strange behavior. For example:

  1. when $\theta=1/3$, the law of $Y=2X^{(\theta)}$ happens to be the devil stair's distribution and $Y$ is concentrated in the 1/3 Cantor set.
  2. When $\theta=1/2$, this corresponds to the Lebesgue measure in $(0,1)$ (a.k.a uniform distribution in (0,1). This is not surprising as this correspond to choosing the digits of a number in binary expansion by tossing a fair coin.
  3. The support of the law $\mu_\theta$ of $X^{(\theta)}$ is contained in $[0,\theta(1-\theta)^{-1}]$.

Claim: $X^{(\theta)}$ converges vaguely to $0$ as $\theta\rightarrow1$.

Motivation:

The Lapalace transform of the law of $X^{(\theta)}$ is given by \begin{align} E\big[e^{-tX^{(\theta)}}\big] = \prod_{n\geq1} E\big[e^{-t\epsilon_n\theta^n}\big]= \prod_{n\geq1}\frac{1+e^{-t\theta^n}}{2} =: g(t,\theta) \end{align} ($t>0$) which is increasing in $\theta$. In particular, $\lim_{\theta\rightarrow1-}g(t,\theta)$ exists.

Notice that if $\theta=1$, then the product above is $0$. This is no surprising since the Bernoulli (0,1) random walk diverges to $\infty$ a.s. This suggests that as $\theta\rightarrow1-$, the law $\mu_\theta$ of $X^{(\theta)}$ converges vaguely to $0$; in other words, as $\theta\rightarrow1-$, all the mass is being moved to infinity.

Proof of claim: The crux of the problem is to show that \begin{align} \lim_{\theta\rightarrow1}g(t,\theta) = 0 \tag{1}\label{one} \end{align} For if this is indeed th case, then for any $a>0$

$$ P[X^{(\theta)}\leq a]\leq e^a g(a,\theta)\xrightarrow{\theta\rightarrow1-}0 $$

Now, for fixed $t>0$, $$\Phi_\theta(\omega)=e^{-Yt^{(\theta)}(\omega)}$$ is uniformly bounded $0<\Phi_\theta\leq1$, monotone noninreasing in $\theta$ (i.e. $\Phi_\theta\leq\Phi_{\theta'}$ if $\theta'<\theta$), and $\lim_{\theta\rightarrow1}\Phi_\theta=0$ almost surely since $\sum_n\epsilon_n=\infty$ almost surely. By dominated convergence $\lim_{\theta\rightarrow1-}E\big[e^{-tX^{(\theta)}}\big]=E\big[\lim_{\theta\rightarrow1-}e^{-tX^{(\theta)}}\big]=0$


Final comments:

  • On the other extreme, when $\theta=0$ then $X^{(\theta)}\equiv0$. Hence, as with $1$, the law $\mu_\theta$ converges vaguely (in fact weakly) to $\delta_0$. This case can also been proven by dominated convergence.

  • The symmetric version of the problem, namely $$Z^{(\theta)}:=2 X^{(\theta)}-\frac{\theta}{1-\theta}=\sum_{n\geq1}\xi_n\theta^n$$ where the $\xi_n=2\epsilon_n-1$ form an i.i.d. sequence of Bernoulli $\pm1$ random variables with parameter $p=1/2$, explains why there seem to be some symmetry around some number ($\theta/(1-\theta)$) in the QQplots shown by the OP.

  • The study of the law of $Z^{(\theta)}$, $0<\theta<1$, is a classical problem in Probability consider by Erdös, and a great source of interesting results and open questions.

$\endgroup$
1
  • $\begingroup$ If $\theta = 1$ and $t > 0$ then $\prod_n (1 + e^{t \theta^n})/2$ is an infinite product of terms > 1. $\endgroup$
    – causative
    Apr 3 at 1:21

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.