2
$\begingroup$

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!

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ As in your other question, a blatant absurdity in the statement of the exercise: no, $U=\sum\limits_{n=1}^{\infty} X_n$, with $(X_n)$ i.i.d. symmetric Bernoulli on $\{\pm1\}$, is not uniform on $[0,1]$ (in fact $U$ diverges almost surely). What is your source? $\endgroup$ – Did Sep 18 '15 at 8:08
  • $\begingroup$ This does need to be fixed. However, my answer begins with the correct statement (at the end of the first box) that $U \sim Unif(0,1).$ (Random numbers could be formed from a sequence of equally likely 0s and 1s.) $\endgroup$ – BruceET Sep 18 '15 at 8:33
  • $\begingroup$ @Did, sorry about that, I missed that typo. It was supposed to be $2^{-n}X_n$ in the sum. This will converge. I have just edited the problem to fix this typo. Thanks for catching that! $\endgroup$ – User112358 Sep 18 '15 at 12:38
  • 1
    $\begingroup$ And now to $X_n=\lfloor 2^nU\rfloor$, also impossible... $\endgroup$ – Did Sep 18 '15 at 12:57
  • $\begingroup$ I actually believe this is just poor notation, this is exactly how it is written in the problem. It is just meant to say that you take $X_n$ to be the $n^{\text{th}}$ digit in the binary expansion of $U$. So each $X_n$ is either $0$ or $1$. $\endgroup$ – User112358 Sep 18 '15 at 13:02
1
$\begingroup$

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.$

enter image description here

|cite|improve this answer
$\endgroup$
  • $\begingroup$ So once I can show that the sum of the $2^{-n} X_n$'s produces a uniform $(0,1)$ random variable I can use the inverse CDF method to produce a random variable that has the desired distribution? Also once I have one such variable, do you have any idea how I can get a sequence of them? Thanks so much for all of your help, I have never heard of this method until today, so I would have been out of luck. $\endgroup$ – User112358 Sep 18 '15 at 13:09
  • 1
    $\begingroup$ Not sure about the notation $2^{-n}X_n$, so I'll say once you know how to get $U \sim Unif(0,1)$ you can use the inverse CDF method as you say. Presumably then, you can get an indep sequence $U_1, U_n, \dots U_n$ and get an indep seqence $F^{-1}(U_1) = X_1,$$F^{-1}(U_2) = X_2, \dots,$ $F^{-1}(U_2) = X_n.$ In my simulation runif(m, 0, 1) generates $m$ unifs, so x = -log(1-u) is a vector of $m$ exponentials. Histogram of them is in the panel at upper right in my fig. Also, mean(x) is the sample mean $\bar X$ of these $m$ exponential observations. This samp mean approx pop mean $\mu$. $\endgroup$ – BruceET Sep 18 '15 at 16:06
  • 1
    $\begingroup$ Another, perhaps simpler, example is to take $\sqrt{U_i} = X_i \sim Beta(2,1),$ which has PDF $f(x) = 2x,$ for $x \in (0,1)$ and hence $F(x) = x^2$ and $F^{-1}(u) = \sqrt{u},$ for $u \in (0,1).$ See Wikipedia for more on exponential and beta distributions as needed. $\endgroup$ – BruceET Sep 18 '15 at 16:17
0
$\begingroup$

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.

enter image description here

|cite|improve this answer
$\endgroup$

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.