Probability of $ \sum_{n=1}^\infty \frac{x_n}{2^n} \leq p$ for Bernoulli sequence Probability of $ \sum_{n=1}^\infty \frac{x_n}{2^n} \leq p$  for a  Bernoulli(1/2) sequence $(x_n)$ and $p \in [0,1]$. I know that the answer should be just $p$ but how can you prove it?
Say for $p= 1/2$ I can look at it as 1-( Probability of being greater than 1/2) which is 1/2 since if our first term in the sequence is 1 then we're done. But how one shows for general $p$?
 A: 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})$.
A: 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$).---
A: Your knowledge about the answer suggest that the the random variable $Y=\sum_{n=1}^\infty X_n/2^n$ has a uniform distribution on the interval $(0,1)$ and by the means of moment generating functions is possible to prove so:
 for every $t\in\mathbb{R}$, we have
$$
e^{tY}\leq e^{t\wedge0}
$$
Since, clearly, $0\leq Y\leq 1$.
By independence, it follows from the dominated convergence theorem that
$$
\mathbb{E}[e^{tY}]=\prod_{n=1}^\infty\mathbb{E}[\exp({\frac{t}{2^n}X_n})]
$$
Note that the factors in the right hand side are the MGF of Bernoulli(1/2) random variables evaluated at $t/2^n$, so they are equal to $2^{-1}(\exp(2^{-n}t)+1)$. Therefore, we need only to find the product
$$
\prod_{n=1}^\infty 2^{-1}(\exp(2^{-n}t)+1)
$$
After expanding the first partial products, it is not hard to see that the expression for the partial products is given by
$$
\prod_{n=1}^m2^{-1}(\exp(2^{-n}t)+1)=2^{-m}\sum_{n=0}^{2^m-1} \exp(n2^{-m}t)
$$
(This can be proven by induction). The latter is a sum of powers which equals to $(e^t-1)/(e^{2^{-m}t}-1)$. 
We have then
$$
\prod_{n=1}^\infty 2^{-1}(\exp(2^{-n}t)+1)=(e^t-1)\lim\limits_{m\to\infty}\frac{2^{-m}}{e^{2^{-m}t}-1}
$$
And using L'Hôpital's rule it's easy to see that the limit in the right hand side is $1/t$. We therefore get
$$
\mathbb{E}[e^{tY}]=\frac{e^t-1}{t}
$$
Which is the moment generating function of a Uniform(0,1) distribution. By uniqueness of the MGF, $Y$ has such distribution and it follows that, $\mathbb{P}[Y\leq p]=p$ for every $p\in [0,1]$.
