Lossy Distance-Shell Tomography on Paths: Recovery from Mean and Covariance

Abstract

Distance-shell sensors report how many targets lie at each hop, without identifying them or separating branches. We show that independent relay failures can make these aggregates more informative. Under nearest-surviving-ancestor bypass, for every known survival probability 0 < p < 1, the mean and covariance of an interior path sensor’s report determine the two integer-valued leg populations up to exchange. Means alone retain exactly the noiseless shell information on every rooted tree. Recovery needs only the covariance diagonal and one adaptively selected column. For legs of length n and counts at most h, a variance-sensitive rounding estimator has an explicit exponential bound at fixed p. At the designed probability p = 2n/(2n + 1), two independent batches give O(h⁴n log(1/δ)) rounds with O(n) scalar accumulators. A binary two-point lower bound proves the matching minimax order Θ_h(n log(1/δ)) for each fixed h and 0 < δ ≤ 1/4.

For nonempty populations with 0 < p < 1, the full law of the total reported count determines an unknown survival probability and the multiset of positive vertex counts. For nonempty binary populations, the mean and covariance already calibrate the survival probability; an explicit counterexample shows why this need not hold for general integer counts. On a spider with 2^k legs, parity populations agree in all joint moments through order k but differ at order k + 1. Endpoint reports connect the model to deletion-channel trace reconstruction, giving imported super-polynomial lower and quasi-polynomial upper bounds at fixed p. Joint landing formulas and a recursive generating function describe how shared ancestry enters the law on general trees. We conjecture that this law identifies the labelled occupied core, with exact finite evidence for every 0 < p < 1. Selected endpoint and two-leg results, together with variance, deterministic rounding and testing components of the sample analysis, are formalized in Lean 4; the full probability guarantee remains a written proof.