A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities

We introduce the following natural generalization of trace reconstruction, parameterized by a deletion probability δ ∈ (0, 1) and length n: There is a length n string of probabilities, S = p 1 , . . . , p n , and each "trace" is obtained by 1) sampling a length n binary string whose ith coordinate is independently set to 1 with probability p i and 0 otherwise, and then 2) deleting each of the binary values independently with probability δ, and returning the corresponding binary string of length ≤ n. The goal is to recover an estimate of S from a set of independently drawn traces. In the case that all p i ∈ 0, 1 this is the standard trace reconstruction problem. We show two complementary results. First, for worst-case strings S and any deletion probability at least order 1/ √ n, no algorithm can approximate S to constant ℓ ∞ distance or ℓ 1 distance o( √ n) using fewer than 2 Ω( √ n) traces. Second-as in the case for standard trace reconstructionreconstruction is easy for random S: for any sufficiently small constant deletion probability, and any ǫ > 0, drawing each p i independently from the uniform distribution over [0, 1], with high probability S can be recovered to ℓ 1 error ǫ using poly(n, 1/ǫ) traces and computation time. We show indistinguishability in our lower bound by regarding a complicated alternating sum (comparing two distributions) as the Fourier transformation of some function evaluated at ±π, and then showing that the Fourier transform decays rapidly away from zero by analyzing its moment generating function.