Describe the algorithm to generate random numbers from an arbitrary discrete distribution with finite number of...

Describe the algorithm to generate random numbers from an arbitrary discrete distribution with finite number of outcomes.

Solutions

Expert Solution

Ans.

One of the best algorithms for sampling from a discrete distribution is the alias method.

The alias method (efficiently) precomputes a two-dimensional data structure to partition a rectangle into areas proportional to the probabilities.seebin fig1

In this schematic from the referenced site, a rectangle of unit height has been partitioned into four kinds of regions--as differentiated by color--in the proportions 1/21/2, 1/31/3, 1/121/12, and 1/121/12, in order to sample repeatedly from a discrete distribution with these probabilities. The vertical strips have a constant (unit) width. Each is divided into just one or two pieces. The identities of the pieces and the locations of the vertical divisions are stored in tables accessible via the column index.

The table can be sampled in two simple steps (one for each coordinate) requiring generating just two independent uniform values and O(1)O(1) calculation. This improves on the O(log(n))O(log⁡(n)) computation needed to invert the discrete CDF as described in other replies here.

milcah answered 8 months ago

Next > < Previous

Related Solutions

A computer was used to generate ten random numbers from a normal distribution with a set...

A computer was used to generate ten random numbers from a normal distribution with a set of unknown mean and variance: −1.1623, 0.2210, 1.6518, −1.1312, −0.2879, −1.0458, 1.3706, −0.7492, −0.1355, −1.2686. Eight more random normal numbers with the same variance perhaps a different mean were then generated (the mean may or may not actually be different): 0.3472, 2.2437, 1.0712, 2.5906, 0.5163, −1.1743, 0.0473, −0.8338. (a) What do you think the means of the random normal number generators were? What do...

a) Using the programming tool of your choice generate 10 random numbers from a flat distribution...

a) Using the programming tool of your choice generate 10 random numbers from a flat distribution between -0.5 and 0.5, and find the mean of these 10 numbers. Consider this mean to be the ‘result’ of this procedure. b) Repeat this 10 times and calculate the mean and variance of your 10 results. Is the distance of the mean from 0 about what you would expect? Why? c) Now repeat it 100 times and calculate the mean and variance. Is...

Generate 1000 random numbers from ??3? starting with standard normal random numbers in R.

Generate 1000 random numbers from ??2, 5? starting with standard normal random numbers in R.

Generate 1000 random numbers from a normal distribution with mean 1 and variance 2 using Box‐Muller...

Generate 1000 random numbers from a normal distribution with mean 1 and variance 2 using Box‐Muller transformation in R.

Use R to generate two random numbers n11, n21 from the Binomial distribution: Bin(10, 0.4). Print...

Use R to generate two random numbers n11, n21 from the Binomial distribution: Bin(10, 0.4). Print your results. Please don’t forget to use the command set.seed(101) before the commands gen- erating the random numbers. (b) (2 points) Use the R command ntable < − array(data = c(n11, n21, n1plus-n11, n2plus-n21), dim = c(2,2)) to create a 2 × 2 table using the numbers generated in part (a) above. Print your table. (c) (3 points) Perform the Fisher’s exact test on...

Propose two of your own random number generation schemes. Please generate 100 random numbers ?? (?...

Propose two of your own random number generation schemes. Please generate 100 random numbers ?? (? = 1,2, … ,100) for each scheme and show the results on the same plot for comparison (i.e., x-axis of the plot will show the index ? and y-axis will show the generated random numbers ??. You can use different colors and/or symbols to distinguish one sequence from the other). Discuss which scheme will be preferred.

Give an example of a discrete distribution which has finite first and second moments, but the...

Give an example of a discrete distribution which has finite first and second moments, but the third moment does not exist.

Consider the probability distribution of the discrete random vector [Χ,Y ] where Χ represents the number...

Consider the probability distribution of the discrete random vector [Χ,Y ] where Χ represents the number of orders for chickens in August at neighbouring supermarket and Y represents the number of orders in September. The joint distribution is shown in the following table: 6 Χ Y 100 200 300 400 500 100 0.06 0.05 0.05 0.01 0.01 200 0.07 0.05 0.01 0.01 0.01 300 0.05 0.10 0.10 0.05 0.05 400 0.05 0.02 0.01 0.01 0.03 500 0.05 0.06 0.05 0.01...

Part (a) Write a number guessing game using System.Collections.Generic.Dictionary. Generate 10 distinct random numbers in the...

Part (a) Write a number guessing game using System.Collections.Generic.Dictionary. Generate 10 distinct random numbers in the range of 1 to 20. Each random number is associated with a prize money (from 1 to 10000). Use a Dictionary to store the mapping between the random number and the prize money. Ask user for two distinct numbers, a and b, both from 1 to 20; if a and b are not distinct, or out of range, quit the program Lookup the prize...

Subjects