LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-02

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.

Half- $ℓ^{1}$ formula for total variation on a countable space

Statement

Let $E$ be an at most countable set equipped with the power-set $σ$ -algebra $2^{E}$ , and let $μ, ν$ be probability laws on $E$ (Total variation distance for probability laws). Then

$∥ μ - ν ∥_{T V} = \frac{1}{2} \sum_{x \in E} ∣ μ (x) - ν (x) ∣,$

where $μ (x), ν (x)$ denote the singleton masses and the series on the right is a series of nonnegative numbers in $[0, + \infty]$ . The value is finite; it is $0$ exactly when $μ = ν$ . The supremum defining the total variation distance is attained at the event $A_{+} = {x \in E : μ (x) > ν (x)}$ .

Facts & Assumptions

Given: An at most countable set $E$ with the power-set $σ$ -algebra and probability laws $μ, ν$ on $E$ .

[F1]

$∥ μ - ν ∥_{T V} : = \sup_{A \in 2^{E}} ∣ μ (A) - ν (A) ∣$ ; for every event the difference is a real number in $[- 1, 1]$ , so the supremum lies in $[0, 1]$ and carries no factor $\frac{1}{2}$ . (Total variation distance for probability laws)

[F2]

Every measure on an at most countable discrete space is its weighted sum of Dirac masses: $μ (A) = \sum_{x \in A} μ ({x})$ for every $A \subseteq E$ , and $\sum_{x \in E} μ ({x}) = μ (E)$ ; for probability laws the total mass is one. (Every measure on a countable discrete space is its weighted sum of Dirac measures)

Proof

Given: An at most countable set $E$ with the power-set $σ$ -algebra and probability laws $μ, ν$ on $E$ .

Proof technique: split the signed mass difference into its positive and negative parts, compare every event against them, and exhibit an attaining event.

1.1F1F2given

Put $d (x) : = μ (x) - ν (x)$ for $x \in E$ . Each $d (x)$ is a real number, and $\sum_{x \in E} ∣ d (x) ∣ \leq \sum_{x \in E} μ (x) + \sum_{x \in E} ν (x) = 1 + 1 = 2$ by the triangle inequality and [F2], so the family $(d (x))_{x \in E}$ is absolutely summable and $\sum_{x \in E} d (x) = μ (E) - ν (E) = 1 - 1 = 0$ .

2.1step 1.1given

Define $P : = \sum_{x : d (x) > 0} d (x)$ and $N : = \sum_{x : d (x) < 0} (- d (x))$ . Both are sums of nonnegative terms dominated by $\sum_{x} ∣ d (x) ∣ < \infty$ , hence finite, and $\sum_{x \in E} d (x) = P - N$ while $\sum_{x \in E} ∣ d (x) ∣ = P + N$ ; by step 1.1, $P - N = 0$ , so $P = N = \frac{1}{2} \sum_{x \in E} ∣ d (x) ∣$ .

3.1F2step 2.1given

Let $A \subseteq E$ . Since the family $(d (x))$ is absolutely summable, $\sum_{x \in A} d (x) = \sum_{x \in A, d (x) > 0} d (x) + \sum_{x \in A, d (x) < 0} d (x)$ is a real number equal to $μ (A) - ν (A)$ by [F2], and its positive part is at most $P$ while its negative part has absolute value at most $N$ : restricting a sum of nonnegative terms to a subset cannot increase it. Hence $μ (A) - ν (A) \leq P$ and $ν (A) - μ (A) \leq N = P$ , so $∣ μ (A) - ν (A) ∣ \leq P$ .

4.1F1step 2.1step 3.1given

For $A_{+} : = {x \in E : d (x) > 0}$ one has $μ (A_{+}) - ν (A_{+}) = \sum_{x \in A_{+}} d (x) = P$ , so the supremum defining the distance is at least $P$ ; together with step 3.1 the supremum is exactly $P = \frac{1}{2} \sum_{x \in E} ∣ d (x) ∣$ , which is the asserted identity.

5.1F1F2step 1.1step 2.1step 3.1step 4.1given∎

Boundary and axiom cases: if $E \subseteq {x}$ with a single point then $μ = ν$ on it by total mass one, and both sides of the identity are $0$ ; an empty $E$ carries no probability law, and the statement is then vacuous; when $μ = ν$ one has $d \equiv 0$ , $P = N = 0$ , and the event $A_{+}$ is empty; the series is bounded by $2$ throughout, so no infinite value arises and no subtraction of infinite quantities is performed; and no object is selected in steps 1.1–4.1 beyond the determined sets ${d > 0}$ , ${d < 0}$ and ${d > 0}$ , so no choice principle is used and the identity is an equality, not an iff.

Depends on

Used by

Dependency tree · two levels

9 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

Levin–Peres–Wilmer, Markov Chains and Mixing Times, second edition, Proposition 4.2 and Appendix C.1 (standard reference, not scraped)
Aldous–Chewi, Probability Theory, Lectures 13–15 (standard reference, not scraped)

Half-ℓ1ℓ1 formula for total variation on a countable space