1 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.

a. Let X be a discrete variable with P(X =xi)=pi for i∈ {1, . . . , k}. The cumulative distribution of X gives the probability that X ∈ {x1, . . . , xj} for each possible j. (See also Appendix A.) 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?

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

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

d. 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?