Lemma 10.7.2: a maximal coupling has and
ProvedWildeQIT.ZhangAudenaert.maximalCoupling_probentropyinformation-theoryp2o-gran-per-chapterp2o-plan-bookp2o-v1wilde-qit
Let and be random variables on a finite alphabet with distributions and . A coupling of is a pair whose marginals are and ; it is maximal if is as large as possible among all couplings (Definitions 10.7.2 and 10.7.3). If is a maximal coupling of and , then
The second identity converts the trace distance into an error probability, which is how Fano's inequality yields the Zhang–Audenaert bound.
Formalization Note A coupling is its joint distribution on ; maximality is the published FinDist.IsMaximalCoupling. The lemma is stated for every maximal coupling; their existence is a separate fact established in the book's proof.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_WildeQIT_coupling import Definitions.Def_WildeQIT_classicalTraceDist import Definitions.Def_WildeQIT_ZhangAudenaert_probNe
Formal statement
namespace WildeQIT.ZhangAudenaert
/-- **Lemma 10.7.2.**
Wilde, *From Classical to Quantum Shannon Theory*, arXiv:1106.1445v8, Lemma 10.7.2,
(10.103)–(10.104), p. 308: "Let `X` and `Y` be discrete random variables taking values in a
finite alphabet `𝒜`. Let `p_X` and `p_Y` denote their distributions, respectively. If `(X̂, Ŷ)` is
a maximal coupling of `X` and `Y`, then the following equalities hold
`Pr{X̂ = Ŷ} = ∑_{u∈𝒜} min{p_X(u), p_Y(u)}`, `Pr{X̂ ≠ Ŷ} = (1/2)‖p_X − p_Y‖₁`."
**Formalization Note.** A coupling `(X̂, Ŷ)` is its joint distribution `c` on `α × α`;
`FinDist.IsMaximalCoupling p q c` (Definitions 10.7.2–10.7.3, published) says that `c` has
marginals `p` and `q` and maximizes `Pr{X̂ = Ŷ} = c.probEq` over all couplings.
`Pr{X̂ ≠ Ŷ} = probNe c`. -/
theorem maximalCoupling_prob {α : Type} [Fintype α] [DecidableEq α] (p q : FinDist α)
(c : FinDist (α × α)) (hc : FinDist.IsMaximalCoupling p q c) :
c.probEq = ∑ u, min (p.prob u) (q.prob u) ∧
probNe c = (1 / 2) * classicalTraceDist p.prob q.prob := by sorry
end WildeQIT.ZhangAudenaert
Source
Wilde, From Classical to Quantum Shannon Theory, arXiv:1106.1445v8, Lemma 10.7.2, eqs. (10.103)–(10.104), p. 308
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.