Latin Hypercube Sampling Asymptotics

Question

I am trying to construct a proof for a problem I am working on and one of the assumptions that I am making is that the set of points I am sampling from is dense over the entire space. Practically, I am using Latin hypercube sampling to obtain my points over the entire sample space. What I would like to know is if Latin hypercube samples are dense over the entire space if you let your sample size tend to $\infty$? If so, a citation for this fact would be greatly appreciated.

Answer 1

Short answer: Yes, in a probabilistic way. It is possible to show that, given any distance $\epsilon>0$, any finite subset $\{x_1,…,x_m\}$ of the sample space and any prescribed ‘tolerance’ $\delta>0$, for suitably large sample sizes we can be sure that the probability that there is a sample point within a distance $\epsilon$ of $x_i$ is $>1-\delta$ for all $i=1,…,m$.

Long answer: I am not aware of any directly relevant citation (but see below). Most of the literature on Latin Hypercube Sampling (LHS) relates to its variance reduction properties. The other issue is, what does it mean to say that the sample size tends to $\infty$? For simple IID random sampling, a sample of size $n$ can be obtained from a sample of size $n-1$ by appending a further independent sample. For LHS I don't think you can do this as the number of samples is specified in advance as part of the procedure. So it appears that you would have to take a succession of independent LHS samples of size $1,2,3,...$.

There also needs to be some way of interpreting 'dense' in the limit as the sample size tends to $\infty$. Density does not seem to hold in a deterministic way for LHS e.g. in two dimensions, you could choose a sequence of LHS samples of size $1,2,3,...$ such that they all stick to the diagonal of $[0,1)^2$. So some kind of probabilistic definition seems necessary. Let, for every $n$, $X_n=(X_{n1},X_{n2},...,X_{nn})$ be a sample of size $n$ generated according to some stochastic mechanism. Assume that, for different $n$, these samples are independent. Then to define asymptotic density we might require that, for every $\epsilon>0$, and for every $x$ in the sample space (assumed to be $[0,1)^d$), we have $P(min_{1\leq k\leq n} \|X_{nk}-x\|\geq \epsilon)\to0$ (as $n\to \infty$).

If the sample $X_n$ is obtained by taking $n$ independent samples from the $U([0,1)^d)$ distribution ('IID random sampling') then $$P(min_{1\leq k\leq n} \|X_{nk}-x\|\geq \epsilon)=\prod_{k=1}^n P(\|X_{nk}-x\|\geq \epsilon)\leq (1-v_\epsilon 2^{-d})^n \to 0$$ where $v_\epsilon$ is the volume of the $d$-dimensional ball of radius $\epsilon$. So certainly IID random sampling is asymptotically dense.

Now consider the case that the samples $X_n$ are obtained by LHS. Theorem 10.1 in these notes states that the members of the sample $X_n$ are all distributed as $U([0,1)^d)$. However, the permutations used in the definition of LHS (although independent for different dimensions) induce some dependence between the members of the sample ($X_{nk}, k\leq n$), so it is less obvious that the asymptotic density property holds.

Fix $\epsilon\gt 0$ and $x\in [0,1)^d$. Define $P_n=P(min_{1\leq k\leq n} \|X_{nk}-x\|\geq \epsilon)$. We want to show that $P_n\to 0$. To do this, we can make use of Proposition 10.3 in those notes, which is a kind of Central Limit Theorem for Latin Hypercube Sampling. Define $f:[0,1]^d\to\mathbb{R}$ by $f(z)=1$ if $z$ is in the ball of radius $\epsilon$ around $x$, $f(z)=0$ otherwise. Then Proposition 10.3 tells us that $Y_n:=\sqrt n (\hat{\mu}_{LHS}-\mu)\xrightarrow{d} N(0,\Sigma)$ where $\mu=\int_{[0,1]^d} f(z) dz$ and $\hat{\mu}_{LHS}=\frac{1}{n}\sum_{i=1}^n f(X_{ni})$.

Take $L>0$. Eventually, for large enough $n$, we will have $-\sqrt n\mu\lt -L$. So eventually we will have $P_n=P(Y_n=-\sqrt n \mu)\le P(Y_n\lt -L)$. Therefore $\limsup P_n\le \limsup P(Y_n\lt -L)=\Phi(\frac{-L}{\sqrt\Sigma})$, where $\Phi$ is the standard normal cdf. Since $L$ was arbitrary, it follows that $P_n\to 0$ as required.

This proves asymptotic density (as defined above) for both iid random sampling and LHS. Informally, this means that given any $\epsilon$ and any $x$ in the sampling space, the probability that the sample gets to within $\epsilon$ of $x$ can be made as close to 1 as you please by choosing the sample size sufficiently large. It is easy to extend the concept of asymptotic density so as to apply to finite subsets of the sample space - by applying what we already know to each point in the finite subset. More formally, this means that we can show: for any $\epsilon>0$ and any finite subset $\{x_1,...,x_m\}$ of the sample space, $min_{1\leq j\leq m} P(min_{1\leq k\leq n} \|X_{nk}-x_j\|\lt \epsilon)\to 1$ (as $n\to\infty$).

Answer 2

I'm not sure if this is quite what you want, but here goes.

You're LHS-sampling $n$ points from $[0,1)^d$, say. We'll argue very informally that, for any $\epsilon>0$, the expected number of empty (hyper)cuboids of size $\epsilon$ in each dimension goes to zero as $n\to\infty$.

Let $m=\lceil 2/\epsilon \rceil$ so that if we divide $[0,1)^d$ uniformly into $m^d$ tiny cuboids -- microcuboids, say -- of width $1/m$ then every width-$\epsilon$ cuboid contains at least one microcuboid. So if we can show that the expected number of unsampled microcuboids is zero, in the limit as $n\to\infty$, then we're done. (Note that our microcuboids are arranged on a regular grid, but the $\epsilon$-cuboids can be in any position.)

The chance of completely missing a given microcuboid with the first sample point is $1-m^{-d}$, independent of $n$, as the first set of $d$ sample coordinates (first sample point) can be chosen freely. Given that the first few sample points have all missed that microcuboid, subsequent sample points will find it harder to miss (on average), so the chance of all $n$ points missing it is less than $(1-m^{-d})^n$.

There are $m^d$ microcuboids in $[0,1)^d$, so the expected number that are missed is bounded above by $m^d(1-m^{-d})^n$ -- because expectations add -- which is zero in the limit as $n\to\infty$.

---

Updates ...

(1) Here's a picture showing how, for given $\epsilon$, you can pick $m$ large enough so that an $m\times m$ grid of "microcuboids" (squares in this 2-dimensional illustration) is guaranteed to have at least one microcuboid within any $\epsilon\times\epsilon$ sized region. I've shown two "randomly"-chosen $\epsilon\times\epsilon$ regions and have coloured-in purple the two microcuboids that they contain.

(2) Consider any particular microcuboid. It has volume $(1/m)^d$, a fraction $m^{-d}$ of the whole space. So the first LHS sample -- which is the only one chosen completely freely -- will miss it with probability $1-m^{-d}$. The only important fact is that this is a fixed value (we'll let $n\to\infty$, but keep $m$ constant) that's less than $1$.

(3) Now think about the number of sample points $n>m$. I've illustrated $n=6m$ in the picture. LHS works in a fine mesh of these super-tiny $n^{-1}\times n^{-1}$ sized "nanocuboids" (if you will), not the larger $m^{-1}\times m^{-1}$ sized "microcuboids", but actually that's not important in the proof. The proof only needs the slightly hand-waving statement that it gets gradually harder, on average, to keep missing a given microcuboid as you throw down more points. So it was a probability of $1-m^{-d}$ for the first LHS point missing, but less than $(1-m^{-d})^n$ for all $n$ of them missing: that's zero in the limit as $n\to\infty$.

(4) All these epsilons are fine for a proof but aren't great for your intuition. So here are a couple of pictures illustrating $n=10$ and $n=50$ sample points, with the largest empty rectangular area highlighted. (The grid is the LHS sampling grid -- the "nanocuboids" referred to earlier.) It should be "obvious" (in some vague intuitive sense) that the largest empty area will shrink to arbitrarily small size as the number of sample points $n\to\infty$.