# Sequential random sampling

This question is from Rice's Mathematical Statistics and Data Analysis. (I'm not a student, so you don't need to worry about helping me "cheat" by answering this!) Suppose you have a population of $$N$$ elements which are ordered, and you want to sample $$n$$ elements. You want to select the elements sequentially in the same order that the population is sorted in. You select element $$i$$ with probability $$\frac{n - n_i}{N - i + 1},$$ where $$n_i$$ are the number of elements already selected before element $$i$$. Show that any possible sample occurs with probability $$\frac{1}{{N \choose n}}.$$ Intuitively, this makes perfect sense to me, since at each step the likelihood you pick an element is the number of needed samples remaining divided by the number of population members remaining. When I try and prove this formally however, my attempts have all failed, because I end up with convoluted constructs like sums with terms like $$1 / {N - i \choose n -i}$$, and I get stuck not knowing how to proceed. All my attempts so far have been various flavors of induction proofs.

EDIT: While I haven't been able to prove this, I have been able to validate this numerically. Here's the Julia code I used:

using Combinatorics

function likelihood(sample::Vector{Bool})::Float64
N = length(sample)
n = sum(sample)
ni = 0
l = 1.0
for (i, s) ∈ enumerate(sample)
if s
l *= (n - ni) / (N - i + 1)
ni += 1
else
l *= 1.0 - (n - ni) / (N - i + 1)
end
end
l
end

function relativediff(a::Float64, b::Float64)::Float64
abs(a - b) / b
end

function biggestdiff(N::Int64, n::Int64)::Float64
biggest = 0.0
expectedlikelihood = 1.0 / binomial(N, n)
for indices ∈ combinations(1:N, n)
sample = repeat([false], N)
for i ∈ indices
sample[i] = true
end
l = likelihood(sample)
diff = relativediff(l, expectedlikelihood)
biggest = max(biggest, diff)
end
biggest
end


The biggestdiff function iterates over all combinations of length $$n$$ samples from a collection $$N$$ elements selected. For each sample, it compares the probability that sample would have been generated sequentially from the rule above, against the expected probability $$1/{N \choose n}$$. It returns the maximum relative difference of all sample, which should be very close to zero. (It might not equal zero because of numerical imprecision.)

Running this for several values of $$N$$ and $$n$$ suggests this is true, and I just haven't been able to prove this formally:

biggestdiff(1, 1)    # 0.0
biggestdiff(5, 3)    # 1.3877787807814457e-16
biggestdiff(50, 4)   # 1.3655018142686574e-15

• I would translate the hypergeometric distribution p.m.f. into these parameters as asserting that the probability that $n_i$ elements have been selected after considering the first $i-1$ elements is $\frac{\binom{n}{n_i} \binom{N - n}{i-1-n_i}}{\binom{N}{i-1}}$ and that, conditioned on $n_i$ elements having been selected, each of the $\binom{i-1}{n_i}$ ways they could have been selected was equally likely so with conditional probability $\frac{1}{\binom{i-1}{n_i}}$. You need to prove these assertions and then show your initial claim (the latter by considering $i=N+1$ and $n_{N+1}=n$). Commented Jan 22 at 9:05
• This is the special case of equal weights in weighted sampling without replacement: see stats.stackexchange.com/a/20592/919. But there's an extremely simple proof: because this procedure assigns the same inclusion probabilities to any sequence (the sampling is uniform at each step), QED.
– whuber
Commented Jan 22 at 13:54
• Thanks Henry. That's similar the approach I was taking. I got stuck working through the algebra on the combinations. Commented Jan 23 at 1:28
• Thanks whuber: The "simple proof" you suggest is the outline of what I've been trying. Where I'm stuck is proving that each item actually has equal probability of selection. It's intuitively obvious to me; I'm just stuck on showing it formally. Commented Jan 23 at 1:32
• There's an ambiguity in the problem statement that might be causing difficulty. "Element $i$" must refer to the $i^\text{th}$ element that is selected in this procedure, not the one in position $i$ in the original sequence. (The latter interpretation would not give correct samples of size $n=1.$) The rule can be restated, "select one element uniformly at random from the sequence and remove it. Repeat the procedure with the remaining $N-1$ elements until the desired sample size $n$ is attained."
– whuber
Commented Jan 23 at 15:03

I finally figured this out. Given $$n$$ and $$N$$, let $$\Omega = \left\{ s \in [0, 1]^N \mathrel{}\middle|\mathrel{} \sum_{i=1}^N s_i = n\right\}$$ be the sample space. An outcome like $$s = (0, 1, 1, 0, 0)$$, for $$n = 2$$, $$N = 5$$, has value $$1$$ for the selected items ($$2$$ and $$3$$ in this case), and value $$0$$ for the items not selected ($$1$$, $$4$$, and $$5$$) in this case. Thus, an outcome represents a sample of $$n$$ elements out of an ordered sequence of $$N$$ items. Using the sequential sampling algorithm, $$n_i = \begin{cases} 0,& i = 1\\ \sum_{j=1}^{i-1} s_i,& i > 1 \end{cases}$$ and $$P(s) = \prod_{i=1}^N p_{s_i}$$ where $$p_{s_i} = \begin{cases} \frac{n - n_i}{N - i + 1},& s_i = 1\\ 1 - \frac{n - n_i}{N - i + 1},& s_i = 0 \end{cases}$$ Now, for a given $$n, N$$ with $$n < N$$, consider two distinct outcomes $$s$$ and $$t$$ that differ only at positions $$i$$ and $$i+1$$. For example: $$\begin{eqnarray} s &= (0, 1, 1, 0, 0) \\ t &= (0, 1, 0, 1, 0) \end{eqnarray}$$ differ only at positions $$i = 3$$ and $$i + 1 = 4$$. Without lack of generality, assume $$s_i = 1$$, $$s_{i+1} = 0$$, $$t_i = 0$$, $$t_{i+1} = 1$$. Then $$P(s) = \left(\prod_{j=1}^{i-1} p_{s_j}\right)p_{s_i}p_{s_{i+1}}\left(\prod_{j=i+2}^{N} p_{s_j}\right)$$ and $$\begin{eqnarray} P(t) =& \left(\prod_{j=1}^{i-1} p_{t_j}\right)p_{t_i}p_{t_{i+1}}\left(\prod_{j=i+2}^{N} p_{t_j}\right) \\ =& \left(\prod_{j=1}^{i-1} p_{s_j}\right)p_{t_i}p_{t_{i+1}}\left(\prod_{j=i+2}^{N} p_{s_j}\right) \end{eqnarray}$$ Thus $$P(s) = P(t)$$ if and only if $$p_{s_i}p_{s_{i+1}} = p_{t_i}p_{t_{i+1}}$$. Now $$\begin{eqnarray} p_{s_i}p_{s_{i+1}} =& \ \frac{n - n_i}{N - i + 1}\left(1 - \frac{n - (n_i+1)}{N - (i+1) + 1}\right) \\ =& \ \frac{n - n_i}{N - i + 1}\frac{N - i - n + n_i + 1}{N - i} \end{eqnarray}$$ and $$\begin{eqnarray} p_{t_i}p_{t_{i+1}} =& \ \left(1 - \frac{n - n_i}{N - i + 1}\right)\frac{n - n_i}{N - (i+1) + 1} \\ =& \ \frac{N - i + 1 - n + n_i}{N - i + 1}\frac{n - n_i}{N - i} \\ =& \ \frac{N - i - n + n_i + 1}{N - i + 1}\frac{n - n_i}{N - i} \\ =& \ \frac{n - n_i}{N - i + 1}\frac{N - i - n + n_i + 1}{N - i} \\ =& p_{s_i}p_{s_{i+1}} \end{eqnarray}$$ Thus, $$P(s) = P(t)$$.
When $$n < N$$, given any outcome $$s \in \Omega$$, we can form a new outcome $$s'$$ by swapping two adjacent values of $$s$$, and $$P(s) = P(s')$$ by the result above. Given $$s$$, we can take the largest value of $$i$$ with $$s_i = 1$$, and form a new sequence by swapping this value with it's next value until $$s_N = 1$$. For example: $$\begin{eqnarray} (0, 1, 1, 0, 0) \\ (0, 1, 0, 1, 0) \\ (0, 1, 0, 0, 1) \\ \end{eqnarray}$$ Note all of these outcomes are equiprobable. We can continue this with the second-to-last $$1$$ value, swapping until it's in the second-to-last position, and the third-to-last $$1$$ value, and so on. At each step, the modified outcome is equiprobable to the last. Continuing with the previous example, all of these outcomes are equiprobable: $$\begin{eqnarray} (0, 1, 0, 0, 1) \\ (0, 0, 1, 0, 1) \\ (0, 0, 0, 1, 1) \end{eqnarray}$$
Thus for any $$s \in \Omega$$, $$P(s) = P((0, \ldots, 0, 1, \ldots 1))$$. This in turn means for any $$s, t \in \Omega$$, $$P(s) = P(t)$$. Since all outcomes are equiprobable, and since there are $${N \choose n}$$ outcomes, for any $$s \in \Omega$$, $$P(s) = \frac{1}{{N \choose n}}$$
In the case when $$n = N$$, the result trivially holds, since there is only one outcome $$(1, \ldots, 1)$$, and $${N \choose n} = 1$$, so $$P((1, \ldots, 1)) = \frac{1}{{N \choose n}}$$
$$\square$$