0
$\begingroup$

For an arbitrary probability space $(X,\mu)$, a sequence $(x_n)$ in $X$ is said to be equidistributed with respect to $\mu$ if the measures $\frac 1 n \sum_{1\le k\le n} \delta_{x_k}$ converges weakly to $\mu$ as $n \to \infty$.

The special case of a compact interval equipped with the Lebesgue measure is very well studied. One way of building equidistributed sequences is to construct an ergodic transformation preserving the measure. This post sketches such a construction for the Lebesgue measure on the real line.

Is there any known explicit construction of an equidistributed sequence for the measure associated to an exponential or Gaussian random variable, preferably that doesn’t involve applying the cumulative distribution function/its inverse?

$\endgroup$
0

2 Answers 2

1
$\begingroup$

Weak convergence of measures is preserved under continuous transformations: if a sequence of Borel measures $\mu_n$ converges to a Borel measure $\mu$ weakly and if $\psi$ is a continuous transformation of the appropriate topological spaces, then the sequence of the pushforward measures $\mu_n\psi^{-1}$ will converge to the pushforward measure $\mu\psi^{-1}$ weakly.

Therefore, the problem immediately reduces to transforming the uniform distribution on the interval $(0,1)$ or on the unit square $(0,1)^2$ (say) continuously to an exponential or Gaussian distribution.

So, if a sequence $(x_n)$ is equidistributed with respect to the uniform distribution on the interval $(0,1)$, then the sequence $(-\ln x_n)$ will be equidistributed with respect to the exponential distribution with mean $1$ -- because the continuous map $(0,1)\ni x\mapsto\psi(x):=-\ln x\in\mathbb R$ transforms the uniform distribution on the interval $(0,1)$ into the exponential distribution.

Similarly, if a sequence $((x_n,y_n))$ is equidistributed with respect to the uniform distribution on the unit square $(0,1)^2$, then the sequence $(\sqrt{-2\ln x_n}\cos(2\pi y_n))$ will be equidistributed with respect to the standard normal distribution, in view of the Box–Muller transform.

$\endgroup$
4
  • $\begingroup$ Thank you very much for your answer. I was aware of inverse sampling and Box Muller transforms, I was more wondering if there was any natural ergodic invariant transform associated to those measures, that somehow would be simpler than going back to the unit interval (it doesn’t matter from a mathematical standpoint, but it does from a computational point of view). $\endgroup$
    – Tartrate
    Commented Dec 21, 2020 at 16:02
  • $\begingroup$ @Tartrate : Your question "Is there any known explicit construction of an equidistributed sequence for the measure associated to an exponential or Gaussian random variable, preferably that doesn’t involve applying the cumulative distribution function/its inverse?" did not mention "any natural ergodic invariant transform" or "computational point of view". If you want to impose these additional conditions, it is better to post them separately. $\endgroup$ Commented Dec 21, 2020 at 19:41
  • $\begingroup$ As regards Gaussian variables, in computational terms one fast way to simulate these variables is through rejection sampling, e. g. the ziggurat algorithm. Drawing a point uniformly in the ziggurat can be deduced fairly quickly from drawing one point uniformly in $[0, 1]^2$ by applying a piecewise-linear function which will preserve equidistribution. And the rejection step will preserve equidistribution too. This should give you a computationally rather quick way to obtain an equidistributed sequence for the Gaussian law. $\endgroup$ Commented Dec 22, 2020 at 3:02
  • $\begingroup$ @RémiPeyre : That's right, I actually forgot about the rejection method. However, instead of a piecewise linear function it may be better to use the exponential density. I am not sure, though, if any of that would be much faster than Box--Muller, since the values of the elementary functions can be computed very fast. Actually, when working on the answer, I did not see any reason to think about computational aspects, given how the question was stated. $\endgroup$ Commented Dec 22, 2020 at 12:38
0
$\begingroup$

Denote by $\Phi(x)$ the cumulative distribution function of $\Gamma$, the standard normal distribution. More explicitly, $$ \Phi(x)=\int_{-\infty}^x \Gamma[dt]:=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^x e^{-t^2/2} dt. $$

$\newcommand{\bR}{\mathbb{R}}$ It defines a homeomorphisms $\Phi:\bR\to (0,1)$. Its inverse $Q=\Phi^{-1}$ is the so called quantile function of $\Gamma$. If $\mu$ is the uniform distribution on $[0,1]$, then $Q_\#\mu$, the push forward of $\mu$ is the normal distribution. The push forward is defined as in Iosif Pinelis' answer,

$$Q_\#\mu[S]= \mu\big[ Q^{-1}(S)\big],$$

for any Borel subset $S\subset \bR$.

Take an ergodic transformation of $T$ of the $\big((0,1),\mu\big)$. Then $Q\circ T \circ \Phi$ is an ergodic transformation of $(\bR,\Gamma)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.