(a) In Example 4.2, explain in detail how to generate from the sampling density $g$ that corresponds to the hat function $h$ of Figure 4.2, by inversion.
The rejection method
So, let's restate the idea:
We need to generate a variable X under the density $f$
$$S(f) = \{ (x, y) \in \mathbb{R}^2 : 0 \leq y \leq f(x) \}$$Proposition 4.1
$(X,Y)$ is a random point uniformly distributed in $S(f)$, then $X$ has density $f$.
if $X$ has density $f$ and the conditional distribution of $Y$ given $X$ is $U(0, f(X))$, $(X,Y)$ is uniformly distribution over $S(f)$.
The goal therefore is to generate $(X, Y)$ uniformly in $S(f)$.
The idea The trick to achieve that is to generate $(X,Y)$ in a space that encloses S(f) and check if $(X, Y) \in S(f)$. If it does belong, then we return it as a random point of the density $S(f)$, otherwise we try again.
The problem So if the enclosing space is huge in relation to the volume of $S(f)$, it would be expected that very few points actually land in $S(f)$ and therefore most of the randomly generate points are lost.
Therefore, depending on the shape of the enclosing space and $S(f)$, this procedure can become extremely wasteful or work pretty well.
The hat function trick (majoring function) The idea is to scale a know density function $g$ over $S(f)$ from which the sampling is done
$$f(x) \leq ag(x)$$$$ \frac {\delta L} {\delta j} $$