Sampling without replacement

Sampling without replacement selects distinct labelled units: after a unit is selected it is unavailable for the remaining draws. Distinct labels can carry equal numerical values, so repeated values do not necessarily imply a repeated unit. The rule alone does not specify selection probabilities; a procedure favoring particular units is still sampling without replacement but need not be simple random sampling.

In uniform sequential sampling without replacement, the next label is chosen uniformly among those remaining. For a population of $N$ labels, any ordered sequence of $n$ distinct labels has probability $1/[N(N-1)\cdots (N-n+1)]$. Each size-$n$ subset has $n!$ possible orders, so its probability is ${\left(\genfrac{}{}{0ex}{}{N}{n}\right)}^{-1}$. This gives the fixed-size simple random sampling design. Equivalently, take the first $n$ labels of a uniformly random permutation. Restricting a uniformly random permutation to a specified label set preserves uniformity; biased modulo mappings should not replace uniform selection.

The draw positions have identical marginal probability distributions, but exhibit statistical dependence. If the first label is $i$, the conditional probability that the second label is $i$ is zero, whereas its marginal probability is $1/N$. Thus these draws are not independent and identically distributed when $N>1$ and $n>1$. For a marked subset of labels, counting size-$n$ subsets with binomial coefficients gives the hypergeometric distribution. The resulting negative covariance explains the finite population correction for both counts and sample means.

Draw two distinct positions uniformly from a fixed population $z_1,\dots ,z_N$ with $N>1$. Let $\mu =N^{-1}{\sum }_i{z}_i$ and ${\sigma }_N^2=N^{-1}{\sum }_i(z_i-\mu {)}^2$. Each draw has expected value $\mu$, whileSubtracting the product of the expected values proves the covariance formula and explains the finite population correction. If the sampled values are coin biases and the actual tosses are conditionally independent given those biases, the law of total covariance gives the same covariance for their head indicator random variables.

Take a uniformly random permutation of $N>1$ distinguishable objects, of which $K$ are marked. Let $B_i$ mean that position $i$ is marked. Every object is equally likely at a specified position, so $\mathbb{P}(B_i)=K/N$. For distinct positions $i,j$, their ordered pair is uniform among $N(N-1)$ distinct-object pairs, of which $K(K-1)$ are marked pairs. This proves the second formula. For $K>0$, the conditional probability is $\mathbb{P}(B_i\mid B_j)=(K-1)/(N-1)$.

For the count $M_m$ of marked objects among the first $m$ positions, indicator random variables and linearity of expectation give $\mathbb{E}[M_m]=mK/N$. These draws are exchangeable but generally dependent; equal marginal probabilities do not imply independence.

Draw balls sequentially without replacement from $g$ green and $r$ red balls. Let $T$ be the first positive draw count at which the numbers of drawn green and red balls agree. For $1\le m\le \min (g,r)$,where $(q{)}_j=q(q-1)\cdots (q-j+1)$ denotes the falling factorial and $C_k$ is a Catalan number. Odd first return times are impossible because equality requires an even total number of draws.

To count the successful colour orders, encode green by a step $+1$ and red by a step $-1$. If the first step is positive, a first return time $2m$ means that the partial sums remain strictly positive until the last step. Delete the first positive step and the last negative step, and shift the remaining heights down by one. The result is a Dyck path of length $2m-2$, of which there are $C_{m-1}$. Interchanging the colours doubles this count. Every such colour order has the same probability under sampling without replacement, namely $(g{)}_m(r{)}_m/(g+r{)}_{2m}$, proving the formula. In particular, the numbers of successful colour orders at lengths two, four and six are two, two and four; balanced orders with an earlier return must not be counted.

When $m\ge 1$ items among $N$ are marked, inspect a uniformly random permutation until the first marked item. For its first position to be $k$, the other $m-1$ marked positions must lie among the last $N-k$ slots. This yields the displayed law with support $1\le k\le N-m+1$. It is the first-success form of sampling without replacement. For one marked item the position is uniform, while its conditional success chance after $r$ failures increases to $1/(N-r)$.