Uniform distribution, as a sum of biased Bernoulli trials.

Question

Suppose that the probability of $x=0$ is $p$, and the probability of $x=1$ is $1-p=q$. Consider the random sequence $X=\{X_i\}_{i=1}^{\infty}$. We map this sequence by $C$ to a point in the interval $[0,1]$ as below:

$1)$ we look at the first random variable. If it is $0$, then we update the interval to $I_1=[0,p)$, else update it to $I_1=[p,1)$.

$2)$ Let $I_k=[a,b)$. Look at the $(k+1)^{th}$ random variable. if it is $0$, then we update the interval to $I_{k+1}=[a,a+p(b-a))$, else we update it to $I_{k+1}=[b-q(b-a),b)$.

and we continue this process till we reach to a point as the length of the random process goes to infinity. As an example if the first $2$ random variables are $01$, then we have:

$I_1=[0,p)$

$I_2=[p-qp,p)$.

Find the pdf of $C(X)$.

Answer 1

Intuitively, we observe that probability of $C(X)$ being inside an interval (for example $[p,1)$) is proportional to the length of the interval.

Notice that $C(X)$ is not well defined for $p=0,1$. So let us assume $0<p<1$. Define new random variables $Y_{i}=p(1-X_{i})+qX_{i}$. Then $Y_{i}=p$ with probability $p$, and $Y_{i}=q$ with probability $q$.

Observe that $C(X)$ can also be written as \begin{eqnarray} C(X)=pX_{1}+p\sum_{k=2}^{\infty}\prod_{i=1}^{k-1}X_{k}Y_{i}. \end{eqnarray}

Basically $\prod_{i=1}^{k-1}Y_{i}$ measures the length of the intervals at $(k-1)th$ step. If $p=\frac{1}{2}$, then $\prod_{i=1}^{k-1}Y_{i}=\frac{1}{2^{k-1}}$, otherwise it depends on the position of the intervals and previous $X_{i}$s.

Now let us pick a $x\in[0,1]$. There is a unique sequence of numbers $\{x_{i}\}$ such that \begin{eqnarray} x=px_{1}+p\sum_{k=1}^{\infty}\prod_{i=1}^{k-1}x_{k}y_{i}, \end{eqnarray} where $x_{i}\in\{0,1\}$ and $y_{i}=p(1-x_{i})+qx_{i}$ for all $i$. We want to find $\mathbb{P}(C(X)\leq x)$.

Let $s=\{s_{i}\}$ be a sequence of numbers from $\{0,1\}$, and $k$ be the first position where $s$ differs from $x$. In other words, $s_{i}=x_{i}$ for all $1\leq i< k$ and $s_{k}\neq x_{k}$. Notice that we have $C(s)\leq x$ only if $s_{k}\leq x_{k}$. But if $x_{k}=0$, then $s_{k}\leq x_{k}$ implies that $s_{k}=0$ i.e., $s_{k}=x_{k}$. In other words, $s_{k}$ can not differ from $x_{k}$ if $x_{k}=0$. So the only possibility is $x_{k}=1$ and $s_{k}=0$. Therefore \begin{eqnarray} \mathbb{P}(C(X)\leq x)&=&\sum_{k: x_{k}=1}\mathbb{P}(X_{i}=x_{i}\;\forall\;1\leq i\leq k-1, X_{k}\neq x_{k})\\ &=&px_{1}+p\sum_{k=1}^{\infty}\prod_{i=1}^{k-1}x_{k}y_{i}\\ &=&x. \end{eqnarray} Consequently $C(X)\sim U[0,1]$.

Answer 2

At the $n$th step, $I_n=J$, where $J$ is one of $2^n$ disjoint intervals whose union is $(0,1)$. Each of these intervals $J$ has length $p^kq^{n-k}$ for some $0\leqslant k\leqslant n$ and the probability that $I_n=J$ is $p^kq^{n-k}$. This holds for every $n$ hence $C(X)$ is uniformly distributed in $(0,1)$.