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.
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 [math-appendix].) 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?
2. 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$).
3. Now consider a continuous-valued variable with a parameterized distribution (e.g., Gaussian). How can samples be generated from such a distribution?
4. Suppose you want to query a continuous-valued variable and you are using a sampling algorithm such as LIKELIHOODWEIGHTING to do the inference. How would you have to modify the query-answering process?