We now consider the generation of new data by sampling a probability distribution whose density is known. Sampling a probability distribution can be achieved with a deterministic but chaotic dynamical system, whose probability distribution is an invariant measure. This dynamical system must explore the entire state space supporting the probability distribution with an ergodic transformation. Birkhoff's theorem shows that the iteration of an ergodic transformation defines such a dynamical system with a unique invariant measure. Examples of such dynamical systems are given for a uniform distribution.
In one dimension, any probability distribution can be calculated by a change of variable from a uniform distribution, which depends on the distribution function. In several dimensions, any probability density can be sampled from another distribution with wider support, using a random sample acceptance/rejection algorithm. However, this algorithm becomes ineffective in high dimensions, due to the curse of high dimensionality. Importance sampling is another approach to Monte-Carlo integral calculation, replacing the sampling of one probability distribution by the sampling of another, easier-to-calculate distribution, with a weighting that depends on the ratio between the two probability densities.
