Construct a sequence of i.i.d random variables with a given a distribution function

Question

I am being asked to solve the following problem:

Assume you have a sequence of i.i.d. (independent identically distributed) random variables, $X_1, X_2, \dots,$ on a probability space $(\Omega,\mathcal{F},P)$ with $P(X_n=1)=P(X_n=-1)=1/2$. Given a distribution function, $F$, use the $X_n$'s to construct a sequence of i.i.d. random variables, $Y_1, Y_2, \dots,$ with distribution function $F$. [Hint: First show that $U=\sum_{n=1}^{\infty} 2^{-n}X_n$ is a Uniform$([0,1])$ random variable, then use $U$ to find one random variable with distribution function F.]

If it helps this was the part (b) of the problem. Prior to this, in part (a) we were asked to solve:

Let $U$ be a Uniform($[0,1]$) random variable (i.e., the distribution of $U$ is the Lebesgue measure on $[0,1]$). Define $X_n=\lfloor 2^n U \rfloor, \ n= 1,2,\dots,$ to be the $n^{\text{th}}$ digit in the binary expansion of $U$
($\lfloor x \rfloor$ is the greatest integer less than or equal to $x$). Show that $X_1, X_2, \dots $ are i.i.d. random variables. Note i.i.d. stands for independent identically distributed.

So in any help you provide feel free to use this result, without proof.

I am really lost, I don't know how to proceed.

I would appreciate any help.

Thanks!

Answer 1

I believe you are being asked to use the 'inverse CDF' or 'quantile' method of generating random variables. I will show you how it works and let you fill in the technical details for a proof.

Suppose we have $U \sim Unif(0, 1)$. In applied simulation, this is the normal starting point because pseudorandom number generators (PRNGs) typically supply such standard (continuous) uniform values in sequences that behave as if they are independent for practical purposes.

Also suppose we want to generate a random sample from an exponential population with rate 1 (hence also mean 1). If $X \sim Exp(1),$ then the CDF of $X$ is $F(x) = 1 - e^{-x},$ for $x > 0.$ The quantile function $F^{-1}(u)$ is $F^{-1}(u) = -\log(1 - u),$ were we use logs base $e$. Thus if $U \sim Unif(0,1)$, then one can show that $F^{-1}(U) = X \sim Exp(1).$

Below is a demonstration using R statistical software: Notice that simulated samples of size $m = 100,000$ have very nearly the theoretical means and standard deviations.

 m = 10^5;  u = runif(m, 0, 1);  x = -log(1-u)
 mean(u);  sd(u);  sqrt(1/12)
 ## 0.4989191  # approx E(U) = 1/2
 ## 0.2887617  # approx SD(U) = sqrt(1/12)
 ## 0.2886751
 mean(x);  sd(x)
 ## 0.9974556  # approx E(X) = 1
 ## 1.001592   # approx SD(X) = 1

Simulated points in a histogram bar for $U$ are transformed into points in a bar of the same color in the histogram for $X$. Each histogram shows 100,000 simulated values; density functions are shown in blue. Empirical cumulative distribution functions each show 2000 points. Theoretical CDFs are shown in light blue.

In the panel at lower right, imagine a randomly chosen point $u$ along the vertical axis, move horizontally to the CDF, then vertically down to to the corresponding $x$. For example, an observation at $u = 0.8$ gets transformed to $x \approx 1.61.$

Answer 2

The notation in the first part of the posted problem is confusing. Also, I believe that the 'floor' function is intended to change $-1$s to $0$s, but that is not what it actually does. Comments have highlighted difficulties, but not how to solve them. I believe the fundamental idea you intend to use is sound.

Below I show a slightly different way to accomplish what I believe was intended. The idea is to use binary bits 0 and 1 (equally likely) to simulate a realization $U$ of $Unif(0,1)$.

Let $B_1, B_2, \dots, B_d$ be a sequence of $0$s and $1$s with $P(B_k = 0) = P(B_k = 1) = 1/2.$ Then $U = \sum_{k=1}^d 2^{-k}B_k$ is a discrete random variable that is approximately $Unif(0, 1)$ and the approximation gets better with increasing number of binary digits $d$.

The required $B_k$ can be generated as $Bern(1/2) = Binom(1, 1/2).$ (Essentially tossing a fair coin with 0=Tails and 1=Head, $d$ times.) The following R code shows how a sum of $d = 10$ terms based on such bits accumulates to a give the initial decimal digits of a uniformly distributed random variate--in this particular case approximately 0.310547.

 b = rbinom(10, 1, 1/2);  k = 1:10;  t = 2^(-k)*b
 cbind(k, b, t, cumsum(t))
        k x           t          
  [1,]  1 0 0.000000000 0.0000000
  [2,]  2 1 0.250000000 0.2500000
  [3,]  3 0 0.000000000 0.2500000
  [4,]  4 0 0.000000000 0.2500000
  [5,]  5 1 0.031250000 0.2812500
  [6,]  6 1 0.015625000 0.2968750
  [7,]  7 1 0.007812500 0.3046875
  [8,]  8 1 0.003906250 0.3085938
  [9,]  9 1 0.001953125 0.3105469
 [10,] 10 0 0.000000000 0.3105469

A loop generating $m=100,000$ such uniform random deviates is shown below (but using $d=20$ for better accuracy). The sample mean of these 100,000 values is nearly $E(U)$ and their standard deviation is nearly $SD(U) = \sqrt{1/12}.$

 m = 10000;  u=numeric(m); d = 20; k = 1:d
 for (i in 1:m) {
   b = rbinom(d, 1, 1/2);  u[i] = sum(b*2^{-k}) }
 mean(u);  sd(u);  sqrt(1/12)
 ## 0.5009656  # approx E(U) = 1/2
 ## 0.2887220  # approx SD(U)
 ## 0.2886751  #   exact

The histogram of these $m$ simulated variates below has 1/16 bins. The first four binary digits of a variate determine into which bin the variate will fall.