Probability of $ \sum_{n=1}^\infty \frac{x_n}{2^n} \leq p$ for Bernoulli sequence

Solution 1:

You can just condition on the first term in the sequence and then use scale invariance.

Suppose that the terms $X_n$ are distributed as Bernoulli$(q)$, so $P(X_i=1)=q$ and $P(X_i=0)=1-q$.

Let $Z := \sum_1^{\infty} \frac{X_n}{2^n}$. Then write $$P(Z \leq p) = q \cdot P(Z \leq p\;|\; X_1=1)+(1-q) \cdot P(Z \leq p\;|\; X_1=0)$$

Now if $p < 1/2$ then $P(Z \leq p\;|\; X_1=1)=0$ and $P(Z \leq p\;|\; X_1=0) = P(Z \leq 2p)$, where we used the fact that $Z$ has the same distributuon as $2Z-X_1=\sum_1^{\infty}\frac{X_{n+1}}{2^n}$. Similarly, when $p\geq 1/2$ we get that $P(Z \leq p\;|\; X_1=1) = P(Z \leq 2p-1)$ and $P(Z \leq p \;|\; X_1=0)=1$.

Letting $f(p):=P(Z \leq p)$ we see that $f$ therefore satisfies the functional equation $$f(p) = \begin{cases} (1-q)\cdot f(2p) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; ,p < 1/2 \\ q\cdot f(2p-1)+1-q \;\;\;\;\;\;, p\geq 1/2 \end{cases}$$ Now let us consider the special case $q=1/2$. Then using the fact that $f(1)=1$ and $f(0)=0$, we see that $f(k \cdot 2^{-n}) = k \cdot 2^{-n}$ for all $0 \leq k \leq 2^n$, which is easy to show by induction on $n$. By monotonicity of $f$ and by density of dyadic rationals in $[0,1]$ we conclude that $f(p)=p$ for all $p \in [0,1]$, which is the desired result.

The case when $q \neq 1/2$ is a bit more interesting. One obtains that $f(\sum_1^{\infty} p_k2^{-k}) = \sum_1^{\infty} p_k q^{|\{m<k:\; p_m=1\}|}(1-q)^{1+|\{m<k:\; p_m=0\}|}$. One may show that the growth order of $f(p)$ near zero is $O(p^{-\log_2(1-q)})$, and similarly near $1$, it looks like $1-O((1-p)^{-\log_2 q})$.

Solution 2:

Write $p$ in base $2$.

$$\sum_{i = 1}^{\infty} \frac{p_i}{2^i}$$

We don't know these coefficients explicitly but we won't need to in the end. Then you have to look at what are the possible values for the $x_i$.

To get something smaller than $p$, you need to have $x_i = p_i$ up to a certain point where $p_k = 1$ and $x_k = 0$. This happens with probability $\frac{1}{2^k}$. Then, sum over all possible values of $k$ such that $p_k = 1$ (these events are indeed disjoint), which yield exactly $p$.

EDIT : this previous version of the answer did not address the right problem since I thought $p$ was the parameter of the Bernoulli law :

---I don't think the result is $p$. Assume for example $p = \frac{1}{2^n}$, denote $q = 1-p$, to get something lower than $p$ you have to get a zero in your $n$ first terms. Which happens with probability $q^n = \frac{(2^n-1)^n}{2^{n^2}}$ (which is different than $p$ for $n \ge 2$).---