OAI.TraceReconstruction.quantitative_sample_lower_bound

The theorem states that, for fixed s in (0,1] and fixed c with 0 < c < 1/(4 ln 2), the following holds for every sequence of word lengths n_k tending to infinity and every sequence of deletion probabilities q_k in the open interval (0,1) such that q_k³ ln(n_k) tends to infinity: for all sufficiently large k, n_k raised to the real power c·ln(q_k³ ln n_k), viewed as an extended nonnegative real, is at most the sample complexity of reconstructing words of length n_k at deletion probability q_k with success level s. Here a trace of a binary word x of length n is obtained by an independent deletion mask that retains each bit with probability 1−q and deletes it with probability q, and the observer sees only the resulting list of retained bits, with no positions revealed. With m independent traces, an estimator is a map from the m-tuple of traces to a probability distribution over words of length n. A budget m is sufficient if some estimator has, for every word x, probability at least s of outputting exactly x, averaged over the m independent masks. The sample complexity is the infimum of the sufficient budgets m, taken in the extended nonnegative reals, and equals infinity if no budget suffices.