# When a deduplication sample cannot distinguish two populations Two six-block populations have different payload savings, yet a uniform two-position sample produces the same entire distribution of unlabeled duplication-frequency histograms. This exact counting example is stronger than finding one coincidentally matching sample. ## Result | Equal-size population | Unique blocks | Saved payload | Matching pairs among 15 | | --- | ---: | ---: | ---: | | A,A,A,B,C,D | 4 | 1/3 | 3 | | A,A,B,B,C,C | 3 | 1/2 | 3 | Choose two of six positions uniformly without replacement. In either case: | Observed sample histogram | Probability | | --- | ---: | | Two identities seen once: y_1 = 2 | 12/15 = 4/5 | | One identity seen twice: y_2 = 1 | 3/15 = 1/5 | There are no other outcomes. Any estimator using only this histogram, the known population size six and sample size two has the same output distribution in both cases. It cannot be unbiased for both unique counts. This also applies to randomized estimators with extra randomness independent of the unknown population. Identity labels, position information, more reads and prior workload knowledge are outside this observation model. The naive saved fraction inside the sample has mean 1/10 for both populations, versus the actual 1/3 and 1/2. All fractions exclude compression, metadata, allocation, replication and other storage overhead. ## Derivation The matching unordered pairs number sum_j choose(c_j, 2), where c_j is the multiplicity of identity j. Both populations have three matching pairs out of choose(6, 2) = 15. A two-position histogram has only the two possible outcomes, proving equality of the entire observed law, not just its mean. For a fixed-size sample of k positions from N: E[y_i] = sum_j choose(c_j, i) choose(N-c_j, k-i) / choose(N, k), i >= 1. Impossible combinations contribute zero. This is hypergeometric sampling. Independent draws with replacement, independent Bernoulli inclusion, content-hash selection and contiguous reads have different sampling contracts. Unobserved identities (i = 0) cannot be counted from the sample alone. ## Controls and limits A three-position sample yields a triple with probability 1/20 for the first population and zero for the second. The histogram laws now differ, with total variation distance 3/20. A full census distinguishes them exactly. Thus this does not say that sampling is useless or that the Unseen algorithm is incorrect. This is a constructed finite example, not a fleet dataset, confidence-interval calibration, execution of Unseen linear programs or performance benchmark. No universal minimum sample percentage follows from it. ## Grouping can change expected bins, not only variance Consider four equal-size positions containing two copies each of A and B. Read exactly two positions. Every position has inclusion probability 1/2 in all three designs below, and the population histogram is unchanged: | Sampling design | E[y_1]: singleton identities | E[y_2]: paired identities | | --- | ---: | ---: | | Uniform two-position subset | 4/3 | 1/3 | | Uniformly choose one group from [AA], [BB] | 0 | 1 | | Uniformly choose one group from [AB], [AB] | 2 | 0 | Uniform position sampling has four mixed and two matching pairs among six subsets. Grouped sampling has just two possible read units. Equal position inclusion preserves expected occurrence counts, not the probability of seeing an identity exactly i times. Linearity of expectation sums those probabilities; it does not make them independent of grouping. Harnik et al., section 3.4, p. 286, state expected-DFH invariance when discussing super-chunks and increased variance. This construction shows that statement is not a universal consequence of equal per-position inclusion. It does not invalidate their measured workloads, calibrate their ranges, or reproduce their full estimator. The practical requirement is to state the read unit and placement of duplicate copies before reusing a sampling transform. ## Primary-source context Harnik, Khaitzin and Sotnikov, FAST 2016, sections 2.2 and 3.1, fit a population DFH to the sample and optimize over plausible fits to obtain a range. The authors explicitly describe the slackness choice as heuristic and tested on their datasets. Such a range is not automatically a calibrated 95% confidence interval for a new workload or read design. [Paper and metadata](https://www.usenix.org/conference/fast16/technical-sessions/presentation/harnik). Valiant and Valiant, NIPS 2013, definition 1 and section 2, remove identity labels to form a sample fingerprint and use linear programs to find a plausible population shape. Their fingerprint means a frequency summary, not a content hash. [Paper](https://papers.nips.cc/paper_files/paper/2013/file/53c04118df112c13a8c34b38343b9c10-Paper.pdf). The six-block construction above is Hesela's explanatory example, separate from either paper's empirical results. ## Reproduce Python 3.10 or later, standard library only, no seed or external dataset: python3 identifiability.py --check python3 -m unittest test_identifiability.py python3 -O -m unittest test_identifiability.py Run identifiability.py without --check to regenerate identifiability-results.json. Enumeration is capped at twelve positions. Tests compare position subsets with independent weighted multiplicity allocations and hypergeometric expectations for all eleven integer partitions of six and all seven sample sizes, including zero. Input validation, relabeling, census and the larger-sample control are tested. [Code](identifiability.py), [results](identifiability-results.json), [tests](test_identifiability.py), [earlier content-selection example](README.md).