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=p1,ldots,pn, and each "trace" is obtained by 1) sampling a length n binary string whose ith coordinate is independently set to 1 with probability pi 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 pi ∈ 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^Omega(√n) traces. Second -- as in the case for standard trace reconstruction -- reconstruction is easy for random S: for any sufficiently small constant deletion probability, and any ε>0, drawing each pi 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.