# A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities

arXiv: https://arxiv.org/abs/2412.00674 · HTML: https://mlsanity.com/paper/2412.00674/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2024.

## Built on by (most cited first, 1 of 1)

- [Beyond the Library: An Agentic Framework for Autoformalizing Research Mathematics](https://mlsanity.com/paper/2606.31134/) (2026)

## Abstract (arXiv)

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.