Sequential Sampling With and Without Replacement

Why the Sampling Rule Matters

A sequence of draws from a finite population can have different probabilities depending on whether each selected item is returned before the next draw. If items are returned, the population composition remains the same at every draw. If items are retained, both the population size and the category counts change. The distinction affects the conditional probability at each step, and therefore the probability of the full sequence.

A second decision is whether the event concerns a particular order of outcomes or only the final composition of the sample. “Priority, then standard” specifies an order. “One priority item and one standard item” allows either order. The latter probability must include both possible sequences.

Definition: In sampling with replacement, each selected item is returned to the population before the next draw. In sampling without replacement, a selected item is not returned. An ordered sample records the order of draws; an unordered sample records which items or categories are selected, but not their order. Unless stated otherwise, assume each item currently available is equally likely to be selected.

Probabilities of Ordered Draws

Suppose a population contains $N$ items, of which $K$ are in a specified category. For draws with replacement, the probability of drawing from that category is $K/N$ at every draw. For draws without replacement, the probability changes after each draw: a selected item is removed from the available population.

For an ordered sequence of category outcomes, the multiplication rule gives the probability by multiplying the conditional probability at each step. The counts used at a step must reflect the outcomes of all preceding draws.

P(\text{ordered sequence}) = \prod_{r=1}^{n} P(\text{outcome at draw }r\mid\text{outcomes at draws }1,\ldots,r-1).

More explicitly, suppose there are $N_j$ items in category $j$, and the specified sequence has category $c_r$ on draw $r$. If $m_{j,r-1}$ is the number of earlier draws from category $j$, then the probability of that sequence is

\begin{aligned} \text{With replacement:}\quad &P(\text{sequence})=\prod_{r=1}^{n}\frac{N_{c_r}}{N},\\[4pt] \text{Without replacement:}\quad &P(\text{sequence})=\prod_{r=1}^{n} \frac{N_{c_r}-m_{c_r,r-1}}{N-r+1}. \end{aligned}

The second expression applies only when the requested sequence is possible. If a category has no remaining items at a step, that sequence has probability zero. The denominators decrease by one on each draw without replacement; with replacement, the population size and category counts are restored before every draw.

Worked Example: A Specified Pair of Draws

A bag contains 5 green tokens and 3 gold tokens. Two tokens are drawn at random. Find the probability of drawing green first and gold second (a) without replacement and (b) with replacement. Also find the probability of getting one token of each color when order does not matter.

Method. Use conditional probabilities for the specified order, then add the probabilities of the allowed orders for the unordered event. The common mistake is to calculate only green-then-gold when either order is acceptable.

(a) Without replacement, green then gold. There are 8 tokens initially, of which 5 are green. After a green token is drawn, 7 tokens remain, of which 3 are gold:

P(\text{green, then gold}) =\frac{5}{8}\cdot\frac{3}{7} =\frac{15}{56}.

(b) With replacement, green then gold. Returning the first token restores the original composition, so the probability of gold on the second draw is $3/8$:

P(\text{green, then gold}) =\frac{5}{8}\cdot\frac{3}{8} =\frac{15}{64}.

One of each color, order ignored. Without replacement, the other order, gold then green, also has probability $(3/8)(5/7)=15/56$. Therefore,

P(\text{one of each, without replacement}) =\frac{15}{56}+\frac{15}{56} =\frac{30}{56} =\frac{15}{28}.

With replacement, the two orders each have probability $15/64$, so the probability is $30/64=15/32$. As a check, the order-specific probability $15/56$ is less than the probability $15/28$ of either order, as it must be.

Unordered Samples and Combinations

When sampling without replacement, every set of $n$ distinct items is equally likely if each draw is uniform among the items still available. There are $\binom{N}{n}$ such sets. If the population has $N_j$ items in category $j$, and an unordered sample is required to contain $r_j$ items from that category, the number of favorable sets is $\prod_j \binom{N_j}{r_j}$. Thus the probability of that composition is the ratio of favorable sets to all possible sets.

Theorem: For a uniform sample of $n$ distinct items drawn without replacement from $N$ items, the probability of selecting $r_j$ items from each category $j$ is $$ \frac{\prod_j \binom{N_j}{r_j}}{\binom{N}{n}}, \qquad \sum_j r_j=n. $$ This formula is for an unordered sample composition. It assumes every $n$-item subset is equally likely.

The same composition can also be found by listing the possible category orders. If the composition has $r_j$ items from category $j$, the number of distinct category sequences is $n!/\prod_j r_j!$. For a fixed composition, each such sequence has the same probability under uniform sampling, so their probabilities can be added. The combination formula is usually shorter, but the sequence method makes the role of order explicit.

Why the Product and Combination Formulas Hold

For an ordered sequence, each successive draw is made from the population remaining after the previous specified outcomes. Applying the multiplication rule to these successive conditional probabilities gives the product formula. For example, without replacement, if the first two specified draws are from categories $a$ and $b$, the first factor is $N_a/N$; the second is $(N_b-1)/{(N-1)}$ if $a=b$, and $N_b/(N-1)$ if $a\ne b$. Each factor counts available items of the required category divided by all available items.

For the unordered formula, count all equally likely $n$-item subsets. To obtain the required composition, choose $r_j$ of the $N_j$ items from each category. These choices can be made in $\prod_j \binom{N_j}{r_j}$ ways, and every favorable set is counted once. Dividing by the total number $\binom{N}{n}$ gives the stated probability.

With replacement, each ordered sequence has probability given by the product of the original category proportions. For example, with two categories, a sample of $n$ draws containing $r$ items from the first category can occur in $\binom{n}{r}$ category orders. Its probability is therefore $\binom{n}{r}(K/N)^r(1-K/N)^{n-r}$. This expression is not the without-replacement formula: the category proportions are not depleted when an item is returned.

Worked Example: Exactly Two Marked Items

A tray contains 2 marked and 4 unmarked components, 6 in total. Three components are selected. Find the probability of exactly 2 marked components with replacement and without replacement. For the without-replacement case, also calculate the probability of the specific order marked, marked, unmarked.

Method. With replacement, count the possible positions of the two marked outcomes. Without replacement, use combinations for the unordered composition and conditional probabilities for the specified order. Do not use the with-replacement category proportion after a component has been retained.

With replacement. There are $\binom{3}{2}=3$ ways to place the two marked outcomes in the three draws. Each specified pattern has probability

\left(\frac{2}{6}\right)^2\left(\frac{4}{6}\right) =\frac{1}{9}\cdot\frac{2}{3} =\frac{2}{27}.

Thus,

P(\text{exactly 2 marked, with replacement}) =3\cdot\frac{2}{27} =\frac{2}{9}.

Without replacement, composition only. There is one way to choose both marked components and $\binom{4}{1}=4$ ways to choose one unmarked component. The total number of three-component subsets is $\binom{6}{3}=20$:

P(\text{exactly 2 marked, without replacement}) =\frac{\binom{2}{2}\binom{4}{1}}{\binom{6}{3}} =\frac{1\cdot4}{20} =\frac{1}{5}.

Without replacement, marked then marked then unmarked. After the first marked component, 1 marked and 4 unmarked remain among 5. After the second marked component, only 4 unmarked components remain among 4:

P(\text{marked, marked, unmarked}) =\frac{2}{6}\cdot\frac{1}{5}\cdot\frac{4}{4} =\frac{1}{15}.

There are three orders with exactly two marked components, and each has probability $1/15$; their total is $3/15=1/5$, agreeing with the combination calculation. The two sampling schemes give different answers, $2/9$ and $1/5$, because the composition changes only in the scheme without replacement.

Worked Example: An Unordered Sample With a Specified Composition

A shipment contains 5 priority-tagged parcels and 7 standard parcels. Four parcels are selected uniformly without replacement for a review. Find the probability that exactly 2 selected parcels have priority tags. Then find the probability of the particular order priority, standard, priority, standard.

Method. Use the combination formula for the composition and the sequential product rule for the specified order. This avoids treating an unordered event as though it were just one ordered sequence.

Exactly 2 priority parcels, order ignored. There are $\binom{5}{2}=10$ ways to choose the priority parcels and $\binom{7}{2}=21$ ways to choose the standard parcels. There are $\binom{12}{4}=495$ possible four-parcel subsets:

P(\text{exactly 2 priority}) =\frac{\binom{5}{2}\binom{7}{2}}{\binom{12}{4}} =\frac{10\cdot21}{495} =\frac{210}{495} =\frac{14}{33}.

Priority, standard, priority, standard. The conditional probabilities update after each selection:

\begin{aligned} P(\text{priority, standard, priority, standard}) &=\frac{5}{12}\cdot\frac{7}{11}\cdot\frac{4}{10}\cdot\frac{6}{9}\\ &=\frac{5\cdot7\cdot4\cdot6}{12\cdot11\cdot10\cdot9}\\ &=\frac{840}{11880} =\frac{7}{99}. \end{aligned}

There are $\binom{4}{2}=6$ possible orders containing two priority and two standard parcels. Each has probability $7/99$, so the total is $6(7/99)=42/99=14/33$, which checks the unordered calculation.

Common Traps and Practical Checks

Using the original denominator after a draw without replacement. After one item is retained, the number available decreases by one. Update both the total and the relevant category count.
Forgetting to include alternative orders. “One of each” includes both orders in a two-draw sample. A question that specifies “first $A$, then $B$” includes only one.
Confusing a combination with a sequence. Combinations count unordered selections. If the event specifies order, use sequential probabilities; if order is ignored, either count favorable subsets or add all allowed sequence probabilities.
Assuming a formula applies to a nonuniform selection process. The combination ratio requires every subset of the given size to be equally likely. If selection is weighted or restricted, the favorable and total subsets need not have equal probabilities.

A useful check is to compare a specified sequence with the event that contains it: the event probability cannot be smaller. When a composition can occur in several orders, add the probabilities of those distinct orders, or count the composition directly. For without-replacement calculations, verify that the remaining category counts sum to the remaining population size at every step.

Key takeaway: Identify whether items are replaced, whether order matters, and whether selection is uniform. Then update the counts after each draw or count favorable subsets. The correct method follows from those features of the sampling process.

Check Your Understanding

For each problem, distinguish the sampling rule from whether order matters before calculating.

A container has 3 silver and 5 copper washers. Two are drawn without replacement. Find the probability of silver first and copper second. (Answer: $15/56$)
A box has 4 blue and 2 orange labels. Three labels are drawn with replacement. Find the probability of exactly one orange label, with order ignored. (Answer: $4/9$)
A crate contains 3 inspected and 6 uninspected devices. Two are selected without replacement. Find the probability both are inspected, and then the probability that the first is inspected and the second is uninspected. (Answer: both inspected $=1/12$; specified order $=1/4$)
A packet contains 4 premium and 8 regular cards. Five are selected without replacement. Find the probability of exactly 2 premium cards. (Answer: $14/33$)
A jar holds 3 red and 3 white beads. Four beads are drawn without replacement. Find the probability of exactly 2 red beads, first using unordered subsets and then by counting category orders. (Answer: $3/5$)

What You'll Learn