Efficient alternative for Example 0.5: An Accept-Reject Distribution

[Banyc]

I am still learning math so there could be factual errors!

Let suppose the range of the output is in $[0, 1]$. We could just multiply it with $a$ if we want to extend its range to $[0, a]$.

The PDF of the distribution implied by the example is

$$f(x) = \begin{cases} 2x & 0 \leq x < 1 \\\ 0 & \text{otherwise} \end{cases}$$

Its CDF is

$$P(X < x) = \begin{cases} x^2 & 0 \leq x < 1 \\\ 0 & \text{otherwise} \end{cases}$$

According to the universality of uniform distribution

Let $F$ be a CDF which is a continuous function and strictly increasing on the support of the distribution.
This ensures that the inverse function $F^{-1}$ exists, as a function from $(0, 1)$ to $\mathbb{R}$.
We then have the following results

• Let $U \sim \text{Unif}(0, 1)$ and $X = F^{-1}(U)$.
  Then $X$ is an r.v. with CDF $F$.
• Let $X$ be an r.v. with CDF $F$.
  Then $F(X) \sim \text{Unif}(0, 1)$.

In this case, $F(x) = P(X &lt; x)$, which is indeed a continuous function that strictly increases.

The inverse of $F$ is

$$F^{-1}(x) = \sqrt{x}, \quad 0 \leq x < 1$$

Apply the $U$ to $F^{-1}$ and we have

$$X = F^{-1}(U) = \sqrt{U}$$

The resulting code is

Math.sqrt(random(1))

[sidwellr]

For "still learning math", you know a lot more than a typical Nature of Code student! The accept-reject algorithm may not be efficient, but it is easy to understand and to customize without having to understand probability theory. I think it is the right level for the Nature of Code.

That said, while reading the custom random distribution section, I also wondered how to do it more efficiently, and came up with the same result. So at least two people are interested in more advanced Nature of Code topics! Probably more. It might be useful to have a forum where Nature of Code students could share insights like this, answers to exercises, and ecosystem projects, as well as help each other and generally socialize.

[dipamsen]

Very relevant video from Stand-up Maths from 2 weeks ago on the topic: https://www.youtube.com/watch?v=ga9Qk38FaHM