Subsampling Without Replacement

Why Subsample Without Replacement?

A discovered subtype is more convincing when it can be recovered after the analysis is perturbed. Repeated subsampling creates such perturbations by selecting a fraction of the observational units, refitting the specified subtype procedure on each selected set, and comparing the resulting partitions on units the runs have in common. The fraction matters: smaller subsets make the analysis face a stronger perturbation, but leave fewer observations—and often fewer members of small subtypes—with which to discover and compare groups.

The earlier material on bootstrap assessment of subgroup stability considers resampling with replacement. Subsampling without replacement instead uses distinct units within each run. It is useful when the question is how the subtype solution changes after omitting a substantial part of the observed cohort, rather than how it changes under a bootstrap sample that may repeat some units and omit others.

Definition: Let \(n\) be the number of eligible observational units. A subsample of size \(m\) is a subset of \(m\) distinct units drawn from those \(n\), with every subset of that size having equal probability under simple random subsampling. The subsample fraction is \(f=m/n\). Repeated subsampling draws multiple such subsets, usually independently from the same observed cohort. Units are not repeated within a subsample, although two different subsamples may overlap.

The unit must be the one appropriate to the study design, as established in the earlier material on choosing a resampling unit. For example, if several samples come from one person and the person is the independent unit, subsampling individual assay records would not create independent participants. Simple random subsampling also assumes that the units are exchangeable for the intended stability question. If the design requires preserving strata or other sampling structure, the resampling scheme should preserve it rather than pretending that all subsets are equally appropriate.

Specify the analysis protocol before interpreting results: the fraction, number of repetitions, subtype procedure, and the stability summary to be used. Apply the same defined protocol in each run. A stability score compares the partitions in the observations that can be compared across runs; it is not automatically a measure of biological truth or evidence that the subtypes cause outcomes. The result is conditional on the cohort, chosen procedure, and resampling design.

Overlap Sets the Comparison’s Information

Two partitions can only be compared directly for observational units represented in both runs. If \(A\) and \(B\) are independently drawn subsets, each of size \(m\), the size of their intersection \(A\cap B\) is random. Under simple random subsampling, any particular unit has probability \(m/n\) of appearing in \(A\), and the same probability of appearing in \(B\). The draws for the two runs are independent, so the unit’s probability of appearing in both is \((m/n)^2\). Summing this probability over the \(n\) units gives the expected intersection size.

E\bigl[|A\cap B|\bigr] =\sum_{i=1}^{n}P(i\in A,\ i\in B) =n\left(\frac{m}{n}\right)^2 =\frac{m^2}{n} =nf^2

This expectation is not a guarantee for any particular pair of runs. Nor should the many pairwise comparisons among repetitions be treated as independent observations: they reuse the same cohort and often reuse the same units. A large number of repetitions can describe the resampling distribution more finely, but it does not create a larger independent study population.

Worked Example: Expected Shared Participants

A hypothetical cohort contains \(n=200\) participants. Each run selects \(m=120\) participants without replacement, so \(f=120/200=0.60\). What is the expected number of participants shared by two independently drawn runs?

Using the overlap result,

E\bigl[|A\cap B|\bigr] =\frac{m^2}{n} =\frac{120^2}{200} =\frac{14{,}400}{200} =72\text{ participants}.

Thus the two runs share 72 participants on average, or \(72/120=0.60\) of the members of either run. The answer is an expectation across pairs of runs, not a claim that every pair shares exactly 72 people. If the same cohort instead used \(m=100\), the expected overlap would be \(100^2/200=50\) participants. The smaller fraction increases the perturbation but leaves fewer shared participants for comparison.

When a chosen stability score is computed only on shared units, the overlap size is part of its context. A score from a small intersection may be noisy or may describe a selected subset that is unrepresentative of the cohort. Report the fraction and the overlap distribution, not just the average score. If overlap is very small, a run-pair comparison may be uninformative even if the score itself is numerically well defined.

Fraction Choice and Rare Subtypes

A smaller \(f\) strengthens the perturbation: more of the observed cohort is omitted from each run. But it also reduces the expected sample size of every group and increases the chance that a rare group is poorly represented or absent. These are linked consequences, not separate tuning problems.

Suppose a particular subtype contains \(r\) of the \(n\) cohort members. Under simple random subsampling of size \(m\), its expected number of sampled members is \(mr/n=fr\). The probability of sampling none is the probability that all \(m\) selected units come from the \(n-r\) nonmembers:

P(\text{no members of the subtype}) =\frac{\binom{n-r}{m}}{\binom{n}{m}},

when \(m\leq n-r\); if \(m>n-r\), omission of all \(r\) members is impossible. The expression accounts for sampling without replacement. For a rough approximation when the cohort is large relative to the sample, the omission probability is about \((1-f)^r\), but the exact hypergeometric probability is preferable when counts are modest.

Worked Example: How Often Might a Rare Group Be Missing?

Imagine a hypothetical cohort of \(n=20\) people, including \(r=2\) members of a rare subtype. A run samples \(m=10\) people, so \(f=0.50\). Find the expected rare-subtype count and the probability that the run contains neither member.

The expected count is

E(\text{rare count})=fr=0.50(2)=1\text{ person}.

There are \(\binom{20}{10}=184{,}756\) possible size-10 subsets. To omit both rare members, all 10 selected people must come from the other 18, giving \(\binom{18}{10}=43{,}758\) subsets. Therefore,

P(\text{no rare members}) =\frac{\binom{18}{10}}{\binom{20}{10}} =\frac{43{,}758}{184{,}756} \approx 0.2368.

So about 23.68% of such runs omit the subtype entirely under this design. This does not show that the subtype is spurious; it shows that a half-cohort sample is a weak basis for judging its reproducibility when it has only two members in the cohort. Increasing the sample to \(m=15\) gives an omission probability of \(\binom{18}{15}/\binom{20}{15}=816/15{,}504\approx0.05263\), but the perturbation is then less severe.

In a real analysis, the subtype membership is usually not known in advance in the way it is in this calculation. The calculation is still a useful planning device: use plausible subgroup prevalences to assess whether a proposed fraction would often leave too few members for discovery. A low expected count is a warning, not a universal cutoff. The number needed to identify a group depends on the complexity of the subtype procedure, its separation from other groups, and the study’s scientific purpose.

A Practical Selection Strategy

There is no universally optimal subsample fraction. Choosing the largest fraction will often yield higher apparent agreement because runs are perturbed less and share more observations. Choosing an extremely small fraction can make a genuine subtype difficult to recover simply because too little information remains. The useful fraction is one that creates a meaningful perturbation while retaining adequate information for the stated stability question.

Set the target.
Decide whether the aim is to assess recovery after modest omissions or robustness to substantial cohort reduction. State the observational unit and any design structure that the sampling must preserve.

Check expected information.
For candidate values of \(f\), calculate \(m=fn\), expected overlap \(nf^2\), and expected counts \(fr\) for plausible small subtypes. Where appropriate, calculate the probability that a rare group is absent.

Run the prespecified analysis repeatedly.
Draw without replacement at the chosen fraction and apply the defined subtype procedure. Record whether runs fail, whether groups are unrepresented, and the amount of overlap available for comparisons.

Summarize and qualify.
Use a stability summary defined for the question, describe its distribution across run pairs, and report the fraction, overlap, and relevant group-count limitations. Interpret it as reproducibility under this perturbation, not as proof of a uniquely correct partition.

Worked Example: Choosing Between Candidate Fractions

A hypothetical cohort has \(n=100\) participants. Analysts consider fractions \(f=0.50\), \(0.70\), and \(0.90\). Across 40 runs at each fraction, they use the same preselected partition-similarity summary and obtain median pairwise values of 0.68, 0.81, and 0.94, respectively. They want a substantial perturbation but do not want comparisons to be dominated by very small overlaps. What do these results support?

The corresponding sample sizes are \(m=50\), \(70\), and \(90\). The expected pairwise overlaps are

\frac{50^2}{100}=25,\qquad \frac{70^2}{100}=49,\qquad \frac{90^2}{100}=81 \quad\text{participants}.

The highest median similarity, 0.94, occurs at \(f=0.90\), but those runs omit only 10% of the cohort and share 81 participants on average. It therefore indicates high agreement under a relatively mild perturbation. At \(f=0.50\), the analysis is perturbed more strongly, but runs share only 25 participants on average and have the lowest median similarity. The intermediate choice, \(f=0.70\), yields a median similarity of 0.81 and an expected overlap of 49 participants. If that level of overlap is adequate for the preselected comparison and the goal is a meaningful but not extreme perturbation, \(f=0.70\) is a defensible working choice. It is not established as universally best by these numbers; the choice should also be checked against plausible rare-subtype counts and the stability distribution, not just its median.

Assumptions, Diagnostics, and Alternatives

The simple formulas above rely on uniform sampling of fixed-size subsets from \(n\) units, with independent draws between runs. The overlap expectation follows from that design. The rare-group probability likewise treats the group membership of the \(r\) units as fixed in the observed cohort. These calculations do not assume that a clustering algorithm has a simple sampling distribution; subtype discovery is generally nonlinear, so there is no universal formula translating \(m\) into a stability score.

Several diagnostic patterns deserve attention. First, inspect whether the distribution of overlap sizes is broad enough that some comparisons have far less information than others. Second, check how often runs fail to produce the intended number of groups or omit very small groups. Third, look for a stability pattern that changes sharply with \(f\): it may reflect inadequate sample size at low fractions, rather than a clean threshold at which a subtype becomes scientifically real. Finally, determine whether a few repeated units or a few run pairs dominate the summary. Repeated subsampling does not make all run-pair comparisons independent.

The main alternative is bootstrap resampling, which samples with replacement and can include duplicate units within a run. It addresses a related but different perturbation and may be useful when bootstrap-based uncertainty is the target. Subsampling without replacement is often easier to interpret as analysis on a reduced cohort, but its results depend on the selected fraction. Neither approach is inherently superior for every stability question. A very large fraction is close to the full-data analysis and may provide weak perturbation; a very small fraction can make rare groups undetectable. Results at one fraction should therefore not be presented as a complete account of stability.

A useful general fact helps clarify the role of sampling without replacement for simple summaries. If \(y_i\) is a fixed binary indicator for each of the \(n\) observed units, define the cohort proportion \(p=n^{-1}\sum_{i=1}^n y_i\), the subsample proportion \(\hat p=m^{-1}\sum_{i\in A}y_i\), and the finite-cohort variance \(S^2=(n-1)^{-1}\sum_{i=1}^n(y_i-p)^2\). Under simple random subsampling, the variance of the subsample proportion is

\operatorname{Var}(\hat p) =\left(1-\frac{m}{n}\right)\frac{S^2}{m}.

The factor \(1-m/n\) is the finite-population correction: sampling a larger fraction without replacement leaves less uncertainty about this fixed cohort proportion. This result concerns a fixed numerical summary, not the variability of a complex subtype algorithm. It should not be used to claim that a stability score has the same variance or to attach an unearned confidence interval to it.

Common Mistakes

Calling subsampling “independent runs.” The subset draws can be independent, but the runs overlap in observed units, so their stability scores are not independent study replications.
Choosing the fraction by the highest score alone. A high score at a large fraction may mainly reflect mild perturbation and large overlap. Report how much the cohort was reduced.
Ignoring rare groups. An absent small subtype in a run can result from the sampling design. Check expected counts and omission probabilities before interpreting non-recovery as evidence of instability.
Comparing partitions without enough shared units. A numerical similarity computed on a tiny intersection may be unstable or unrepresentative. Include overlap information when reporting comparisons.
Overgeneralizing the result. Stability under one fraction and one analysis protocol does not establish that the discovered partition is biologically true, clinically useful, or robust to every other perturbation.

Key takeaway: Subsampling without replacement evaluates reproducibility under deliberate cohort reduction. The fraction controls both perturbation strength and the information available: expected pairwise overlap is \(nf^2\), while a subtype with \(r\) members contributes only \(fr\) members on average to each run. Choose and report the fraction in light of both quantities.

Check Your Understanding

Answer each question using the stated subsampling design. Solutions follow the questions.

A cohort has \(n=160\) units, and each run samples \(m=80\). What is the expected overlap of two independently drawn runs?
A subtype has \(r=5\) members in a cohort and the subsample fraction is \(f=0.60\). What is its expected count per run? Does that expectation guarantee at least one member in every run?
Why might a similarity of 0.95 at \(f=0.95\) be less compelling evidence of robustness to substantial perturbation than a similarity of 0.85 at \(f=0.65\)?
State one reason that pairwise stability values from 30 repeated subsamples should not be treated as 435 independent observations.

Solutions. (1) The expected overlap is \(m^2/n=80^2/160=6{,}400/160=40\) units. (2) The expected count is \(fr=0.60(5)=3\) members. This is an average, not a guarantee; some runs may contain fewer members, including none. (3) At \(f=0.95\), each run omits only 5% of the cohort, so the perturbation is mild and runs share many units. A score of 0.85 at \(f=0.65\) reflects agreement under a stronger reduction, though its overlap and rare-group representation still need checking. (4) Run pairs reuse the same observed cohort and share participants; consequently, their scores are dependent rather than 435 independent study replications.