Let rv $X$ have a distribution $F (t):={\rm Prob}(X <t)$ and rv $Y$ have a distribution $G (t):=(F(t))^s$ for some constant $s>0$. Suppose that I know an algorithm for generating random variates of $X$. Is there a general argument/theorem, which could help me to construct an algorithm for generating the variates of $Y$ using this information?


Here is an idea based on the rejection method that should work for real $s>1$ without requiring inversion.

The density of $Y$ is given by $$ g(t)=sF(t)^{s-1}f(t) $$ For $s>1$, we thus have $$ g(t)\leq sf(t) $$ as $F(t)\leq1$ and hence $F(t)^{s-1}\leq1$, too.

Hence, we may set up a rejection sampler that treats a draw from $X$ accepted with probability $$ \frac{g(t)}{sf(t)}=F(t)^{s-1} $$ as a draw from $Y$. The idea would not work for $s<1$ as $F(t)^{s-1}>1$ in that case. If $g$ has bounded support, you could use a standard rejection algorithm with a rectangular box around it.

We thus accept draws from $F$ if a uniform r.v.s is less than $g$ (red) divided by $s$ times their density (blue) at that draw. Here is a visualization for the normal case with $s=4$:

enter image description here

Here is an implementation in R for the known case of $\max(X_1,\ldots,X_s)$ for iid $X_i\sim N(0,1)$, that reveals that the algorithm works, but also that it is inefficient as it discards many draws, in particular negative ones. In particular, the unconditional acceptance probability of a draw is $1/s$, the relative area under the two curves.

s <- 4
draws <- 10000
plot(ecdf(replicate(draws,max(rnorm(s)))), lwd=2, col="darkgreen", xlim=c(-1,3)) # the empirical "target"
curve(pnorm(x)^s,-1,3, add=T, lwd=2, col="salmon") # the known theoretical cdf

rejection.method <- function(s,draws){
  X <- rnorm(draws)
  accept <- runif(draws) < pnorm(X)^(s-1)

Y.rejection.method <- rejection.method(s,draws)
curve(ecdf(Y.rejection.method)(x), -1, 3, add=T, lwd=2, col="lightblue") # empirical cdf of the sampler

length(Y.rejection.method)/draws # just around 25%

enter image description here

| cite | improve this answer | |

Given a CDF $P(x)$ and a RNG that generates uniform deviates $U \in (0, 1)$, the standard way of producing non-uniform deviates that follow the CDF is to take $P^{-1}(U)$. So you would generate $X = F^{-1}(U)$ and $Y = G^{-1}(U)$. $G(x) = [F(x)]^s$ implies $G^{-1}(u) = F^{-1}(u^{1/s})$, so $$Y = F^{-1}(U^{1/s}) = F^{-1}([F(X)]^{1/s})$$

| cite | improve this answer | |
  • 1
    $\begingroup$ This would be a valid answer if the algorithm for $X$ is $X=F^{-1}(U)$. This is a special case though, and may not be practicable, so $F^{-1}$ is not part of available information. $\endgroup$ – rytis May 10 '17 at 17:08
  • $\begingroup$ @rytis: The final equation is actually valid regardless of whether CDF inversion is used to generate X. But yes, it does require $F^{-1}$. I am skeptical that you can generate Y from X without at least effectively using $F^{-1}$. $\endgroup$ – David Wright May 10 '17 at 17:27
  • 1
    $\begingroup$ @rytis: I should say the the final equation is distributionally valid regardless of whether CDF inversion is used. That is, individual X and Y values will only be related in this way if CDF inversion is used, but even if CDF inversion is not used, the Ys generated from this equation will have the desired distribution. Also, from an algorithmic perspective, you could argue that you always have $F^{-1}(x)$ if you have $F(x)$, because you can employ a root-finding subroutine. $\endgroup$ – David Wright May 10 '17 at 17:35
  • $\begingroup$ A solvable special case to illustrate that it is possible without explicit knowledge of $F$ is afforded by any integral constant: let $s=1,2,...$, then $Y=\max(X_1, X_2, ..., X_s)$. Any ideas about when $s$ is real? $\endgroup$ – rytis May 10 '17 at 19:31

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.