(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
In the normal settings (without hat function), the idea is to simply to sample points under the surface of the density curve. If the points are chosen at uniform in that space, then the points will follow the density of the given density.
$$ \frac {\delta L} {\delta j} $$