AFTD Auto-Formalizing Theoretical Domains

DiscreteMemorylessChannel

structure

A discrete memoryless channel from input alphabet A to finite output alphabet Y is defined by non-negative transition probabilities summing to 1 for each input symbol.

Statement

structure DiscreteMemorylessChannel (A Y : Type*) [Fintype Y]
Defined in
arXiv:2610.41977, Section 5; Shannon 1956
Verified
07 Nov 2026
Axioms
none listed
Used by 6
  • 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_distinguishability_graphThe distinguishability graph D(W) of a discrete memoryless channel W has inputs as vertices, with two distinct inputs adjacent if and only…
  • random_switching_channelGiven channels W_G and W_H and switching parameter p ∈ (0, 1), the random switching channel has input pairs (a, b) and tagged outputs in Y…
  • 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

A structure DiscreteMemorylessChannel parameterized by a type A and a finite type Y ([Fintype Y]), consisting of: 1. prob: a function from A → Y → ℝ; 2. prob_nonneg: a proof that for all a : A and y : Y, 0 ≤ prob a y; 3. prob_sum: a proof that for all a : A, the sum of prob a y over all y : Y (over Finset.univ) equals 1.

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

/-- A discrete memoryless channel from input alphabet A to finite output alphabet Y specified by transition probabilities. -/
structure DiscreteMemorylessChannel (A Y : Type*) [Fintype Y] where
  prob : A → Y → ℝ
  prob_nonneg : ∀ a y, 0 ≤ prob a y
  prob_sum : ∀ a, ∑ y, prob a y = 1
See it in the graphDiscuss this resultChallenge it