11
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Yes, assuming a continuous distribution, because for any $\epsilon>0$ you can set the number of divisions to be such that all per-variable intervals have width $<\epsilon/2$. Thus at least one hyperinterval (i.e. sample volume) is strictly contained by a width $\epsilon$ hypercube around any point you choose. (Comment, not Answer, as all I know about LHS comes from Wikipedia as of ten minutes ago ...) $\endgroup$ – Creosote Nov 10 '15 at 23:19
  • $\begingroup$ This is true, but I don't think it can easily be used to show denseness of large Latin Hypercube samples. The reason for this is that the sampled points in LHS are not independent: the existence of a sample point inside a specific hyperinterval precludes any other sample points from appearing in the same row/column (or whatever the multi-dimensional term is for this). $\endgroup$ – S. Catterall Reinstate Monica Nov 19 '15 at 23:10
  • $\begingroup$ @Creosote do you think you could formalize your answer more? $\endgroup$ – user95564 Nov 22 '15 at 0:24
  • $\begingroup$ @RustyStatistician, please expand your opening post to explain, in a formal manner as required by your proof, what you mean by "the set of points I am sampling from is dense over the entire space". Thanks. $\endgroup$ – Creosote Nov 22 '15 at 8:23
  • $\begingroup$ If I take an initial Latin Hypercube Sample where $n$ is so large, we consider it to be inifinty, is that sample dense?' $\endgroup$ – user95564 Nov 22 '15 at 8:49
6
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ I have two questions: 1) If you just have sample of size $n$ where $n$ is large, does that change the argument? And 2) Latin hypercubes samples can be on any range of values (not necessarily just (0,1)) so does that also change teh answer? $\endgroup$ – user95564 Nov 19 '15 at 6:22
  • $\begingroup$ Also, would you be willing to explain why for large enough $n$, we will have $-\sqrt{n}\mu$? I assume that means that for large $n$, $\hat\mu_{LHS}$ goes to zero, because in distribution it is a $N(0,\Sigma)$? $\endgroup$ – user95564 Nov 19 '15 at 6:37
  • $\begingroup$ @RustyStatistician Everything is defined in terms of finite samples i.e. $n\lt\infty$ but large. I've added some additional explanation at the end to explain what's happening. Other ranges of values can easily be accommodated ((0,1) is not special), so long as the volume of the sample space is finite. $\endgroup$ – S. Catterall Reinstate Monica Nov 19 '15 at 22:22
  • $\begingroup$ Can you elaborate on your short answer? $\endgroup$ – user95564 Nov 20 '15 at 21:50
  • $\begingroup$ @RustyStatistician The short answer is an informal summary of my long answer which, I think you'll agree, is already quite elaborate! So , as suggested above, it would be good if you could rewrite your question in more formal terms so that I know whether my attempted answer is on the right track (in terms of answering your intended question) or not. $\endgroup$ – S. Catterall Reinstate Monica Nov 22 '15 at 9:10
3
+350
$\begingroup$

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.

enter image description here

(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$.

enter image description here

$\endgroup$
  • $\begingroup$ Does this argument hold for any general interval? Instead of $[0,1)$? $\endgroup$ – user95564 Nov 25 '15 at 0:11
  • $\begingroup$ Yes, for any finite dimensions. It should be clearer now that I've fixed the proof. $\endgroup$ – Creosote Nov 25 '15 at 7:59
  • $\begingroup$ is it possible to give a 1-d or even 2-d picture of this proof? I am pretty lost in it. $\endgroup$ – user95564 Dec 2 '15 at 0:10
  • $\begingroup$ Done. Happy to take further questions if need be. $\endgroup$ – Creosote Dec 2 '15 at 23:19
  • $\begingroup$ Awesome thanks! That definitely does help now with the intuition. $\endgroup$ – user95564 Dec 2 '15 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy