How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Link-loss identifiability from split and coverage
Statement
Let and be a finite-tree multicast loss experiment with parameter space , independent link successes, and the same link probabilities in every probe. Let be the full repeated-probe sampling law determined by the one-probe outcome laws . Then is injective if and only if satisfies the split/coverage condition.
Statement references
Facts & Assumptions
Given: A finite rooted tree and finite family of probe designs as specified in the tree-experiment definition, with for every edge and for every design. Prove that the full sampling-law map is injective exactly when every receiver is covered and every nonroot internal vertex is split by some design.
Finite-tree multicast loss experiments: For each design, link successes are independent Bernoulli variables with fixed probabilities , the observed receiver success is the product on its root path, and the full outcome vector has the finite law .
Split and coverage condition for a multicast design: Coverage means every leaf receiver belongs to some ; a nonroot internal vertex is split when a single meets two distinct child subtrees.
Identifiability of an estimand: The identity target on the parameter set is identifiable exactly when equality of sampling laws implies equality of the parameter vectors, equivalently when the parameter-to-law map is injective.
Proof
For each vertex , put , with . Because , the repeated-probe law for design has one-probe marginal ; conversely, equality of all one-probe laws gives equality of . For each covered leaf , the marginal success probability read from any design containing is . Thus equality of experiment laws determines every when all receivers are covered.
If a receiver is uncovered, its terminal edge occurs in no observed path. Changing to a different value in leaves every observed outcome law unchanged, because is a leaf and no other receiver path uses . The parameter-to-law map is then not injective.
Suppose a nonroot internal vertex is not split by any design. Let be its incoming edge and let range over its child edges. Since and each of the finitely many , an open interval around keeps and for every child; all changed probabilities remain positive there. Choose in that interval. Define and , leaving every other probability fixed. Then for every child . In each design, receivers below , if any, lie in one child subtree ; their outcomes all contain the common factor . This factor is Bernoulli with the same success probability under and , and is independent of every other link variable. Receivers outside that child subtree use no changed edge; their possible shared ancestor variables remain unchanged and independent of . Thus the joint receiver-outcome law for every design is unchanged, although .
Let be a nonroot internal vertex. By [F2], some design contains receivers in distinct child subtrees of ; since is a tree their last common vertex on the root paths is . Write and . Independence in [F1] gives , , and . All factors are positive, so and . Hence the law determines for every nonroot internal vertex.
The value is fixed; steps 1.1 and 2.1 determine for every other vertex. For each edge , , with . Therefore equal experiment laws give equal on every edge, so is injective. By [F3], the link-probability identity target is identifiable.
If the split/coverage condition fails, either a receiver is uncovered or a nonroot internal vertex is not split. Steps 1.2 and 1.3 give two distinct parameter vectors with the same full sampling law in either case. Thus injectivity of implies the condition; together with step 3.1 this proves the equivalence.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- B. Xi, G. Michailidis, and V. N. Nair, Estimating Network Loss Rates Using Active Tomography, Journal of the American Statistical Association 101 (2006), 1430–1448 (standard reference, not scraped)
- E. Lawrence, G. Michailidis, and V. N. Nair, Statistical Inverse Problems in Active Network Tomography, IMS Lecture Notes–Monograph Series 54 (2007), 24–44 (standard reference, not scraped)