Order Statistics and Inverse Transform Sampling

Reported in interviews at PDT Partners Renaissance Technologies Squarepoint Capital

Problem statement

Inverse transform sampling turns a single uniform draw into a sample from a target distribution. If $U \sim \text{Uniform}(0,1)$ and $F$ is a CDF, then $X = F^{-1}(U)$ has CDF $F$.

Implement the function:

def inverse_transform(dist, u, lam):
    ...

Given u (a value in $(0,1)$ representing a uniform draw), return the closed-form inverse CDF $F^{-1}(u)$ for the distribution named by dist:

  • 'exponential': rate lam, $F(x) = 1 - e^{-\lambda x}$ for $x \ge 0$; return $-\ln(1-u)/\lambda$.
  • 'cauchy': standard Cauchy$(0,1)$; return $\tan(\pi(u - \tfrac12))$.
  • 'logistic': standard Logistic$(0,1)$; return $\ln(u/(1-u))$.
  • 'uniform': Uniform$(0,1)$; return $u$.

lam is the exponential rate and is ignored by the other distributions. Return the numeric value (do not print).

For distributions with no closed-form inverse CDF (e.g. Normal$(0,1)$), fallbacks include the Box-Muller transform, a numerical inverse, rejection sampling, or MCMC.

Example

inverse_transform('exponential', 0.5, 1.0) -> 0.6931471805599453

With $u=0.5$ and rate $\lambda=1$, $F^{-1}(u) = -\ln(1-0.5)/1 = -\ln(0.5) = \ln 2 \approx 0.6931$, the median of the unit-rate exponential.

Show hint

What happens to the probability $P(F^{-1}(U) \le x)$ when $U$ is uniform and you apply $F$ to both sides of the inequality?

Relevant roles: Research Scientist, Applied Scientist, ML Engineer and Data Scientist.

Related free problems