LemmaStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck pass

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.

Squared-vector distributions are close in total variation

Statement

Let $x, y \in R^{n}$ be nonzero, and define $D_{x} (i) = x_{i}^{2} / ∥ x ∥_{2}^{2}$ and $D_{y} (i) = y_{i}^{2} / ∥ y ∥_{2}^{2}$ . Then $d_{T V} (D_{x}, D_{y}) \leq \frac{2 ∥ x - y ∥_{2}}{∥ x ∥_{2}} .$ The bound is valid even when its right side exceeds $1$ .

Facts & Assumptions

Given: Nonzero real vectors $x, y \in R^{n}$ .

[F1]

ℓ2 sample/query access to vectors and matrices: $D_{x} (i) = x_{i}^{2} / ∥ x ∥_{2}^{2}$ for nonzero $x$ , and likewise for $y$ .

[F2]

End-to-end channel and output error contract: $d_{T V} (p, q) = \frac{1}{2} \sum_{i} ∣ p_{i} - q_{i} ∣$ for distributions on a common finite alphabet.

[F3]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: Cauchy–Schwarz and the triangle inequality hold for the Euclidean norm.

Proof

1.1givenF1construct

Put $a = ∥ x ∥_{2} > 0$ , $b = ∥ y ∥_{2} > 0$ , $u = x / a$ , and $v = y / b$ . Then $∥ u ∥_{2} = ∥ v ∥_{2} = 1$ by their definitions.

2.1step 1.1F2F3algebra

Using $∣ u_{i}^{2} - v_{i}^{2} ∣ = ∣ u_{i} - v_{i} ∣ ∣ u_{i} + v_{i} ∣$ and [F3], $d_{T V} (D_{x}, D_{y}) = \frac{1}{2} \sum_{i} ∣ u_{i} - v_{i} ∣ ∣ u_{i} + v_{i} ∣ \leq \frac{1}{2} ∥ u - v ∥_{2} ∥ u + v ∥_{2} \leq ∥ u - v ∥_{2} .$

3.1step 1.1step 2.1F3algebra∎

Since $u - v = (x - y) / a + y (1 / a - 1 / b)$ , [F3] gives $∥ u - v ∥_{2} \leq \frac{∥ x - y ∥_{2}}{a} + b ∣ \frac{1}{a} - \frac{1}{b} ∣ = \frac{∥ x - y ∥_{2} + ∣ b - a ∣}{a} \leq \frac{2 ∥ x - y ∥_{2}}{a},$ where $∣ b - a ∣ \leq ∥ x - y ∥_{2}$ is the reverse triangle inequality. Combining this with step 2.1 proves the result.

Depends on

Used by

Tang's conditional recommendation sampler Theorem

Dependency tree · two levels

26 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

Ewin Tang, A quantum-inspired classical algorithm for recommendation systems, version 3 (standard reference, not scraped)