channel_distinguishability_graph
The distinguishability graph D(W) of a discrete memoryless channel W has inputs as vertices, with two distinct inputs adjacent if and only if their output supports are disjoint.
Statement
def channel_distinguishability_graph {A Y : Type*} [Fintype Y] (W : DiscreteMemorylessChannel A Y) : SimpleGraph A
- Defined in
- arXiv:2610.41977, Section 5, Equation (5.1); Shannon 1956
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Built on 1
- DiscreteMemorylessChannelA discrete memoryless channel from input alphabet A to finite output alphabet Y is defined by non-negative transition probabilities…
- Used by 4
- random_switching_distinguishability_graphFor any discrete memoryless channels W_G and W_H and switching parameter p ∈ (0, 1), the distinguishability graph of the random switching…
- channel_zero_error_code_sizeThe zero-error code size M_0(W, n) for a channel W in n channel uses is the clique number of the n-th OR-power of its distinguishability…
- proposition_5_1_random_switching_channel_realizationFor any discrete memoryless channels W_G and W_H and any switching probability p ∈ (0, 1), the distinguishability graph of the switched…
- channel_zero_error_rateThe zero-error capacity rate R_0(W) of a channel W in bits per use is the base-2 logarithm of the Shannon OR-capacity of its…
Read back from the Lean
Given types A and Y with Y finite, and a discrete memoryless channel W from A to Y (with transition probability function W.prob : A → Y → ℝ), channel_distinguishability_graph W is the simple graph on vertex type A where two vertices a and a' are adjacent if and only if a ≠ a' and the sets {y : Y | 0 < W.prob a y} and {y : Y | 0 < W.prob a' y} are disjoint (i.e., there is no output y : Y that has strictly positive probability under both input a and input a').
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The distinguishability graph of a discrete memoryless channel has input vertices adjacent when their output supports are disjoint. -/ def channel_distinguishability_graph {A Y : Type*} [Fintype Y] (W : DiscreteMemorylessChannel A Y) : SimpleGraph A where Adj a a' := a ≠ a' ∧ Disjoint {y : Y | 0 < W.prob a y} {y : Y | 0 < W.prob a' y} symm := ⟨fun _ _ ⟨hne, hd⟩ => ⟨hne.symm, hd.symm⟩⟩ loopless := ⟨fun _ ⟨hne, _⟩ => hne rfl⟩