Exercise 14.20 [primitive-sampling-exercise]
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 [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?
-
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 continuous-valued variable with a parameterized distribution (e.g., Gaussian). How can samples be generated from such a distribution?
-
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?