Re: Sampling from arbitrary probability distribution

Just d' FAQs wrote: 
Shaobo Hou wrote:

I need to sample lots of points from an arbitrary probability distribution but I would like to sample more points from area of high probability, like using monte carlo method for sampling illuminations for rendering purpose.

I can compute the probability (or something similar to the true probabiility) at any point in the space but I am not sure what sort algorithm I should use. 


If we can write down an expression for the distribution, and if that
expression is, invertible, then we can create that distribution by
functional transformation of a uniform distribution. With empirical
distributions, which seem more likely here, it's more difficult.


Well, actually you must have the INTEGRATED (cumulative) probability
distribution, then its functional inversion gives you the transformation
from a uniform distribution to any.

But if your prob. distr. is lousy, don't despair. You can do it
numerically, choose your precision/number of sampling bins, then
sample the distribution, then compute its integral by incremental
summing, and then "invert" the function by scanning your array.
(Details if you wish, privately). This is not so superb algorithm,
since its complexity - for ONE generated number - is proportional
to the number of sampling bins, but it is precise, and simple to
implement. Even if you don't have any mathematical function, but
just an experimental distribution (obviously already discretized).

Another trick, *very* often used if your distribution is finite
within a finite interval: use the rejection method. Map the
distribution (not integrated) into a unit square; it will be
a functional profile inside. Choose uniformly a random point on
the x axis, and then choose another point between 0 and 1,
also uniformly. If the point falls under the prob. distr. curve,
then accept it, otherwise reject.

If the distribution varies wildly, the efficiency of the method
becomes bad, but there are ways, such as antithetic variables, etc.,
which permit to optimize it.


Jerzy Karczmarczuk
.

Relevant Pages

  • Re: HUP Fails Via Nonexistent Distributions 2: The Uniform Claim
    ... > Max Jammer's The Philosophy of Quantum Mechanics, Wiley: ... Also, the probability that q is in [L1, ... > The uniform probability distribution in mathematical ... the graph of a uniform distribution is a horizontal line ...
    (sci.physics)
  • HUP Fails Via Nonexistent Distributions 2: The Uniform Claim
    ... Max Jammer's The Philosophy of Quantum Mechanics, Wiley: ... Also, the probability that q is in [L1, ... The uniform probability distribution in mathematical ... the graph of a uniform distribution is a horizontal line ...
    (sci.physics)
  • Re: Pigeons, People, and Priors
    ... the variance of the probability generator go to zero you have a continuum ... a random-interval 60 s schedule is not. ... The Exponential Distribution ... I probably should have used the phrase "statistical learning theory" rather ...
    (comp.ai.philosophy)
  • Re: So called "stimulus/response" models
    ... Instead of answering to each misunderstood, ironic and out of context ... Sorry, you exhibit a simplistic view of probability theory, and an even more ... of acquiring the consequences of responses. ... distribution over consequences of a given act. ...
    (comp.ai.philosophy)
  • Re: behavior as mapping
    ... estimating a probability distribution, the distribution ... sequence with equal probability - since you have microsecond temporal ... reduction of the entropy Pto the entropy P ... If there were 4 genes we would need 2 bits of binding site info. ...
    (comp.ai.philosophy)