# Sampling from an unknown distribution

I am using the principle of maximum entropy to fit a density to a given set of samples. I want to generate new set of samples from the approximated density. Is there any way to draw samples from a density obtained by maximum entropy approach?

-
When you "fit" a density, how is the output expressed? –  whuber Jan 11 '12 at 13:18
It would help to say more about those "feature functions." If, for instance, they form a mixture distribution, then the sampling process is reduced to choosing one of those functions randomly and then sampling from it. This could be hugely more efficient than attempting to sample from the density using, say, rejection sampling. –  whuber Jan 13 '12 at 14:27

Construct a piecewise probability distribution curve to fit the data and then use rejection sampling (e.g. see Ziggurat Algorithm to see how to implement rejection sampling).

-
The output is expressed in terms of feature functions defined over the space of the samples and their corresponding coefficients. Locster could you please explain a little bit more. What do you mean by piecewise probability distribution curve to the data? Note that my data is multi-dimenstional. –  Beh Jan 11 '12 at 18:53
Ok so you have a set of functions that define the [relative] density for any given point in the space. For rejection sampling to work you will need the densities to be normalized (for the purposes of this explanation let's say we determine the maximum density observed across the space). So my suggestion then is to generate coordinates in the space randomly (and uniformly distributed), for each generated point generate another uniform random value V in the range [0, maxDensity]. If V is <= the density described by your function then accept the point as a valid sample, otherwise reject it. –  locster Jan 13 '12 at 11:50

As Iocster said, you can use rejection sampling if you have an appropriate proposal density. Here is another approach that is a rather computationally intensive answer to the question that you can use for any density estimate, regardless of whether it was fit by maximum entropy:

If you have an estimated density, $\hat{f}$, you can get an estimated cumulative distribution function

$$\hat{F}(y) = \int_{-\infty}^{y} \hat{f}(x) dx$$

this integral can be estimated numerically using, for example, the integrate() function in R. Next, you can numerically estimate the inverse cumulative distribution function (i.e. the quantile function)

$$\hat{Q}(x) = \hat{F}^{-1}(x) = \inf \{ y : \hat{F}(y) = x \}$$

Assuming $\hat{F}$ is monotonically increasing, the intermediate value theorem applies, and $Q(x)$ can be calculate using any standard root finding algorithm. Once you have $\hat{Q}$, you can apply Inverse Transform Sampling, which says $\hat{Q}(U)$, where $U \sim {\rm Uniform}(0,1)$, is a draw from a distribution with CDF $\hat{F}$ (and therefore density $\hat{f}$).

-