Exercise 14.20 [primitivesamplingexercise]
Consider the problem of generating a random sample from a specified distribution on a single variable. Assume you have a random number generator that returns a random number uniformly distributed between 0 and 1.

Let $X$ be a discrete variable with $P(Xx_i)p_i$ for $i{1,\ldots,k}$. The cumulative distribution of $X$ gives the probability that $X{x_1,\ldots,x_j}$ for each possible $j$. (See also Appendix [mathappendix].) Explain how to calculate the cumulative distribution in $O(k)$ time and how to generate a single sample of $X$ from it. Can the latter be done in less than $O(k)$ time?

Now suppose we want to generate $N$ samples of $X$, where $N\gg k$. Explain how to do this with an expected run time per sample that is constant (i.e., independent of $k$).

Now consider a continuousvalued variable with a parameterized distribution (e.g., Gaussian). How can samples be generated from such a distribution?

Suppose you want to query a continuousvalued variable and you are using a sampling algorithm such as LIKELIHOODWEIGHTING to do the inference. How would you have to modify the queryanswering process?