Consider the problem of generating a random sample Iron, a specified distribution on a single variable. You can assume that a random number generator is available that returns a random number uniformly distributed between 0 and 1.

(a). Let X be a discrete variable with P (X = x_i) = p_i for I Є {1,..., k}. The cumulative distribution of X gives the probability that X Є {x₁… x _j} for each possible j. 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 runtime 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 LIKELIHOOD WEIGHTING to do the inference. How would you have to modify the query answering process?