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

Abstract

This preprint studies recovery of nonnegative integer populations from anonymous hop-count histograms under independent relay failures. Failed relays are bypassed by attaching surviving descendants to their nearest surviving ancestor, while targets on failed relays are silent. For every known survival probability p with 0 < p < 1, the mean and covariance at an interior path sensor determine the two leg populations up to exchange. On every rooted tree, means alone retain exactly the noiseless distance-shell information. Recovery requires only the covariance diagonal and one adaptively selected column. An explicit estimator has finite-sample guarantees; choosing p = n/(n+1) gives a polynomial sufficient sample bound for bounded counts on legs of length n. Further results address unknown-probability calibration, shared-ancestor moment formulas and higher-moment obstructions on spiders. The full-law identification conjecture for general trees remains open, with exact evidence for the finite families stated in the paper. Endpoint complexity consequences are imported from cited trace-reconstruction preprints and are separate from the directly proved covariance recovery theorem. The paper builds on earlier distance-shell work and explicitly relates its contribution to statistical network tomography, tree-deletion traces, deletion-channel population recovery and classical moment methods. Supplementary materials contain the LaTeX source, a pinned Lean 4 / Mathlib project proving selected endpoint and two-leg results, and exact Python computations with their results and reproduction instructions. The Lean formalization does not cover every theorem in the manuscript. The manuscript, LaTeX source and root documentation are licensed under CC BY 4.0. The Lean and Python materials are licensed under MIT, as specified in the supplementary archive.