# Connection between uniform distribution on a set and uniform sampling from a set - intuitive pictures and necessary mathematical formulas

What's the connection between uniform distribution and uniform sampling from a set $$S$$? Are these two terms synonymous: "uniform sampling from a set" and "sampling from a set according to a uniform distribution"?

A uniform sample can be random, right? I mean one can choose $$n$$ iid variables each one uniformly distributed on the set.

I know for uniform distribution, the PMF or PDF is constant, so each value is equally probable in discrete cases, but I'm having trouble connecting it with the uniform sampling. To be more explicit, assume that $$S:=[0,1] \times [0,1] \subset \mathbb{R}^2.$$ Say we'd like to sample $$S$$ uniformly, $$n$$ times. To me this means: we're taking values given by $$n$$ number of iid uniform random variables $$\{X_1\dots X_n\} \in S$$, and plot these values on the square $$S.$$ Now the intuitive picture I see everywhere is that $$S$$ is broken into a uniform grid of smaller squares to plot these values, and the samples belongs to the vertices of these squares. This is where I'm having trouble: (assume that the samples are iid random sample, but if not, please provide some argument)

1) Why do the samples have to appear in such a regular pattern: situated at the vertices of these smaller squares forming the grid?

2) Is it true that as we let $$n,$$ the number of points from $$S$$ sampled according to a uniform distribution on $$S$$ go to infinity, the distances between neighboring samples must go to zero? Why? Let's put it mathematically. Let $$\{X_1 \dots X_n\}, X_i \sim_{iid} Unif(S=[0,1]\times [0,1]).$$ Then, for each $$i,$$ must $$min_{1 \le j \le n, j \ne i} ||X_i - X_j|| \to_{p} 0$$ in probability as $$n \to \infty?$$ (the minimum here corresponds to "neighboring" distance). Alternately, the samples might have just one accumulation point, so that the neighboring distances don't $$\to 0.$$

3) (Continuation of question 2) If we select $$n$$ points on $$S$$ non-uniformly, say according to a $$\mathcal{N}(0, I)$$ distribution instead, how will the sampled points on $$S$$ look like? Must the neighboring distances $$\to 0,$$ i.e. for each $$i,$$ must $$min_{1 \le j \le n} ||X_i - X_j|| \to_{p} 0$$ in probability as $$n \to \infty?$$

REFERENCE: For the reference, please see : https://arxiv.org/pdf/1305.7255.pdf, e;g. in sec 2.5, ". We illustrate this with the well-known example of the “Swiss-roll with a hole” (Figure 1), a two dimensional strip with a rectangular hole, rolled up in three dimensions, sampled uniformly. " Or in the section before (same page): "for a **uniform sampling density on $$\mathcal{M}.$$"** In sec 5.1, " where the sampling density $$\pi$$ is not uniform on $$\mathcal{M}$$". Not sure what sampling density is, is it the pdf of the random variable?

There are many (interrelated) questions here and not enough space to pursue all their implications. Let's therefore focus on a central idea, which I wish to state rigorously and generally, so I will begin with some definitions that cover the examples in the question (and much more).

First, we need to capture the idea of a "distribution" in some interval like $$[0,1]\subset \mathbb R$$ or a ball in $$\mathbb{R}^n$$ or even a finite set like $$\{1,2,\ldots,n\}.$$ We need to relate this to some kind of distance on these sets and we will need to focus attention on small neighborhoods of points within these sets. Here's my attempt, which generalizes the usual concept of a real-valued random variable:

Let $$(S,\mathfrak{F},\mathbb P)$$ be a probability space and $$(T,\delta)$$ a metric space. When $$X:S\to T$$ is a random variable, let us say that $$t\in T$$ is a support point of $$X$$ when there is positive probability that $$X$$ lies in any non-trivial closed ball around $$t:$$ that is, for any number $$\rho \gt 0,$$ $$\mathbb{P}(\delta(X,t) \le \rho) \gt 0.$$ "The" support of $$X$$ is the union of all its support points.

Next, we need to create a framework to describe a sampling process that can become arbitrarily large. This is standard, but I will take the opportunity to count random points within neighborhoods in $$T:$$

Suppose $$(X_i),$$ $$i=1,2,3,\ldots,$$ is a sequence of iid $$T$$-valued variables on $$S.$$ For any $$t\in T,$$ $$\rho \gt 0,$$ and integer $$n,$$ let $$N_n(t,\rho)$$ count how many of the first $$n$$ of the $$X_i$$ lie within distance $$\rho$$ of $$t.$$ For a given $$t$$ and $$\rho,$$ the sequence $$N_1(t,\rho), N_2(t,\rho),\ldots$$ is a sequence of integer-valued random variables on $$S.$$

Let's call such an iid sequence a "sampling process."

These simple definitions are enough to prove a far-reaching claim:

Claim: the sequence $$N_i(t,\rho)$$ almost surely diverges.

Before proving this claim, let's apply it to the questions.

1. There doesn't have to a any "regular pattern." Indeed, there's nothing in the general definitions and analysis that can be used even to define or characterize a "pattern."

2. When $$T$$ is the unit interval $$[0,1]\subset\mathbb R,$$ and $$\delta$$ is the usual distance ($$\delta(x,y) = |y-x|$$), the claim implies distances between neighboring samples must go to zero. For if not, let $$t$$ lie in one of the gaps and let $$\rho$$ be less than the distance from $$t$$ to the nearest sample points. The claim shows this can't happen because eventually there will be a large number of sample points within distance $$\rho$$ of $$t.$$

3. When $$T$$ is $$\mathbb R$$ with its usual distance and $$X$$ has a Normal distribution, it's easy to show the support of $$X$$ is $$\mathbb R.$$ (Proof: the chance that $$X$$ lies within $$\rho$$ of $$t\in\mathbb R$$ is the integral over the interval $$[t-\rho,t+\rho]$$ of a strictly positive continuous density function. That function therefore attains a strictly positive minimum value, say $$q,$$ on the interval, whence the probability is at least $$2\rho q,$$ which is nonzero.)

The same analysis as $$(2)$$ proves that around any number $$t$$ eventually there will be an arbitrarily large number of sample points close to $$t.$$ (What it does not reveal, though, is that when $$t$$ is far from the mean of $$X,$$ the sample size need to be astronomically large before a cluster of sample points is likely to appear near $$t.$$)

### Proof of the claim.

The claim is proven if we can show that for any integer $$M$$ and real number $$\epsilon \gt 0,$$ the chance that all the $$N_i(t,\rho)$$ in this sequence are bounded by $$M$$ is no greater than $$\epsilon.$$

Let's do some preliminary analysis before addressing this issue.

Because $$t$$ is in the support of each $$X_i,$$ the number $$q = \mathbb{P}(\delta(X,t)\le \rho)$$ is nonzero. Define the random variables $$I_i(t,\rho)$$ to be the indicators of this event: $$I_i(t,\rho) = \left\{\matrix{1 & \text{if } \delta(X_i,t)\le \rho \\ 0 & \text{otherwise.}}\right.$$

Because the $$I_i(t,\rho)$$ are functions of the independent variables $$X_i,$$ the $$I_i(t,\rho)$$ are independent; and because the $$X_i$$ are identically distributed, so are the $$I_i(t,\rho) .$$ The common distribution of the $$I_i(t,\rho)$$ is Bernoulli$$(q),$$ as we have already computed. Since $$N_n(t,\rho) = \sum_{i=1}^n I_i(t,\rho),$$ the variable $$N_n(t,\rho)$$ has a Binomial$$(n,q)$$ distribution. Its expectation is $$nq,$$ its variance is $$nq(1-q),$$ and Chebyshev's inequality asserts that for any $$\kappa \ge 1,$$

$$\mathbb{P}\left(|N_n(t,\rho) - nq| \ge \kappa \sqrt{nq(1-q)}\right) \le \frac{1}{\kappa^2}.\tag{1}$$

Return, now, to arbitrary $$M$$ and $$\epsilon.$$ By choosing any $$n$$ so large that

$$n \gt \frac{1}{q}\left(2M + \frac{1-q}{\epsilon} + \frac{M^2}{q}\right),$$

we deduce

$$nq(1-q) \le (M-nq)^2\epsilon.$$

In these terms, the inequality $$(1)$$ can be rewritten

$$\mathbb{P}\left(N_n(t,\rho)\le M\right) \le \epsilon.$$

Although this applies only to any sufficiently large $$n,$$ it is enough for the proof, because the sequence $$N_i(t,\rho)$$ has independent increments. This means (among other things) that for integral $$a\ge 1,$$ $$N_{an}(t,\rho)$$ is the sum of $$a$$ iid variables having the same distribution as $$N_n(t,\rho):$$ namely, the count of the first $$n$$ of the $$X_i$$ plus the count of the next $$n$$ of the $$X_i$$ plus etc. The chance that $$N_{an}(t,\rho)$$ does not exceed $$M$$ exceeds the chance that all $$a$$ of these variables do not exceed $$M,$$ which (by independence) equals $$(1-\epsilon)^a.$$ The limit of this value, as $$a$$ grows large, is zero. Consequently, it is almost certain that at least one of these variables exceeds $$M.$$ But then all subsequent values of the $$N_i(t,\rho),$$ which can never be any less than the preceding counts, must all exceed $$M,$$ too.

We have shown that no matter what $$t\in T$$ and $$\rho\gt 0$$ may be, there is zero chance that only finitely many of the $$X_i$$ are within distance $$\rho$$ of $$t,$$ QED.

In this rigorous sense we have the right to say

Every support point of a random variable $$X$$ is an accumulation point of the sampling process of $$X.$$

• whuber: thanks very much for taking the time to write this detailed answer. I've already upvoted, but will take the time to sit down and study your answer in great detail, from which I'm sure I've lots to learn. Should I've questions, I'll write them here, thanks again! – Mathmath May 14 '20 at 14:57
• Hello and thanks again, I think I understood your argument, just summarizing it here - so each support point $t$ and each ball $B(t, \rho),$ you expressed the number of sample points in that ball as the sum of the (random) indicator functions of that ball, and the random indicator functions being Bernoulli, their sum, the number of sample points in the ball is Binomial, and then you used the concentration (Chebyshev's ineq.) of the Bernoulli variables around its mean to arrive at the fact that as the sample size grows, the sample points also grows with probability 1. (contd.) – Mathmath May 15 '20 at 23:17
• And I understood that these chain of arguments imply that around support points, the number of sample points diverges to infinity with prob 1. But then a follow up question will be: what're all the support points of a given random variable? For real-valued normal distribution, it's the whole real line. It seems true that for every point where the PDF (even for random vectors or metric space valued random variables), the supports points are those where the PDF is strictly positive (the alternate definition is here - statlect.com/glossary/support-of-a-random-variable), and (contd) – Mathmath May 15 '20 at 23:22
• (contd) and it seems these definitions should be equivalent. One side is trivial, namely if the PDF is strictly positive at $t \in T,$ then $t$ is clearly a support point according to your definition. On the other hand, if $t$ is s.t. every ball around it has a +ve prob. of containing $X,$ then the derivative can still go to zero it seems. (I'll think about this issue...) But this implies at all points $t \in T$ where $f_X(t) > 0, t$ is a support point (your definition); e.g. for uniform distn on $[0,1]^2,$ every point is a support pt(your definition), as the pdf $> 0.$. Your opinion welcome. – Mathmath May 15 '20 at 23:32
• Even the trivial implication is incorrect. The problem is that a PDF is never well-defined: it can be modified arbitrarily on any set of measure zero. Thus, a point $t$ is a support point of a real-valued distribution $F$ whenever (according to my definition) for all $\rho\gt 0,$ $F(t+\rho)-G(t-\rho)\gt 0$ where $G(x)$ is defined to be the limit of $F(x)$ from below. This expression is the probability of the closed interval $[t-\rho,t+\rho].$ It's best to think in terms of $F$ rather than a PDF. After all, when $F$ is discrete it doesn't even have a PDF. – whuber May 16 '20 at 21:35

Unless this is a reserved term in some domains, uniform sampling means [for me] sampling from the Uniform distribution. Here is the outcome from an iid Uniform sample of size 1000 over the unit square:

As clear from the above, the simulated points are irregularly located over that square. However, by simple virtue of the law of large numbers, the coverage of any subset of the unit square by the sample will converge to the surface of this subset.

• Actually, anyone reading my Science Direct source quickly realizes that the opinion presented above does not represent the topic of 'uniform sampling' as presented in the academic literature. – AJKOER May 13 '20 at 21:40
• This source, per my answer, from Science Direct, at sciencedirect.com/topics/computer-science/uniform-sampling outlines the field of Uniform Sampling as currently presented in the academic literature. It differs in content from the above comment and also its relationship to material classically covered in, for example, my Sampling Theory course. – AJKOER May 13 '20 at 21:47
• Xi'an: thank you again for your answer and the picture. I'm not sure I understand "the coverage of any subset of the unit square by the sample will converge to the surface of this subset" and the use of the term "law of large numbers" in my question. I'm familiar with the weak and strong laws of large numbers, but I'm not sure how those imply why each neighboring distance must go to zero as we take more and more points? FYI: I modified question 2, so that'd put things more rigorously. However, your simulation is helpful. Could you simulate similarly from Normal and some other distributions? – Mathmath May 14 '20 at 13:41
• The intuition is that any subset with positive measure will see an accumulation of points as the sample size grow. W. Huber's terrific answer makes this intuition more rigorous. – Xi'an May 15 '20 at 11:51

Per a source, to quote:

If a sample is selected from a population which has been grouped into strata, in such a way that the number of units selected from each stratum is proportional to the total number of units in that stratum, the sample is said to have been selected with a uniform sampling fraction.

Related concept is proportionate stratified sample, defined here, to quote:

Proportionate stratified sample is a version of a sampling method call stratified sample. If certain characteristics of population influence phenomenon that is being explored then these characteristics can be used for stratification purposes. That means that population as well as sample will be divided into subpopulation / subsamples described by stratification variables. Typical examples of stratified samples used in market and social research is stratification by region and urbanity level. Key assumptions are that stratification variables correlate with 'dependent' variables and that they help maximise homogeneity within strata and maximise variance across strata. After stratification drawing of sampling units is independent across strata.

And further:

Proportionate stratified sample means that size of sample strata is proportional to the size of population strata; in other words, probability of unit being selected from the stratum is proportional to relative size of that stratum in population.

The topic has been applied in many applications including signal processing and further involves finer points. To quote from Science Direct [EDIT] which comments directly on 'Uniform Sampling' [END EDIT], an example detailing a scheme applied to the parent population:

...sampled independently and uniformly from {1, …, n}×{1, …, n} with replacement. Then with high probability the sequence of iterates generated by (19) with a proper stepsize and the initial guess constructed by (25) converges linearly to a global minimizer,,,,

So, there can be much more implied in a uniform sampling scheme than simple random sampling (occurring here with replacement) per a uniform distribution. These include initial guesses likely to assess variation of important criteria of interest which further drives sampling size, sampling steps or systematic sampling procedures with an intent to achieve a convergence on an attribute of interest based on a metric.

• -1 This answer misses the point of the question, which clearly concerns uniform sampling from an interval rather than a discrete set. See the sentence beginning "to be more explicit." – whuber May 14 '20 at 13:08
• @whuber yes an interval or a product of intervals, and more generally, an open subset of $\mathbb{R}^n,$ e.g. an open ball of the form $\{x: ||x|| < 1\}$ – Mathmath May 14 '20 at 13:10