Perfect sampling and inverse transform sampling

Question

Firstly, looking at the discussion https://math.stackexchange.com/questions/241315/three-ideas-of-perfect-sampling, the term "perfect sampling" does not seem adequate, since there are several aspects that don't sound perfect at all. The sampling becomes perfect from some point in the chain, but establishing a criteria may use different approaches. I don't know if you agree, but, isn't Perfect sampling achieved only through the Inverse transform sampling?

Another and most important question concerns the Inverse transform sampling (ITS). Let $X\sim F(x)$, where $F(x)$ is the cdf of $X$. According to the ITS, we have that $U=F(x)\sim \operatorname{Unif}(0,1)$, then we sample $u$ from $\operatorname{Unif}(0,1)$ and obtain sampled value $x$ of $X$ from $x=F^{-1}(u)$. Although this look more "perfect" to me, we have a problem, that an expression for the inverse of $F$ mostly is not available, that is why we have all the approximated methods.

So, I was wondering, what is wrong with the following strategy?

Suppose that $F^{-1}(x)$ is not available, but evaluating $F(x)$ is (computationally) easy, so I could set a range $a<x_1<x_2<...x_n<b$ where $[a,b]\subset \mathbb{R}$, the number of points $n$ is chosen suitably, then by computing $u_1=F(x_1),...,u_n=F(x_n)$, we have table of values from which we can draw $x_i$ promptly by drawing $u_i\sim Unif(0,1)$. If we choose a large number of $x_i$ within the range, can we get a very good random number generator?

A problem is when $X$ is defined in ranges such as $(-\infty,\infty)$ and $(0,\infty)$, because we can't be sure of what range to sample from.

Has anybody came across with some similar algorithm?

I hope to have passed the main idea, sorry, I was not formal because I would like to hear from your experiences. I would appreciate any comments. thanks in advance.

Answer 1

Perfect sampling is now called exact sampling and it is indeed exact, when compared with a standard MCMC algorithm that is only asymptotically exact (in the number of simulations). An exact sampling algorithm comes with a stopping rule that guarantees that the final value is simulated from the target distribution. Although it may require a longer execution time than an inverse cdf method, a known transform of a simpler distribution (e.g., a Negative Binomial being the mixture of a Poisson distribution by a Gamma distribution), an accept-reject or a ratio-of-uniform algorithm, it identically operates as a function that returns one or $n$ simulations when provided with a seed.

Concerning the grid inversion method suggested in the question, this is an approximation of an exact inversion, with cost increasing with the requested precision. In addition, it does not extend to larger dimensions.

Remark 1 The compactness restriction is not a major issue. First, the random variable $X$ to be simulated can be transformed by an arbitrary function $H$ so that $H(x)\in(0,1)$ for all realisations $x$ of $X$. Second, the bounds $a$ and $b$ can be chosen so that $\mathbb P(X\in(a,b))$ is (at least) equal to a predefined probability like $0.99$ or $0.9999$.

Remark 2 There exist other "perfect" sampling strategies, including accept-reject, ratio-of-uniform algorithms.