![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
guslMost programming languages provide us with an independent identically-distributed (IID) source of random variables, distributed uniformly between 0 and 1.
To convert this uniform distribution to any arbitrary 1D distribution, we need the inverse of the CDF of the distribution.
However, for arbitrary 2D distributions, it's not so clear. For one thing, it's not so clear what a 2D CDF would be, and whether it would take 1 or 2 arguments.
Still, I came up with a naive algorithm for a 2D generator:
(1) Find the distribution of the x component by integrating over y for each value in the x-axis (you could also choose some x's and interpolate: then you won't need to do this for *every* value), and generate an x_0 using the 1D generator.
(2) Find the distribution of the y component, conditioned on x=x_0 (computationally trivial). Generate y_0 using the 1D generator.
I really think I could do better here. How?
---
I also thought of a Las Vegas algorithm:
(1) create a geometrical shape inside your distribution, and integrate the PDF inside it. Call the result I.
(2) if random() < I, you fall inside the shape. If this area is precise enough, you're done.
If it's not precise enough, we make a PDF in this area (set all values outside to zero, and divide all values inside by I: best done lazily). Go back to 1.
(3) if random() >= I, you fall outside the shape.
If the area outside the shape is precise enough, you're done.
If it's not precise enough, we make a PDF in this outside area (set all values outside to zero, and divide all values inside by I: best done lazily). Go back to 1.
Improvement
If you partition the space into more subsets, you will save random numbers. They are a resource afterall (although maybe you can recycle them, using the residue).
To convert this uniform distribution to any arbitrary 1D distribution, we need the inverse of the CDF of the distribution.
inv-cdf(random()) will generate the distribution we want.However, for arbitrary 2D distributions, it's not so clear. For one thing, it's not so clear what a 2D CDF would be, and whether it would take 1 or 2 arguments.
Still, I came up with a naive algorithm for a 2D generator:
(1) Find the distribution of the x component by integrating over y for each value in the x-axis (you could also choose some x's and interpolate: then you won't need to do this for *every* value), and generate an x_0 using the 1D generator.
(2) Find the distribution of the y component, conditioned on x=x_0 (computationally trivial). Generate y_0 using the 1D generator.
I really think I could do better here. How?
---
I also thought of a Las Vegas algorithm:
(1) create a geometrical shape inside your distribution, and integrate the PDF inside it. Call the result I.
(2) if random() < I, you fall inside the shape. If this area is precise enough, you're done.
If it's not precise enough, we make a PDF in this area (set all values outside to zero, and divide all values inside by I: best done lazily). Go back to 1.
(3) if random() >= I, you fall outside the shape.
If the area outside the shape is precise enough, you're done.
If it's not precise enough, we make a PDF in this outside area (set all values outside to zero, and divide all values inside by I: best done lazily). Go back to 1.
Improvement
If you partition the space into more subsets, you will save random numbers. They are a resource afterall (although maybe you can recycle them, using the residue).