random_switching_distinguishability_graph
For any discrete memoryless channels W_G and W_H and switching parameter p ∈ (0, 1), the distinguishability graph of the random switching channel is the categorical product D(W_G) × D(W_H).
Statement
theorem random_switching_distinguishability_graph {A B Y Z : Type*} [Fintype Y] [Fintype Z] (W_G : DiscreteMemorylessChannel A Y) (W_H : DiscreteMemorylessChannel B Z) (p : ℝ) (hp0 : 0 < p) (hp1 : p < 1) : channel_distinguishability_graph (random_switching_channel W_G W_H p hp0 hp1) = simple_graph_categorical_prod (channel_distinguishability_graph W_G) (channel_distinguishability_graph W_H)
- Source
- arXiv:2610.41977, Proposition 5.1, Equation (5.2)
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- DiscreteMemorylessChannelA discrete memoryless channel from input alphabet A to finite output alphabet Y is defined by non-negative transition probabilities…
- 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…
- simple_graph_categorical_prodThe categorical product (tensor product) G × H of two simple graphs G and H has vertex set V(G) × V(H), with an edge between (u₁, v₁) and…
- Used by 1
- 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…
Read back from the Lean
For any types A and B, and any finite types Y and Z, let W_G be a discrete memoryless channel from A to Y and W_H be a discrete memoryless channel from B to Z. For any real number p satisfying 0 < p and p < 1, the distinguishability graph of the random switching channel between W_G and W_H with parameter p is equal to the categorical (tensor) product of the distinguishability graph of W_G and the distinguishability graph of W_H.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that the distinguishability graph of a random switching channel W is the categorical product D(W_G) × D(W_H), we reduce graph equality to the equivalence of adjacency by extensionality. Adjacency in the switching channel requires distinct inputs with disjoint output distributions. Since the output support of W on (a, b) is the union of the injected supports of W_G(a) and W_H(b), two pairs have disjoint supports in W if and only if both component pairs have disjoint supports in W_G and W_H. Finally, nonemptiness of channel supports ensures that disjoint supports imply distinctness of the component inputs, matching the definition of the categorical product graph.
Every channel input has at least one output symbol with strictly positive probability.
Suppose, for contradiction, that no output symbol has positive transition probability for an input a, so W(y | a) ≤ 0 for all y. Since transition probabilities are non-negative, every W(y | a) must equal 0 by le_antisymm. By Finset.sum_eq_zero, the sum of probabilities over all outputs is 0, which contradicts the channel requirement that probabilities sum to 1.
uses
Finset.sum_eq_zero,le_antisymmby_contra h push Not at h have h0 : ∑ y, W.prob a y = 0 := by apply Finset.sum_eq_zero intro y _ exact le_antisymm (h y) (W.prob_nonneg a y) linarith [W.prob_sum a]
An output of the form inl(y) has positive probability under the switching channel for input (a, b) if and only if y is in the support of W_G(a).
We inspect an output x in the sum type Y ⊕ Z. When x = inl(y), the switching channel assigns probability p * W_G(a, y). Since p > 0, mul_pos_iff_of_pos_left shows this product is positive exactly when W_G(a, y) > 0. Hence inl(y) belongs to the support of the switching channel if and only if it belongs to the inl-image of the support of W_G(a). The inr-image component cannot contain inl(y) because the constructors inl and inr are disjoint.
uses
mem_ofPred_eq,mem_union,mul_pos_iff_of_pos_left,mem_image_of_mem,Set.mem_imageext x cases x with | inl y => rw [mem_ofPred_eq, mem_union] constructor · intro h left simp only [random_switching_channel, mul_pos_iff_of_pos_left hp0] at h exact mem_image_of_mem Sum.inl h · rintro (h | h) · rcases (Set.mem_image Sum.inl _ _).mp h with ⟨y', hy', hEq⟩ injection hEq with hEq' rw [hEq'] at hy' simp only [random_switching_channel, mul_pos_iff_of_pos_left hp0] exact hy' · rcases (Set.mem_image Sum.inr _ _).mp h with ⟨z, hz, hz'⟩ exact absurd hz' (by simp)
An output of the form inr(z) has positive probability under the switching channel for input (a, b) if and only if z is in the support of W_H(b).
When x = inr(z), the switching channel assigns probability (1 - p) * W_H(b, z). Since p < 1, 1 - p > 0, so the probability is positive exactly when W_H(b, z) > 0. Thus inr(z) is in the support of the switching channel if and only if it belongs to the inr-image of the support of W_H(b). Combining this with the inl case establishes that the full support for input (a, b) is the union of the inl-image of supp(W_G(a)) and the inr-image of supp(W_H(b)).
uses
mem_ofPred_eq,mem_union,mem_image_of_mem,mul_pos_iff_of_pos_left,Set.mem_imagerw [mem_ofPred_eq, mem_union] constructor · intro h right simp only [random_switching_channel] at h exact mem_image_of_mem Sum.inr (by rw [mul_pos_iff_of_pos_left] at h · exact h · linarith) · rintro (h | h) · rcases (Set.mem_image Sum.inl _ _).mp h with ⟨y', hy', hy'⟩ exact absurd hy' (by simp) · rcases (Set.mem_image Sum.inr _ _).mp h with ⟨z', hz', hEq⟩ injection hEq with hEq' rw [hEq'] at hz' simp only [random_switching_channel] rw [mul_pos_iff_of_pos_left] · exact hz' · linarith
Two input pairs have disjoint output supports in the random switching channel if and only if both component inputs have disjoint supports in W_G and W_H.
Rewriting both supports using random_switching_distinguishability_graph_support_eq expresses each support as a union of an inl-image and an inr-image. Distributing disjointness over unions produces four pairwise conditions via Set.disjoint_union_left and Set.disjoint_union_right. The cross terms between inl and inr images are disjoint by Set.disjoint_image_inl_image_inr, and the remaining terms simplify by injectivity of inl and inr (Set.disjoint_image_iff) to disjointness of the original supports in W_G and W_H.
uses
random_switching_distinguishability_graph_support_eq,Set.disjoint_union_left,Set.disjoint_union_right,Set.disjoint_image_iff,Sum.inl_injective,Sum.inr_injective,Set.disjoint_image_inl_image_inr,and_true,true_andrw [random_switching_distinguishability_graph_support_eq W_G W_H p hp0 hp1 ab, random_switching_distinguishability_graph_support_eq W_G W_H p hp0 hp1 ab'] rw [Set.disjoint_union_left, Set.disjoint_union_right, Set.disjoint_union_right] rw [Set.disjoint_image_iff Sum.inl_injective, Set.disjoint_image_iff Sum.inr_injective] simp only [Set.disjoint_image_inl_image_inr, Set.disjoint_image_inl_image_inr.symm, and_true, true_and]
To show graph equality, it suffices to prove that two input pairs u, v are adjacent in the switching channel distinguishability graph if and only if they are adjacent in the categorical product graph.
By graph extensionality (SimpleGraph.ext) and functional extensionality, two graphs are identical if their adjacency relations agree on all pairs u, v. Unfolding the definitions of channel_distinguishability_graph and simple_graph_categorical_prod, the goal reduces via propext to showing that (u ≠ v with disjoint switching channel supports) is equivalent to (u.1 ≠ v.1 with disjoint supports in W_G) and (u.2 ≠ v.2 with disjoint supports in W_H).
uses
SimpleGraph.ext,propextapply SimpleGraph.ext funext u v apply propext simp only [channel_distinguishability_graph, simple_graph_categorical_prod] constructor
Adjacency in the switching channel distinguishability graph implies adjacency in the categorical product graph.
Given u ≠ v and disjoint switching channel supports, random_switching_distinguishability_graph_disj yields disjoint supports in both W_G and W_H. If u.1 = v.1, the support of W_G(u.1) would be disjoint from itself; but by random_switching_distinguishability_graph_support_nonempty, this support is nonempty, which would mean an element is both in the set and not in the set (Set.disjoint_left.mp), a contradiction. The same nonemptiness argument shows u.2 ≠ v.2, proving adjacency in the categorical product.
uses
random_switching_distinguishability_graph_disj,random_switching_distinguishability_graph_support_nonempty,Set.disjoint_left.mp· rintro ⟨hne, hdisj⟩ obtain ⟨hdG, hdH⟩ := (random_switching_distinguishability_graph_disj W_G W_H p hp0 hp1 u v).mp hdisj refine ⟨⟨?_, hdG⟩, ⟨?_, hdH⟩⟩ · intro h rw [← h] at hdG obtain ⟨y, hy⟩ := random_switching_distinguishability_graph_support_nonempty W_G u.1 exact (Set.disjoint_left.mp hdG hy) hy · intro h rw [← h] at hdH obtain ⟨z, hz⟩ := random_switching_distinguishability_graph_support_nonempty W_H u.2 exact (Set.disjoint_left.mp hdH hz) hzAdjacency in the categorical product graph implies adjacency in the switching channel distinguishability graph.
Assuming adjacency in both components, we have u.1 ≠ v.1, u.2 ≠ v.2, and disjoint supports in both W_G and W_H. By random_switching_distinguishability_graph_disj, the switching channel output supports are disjoint. Furthermore, u ≠ v must hold because if u = v, projecting to the first component via congrArg Prod.fst would give u.1 = v.1, contradicting u.1 ≠ v.1.
uses
random_switching_distinguishability_graph_disj,congrArg· rintro ⟨⟨hne1, hdG⟩, ⟨hne2, hdH⟩⟩ refine ⟨?_, (random_switching_distinguishability_graph_disj W_G W_H p hp0 hp1 u v).mpr ⟨hdG, hdH⟩⟩ intro h exact hne1 (congrArg Prod.fst h)
Finset.sum_eq_zero- A finite sum of terms is zero if every term in the sum is zero.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
mem_ofPred_eq- An element belongs to a set-builder comprehension if and only if it satisfies the defining predicate.
mem_union- An element belongs to the union of two sets if and only if it belongs to at least one of them.
mul_pos_iff_of_pos_left- Multiplying by a strictly positive number preserves whether a quantity is strictly positive.
mem_image_of_mem- If an element belongs to a set, its image under a function belongs to the image of the set.
Set.mem_image- An element is in the image of a set under a function if and only if it is the value of the function at some element of the set.
random_switching_distinguishability_graph_support_eq- The support of the output distribution of the random switching channel on an input pair is the union of the left-injected support of the first channel and the right-injected support of the second channel.
Set.disjoint_union_left- A union of two sets is disjoint from a third set if and only if both sets are individually disjoint from the third.
Set.disjoint_union_right- A set is disjoint from a union of two sets if and only if it is disjoint from each of them individually.
Set.disjoint_image_iff- An injective function preserves and reflects disjointness of sets under forward images.
Sum.inl_injective- The left injection Sum.inl into a sum type is injective.
Sum.inr_injective- The right injection Sum.inr into a sum type is injective.
Set.disjoint_image_inl_image_inr- The image of any set under Sum.inl is disjoint from the image of any set under Sum.inr.
and_true- Conjunction of a proposition with True simplifies to the proposition itself.
true_and- Conjunction of True with a proposition simplifies to the proposition itself.
SimpleGraph.ext- Two simple graphs on the same vertex type are equal if their adjacency relations are equal.
propext- Propositional extensionality: two propositions are equal if and only if they are logically equivalent.
random_switching_distinguishability_graph_disj- Two inputs to a random switching channel have disjoint output supports if and only if their respective component inputs have disjoint supports in both underlying channels.
random_switching_distinguishability_graph_support_nonempty- For any input to a discrete memoryless channel, there is at least one output symbol with strictly positive probability.
Set.disjoint_left.mp- If two sets are disjoint, any element in the first set cannot belong to the second set.
congrArg- Applying a function to equal inputs yields equal outputs.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Setprivate lemma random_switching_distinguishability_graph_support_nonempty {A Y : Type*} [Fintype Y] (W : DiscreteMemorylessChannel A Y) (a : A) : ∃ y, 0 < W.prob a y := by by_contra h push Not at h have h0 : ∑ y, W.prob a y = 0 := by apply Finset.sum_eq_zero intro y _ exact le_antisymm (h y) (W.prob_nonneg a y) linarith [W.prob_sum a]private lemma random_switching_distinguishability_graph_support_eq {A B Y Z : Type*} [Fintype Y] [Fintype Z] (W_G : DiscreteMemorylessChannel A Y) (W_H : DiscreteMemorylessChannel B Z) (p : ℝ) (hp0 : 0 < p) (hp1 : p < 1) (ab : A × B) : {x : Y ⊕ Z | 0 < (random_switching_channel W_G W_H p hp0 hp1).prob ab x} = Sum.inl '' {y : Y | 0 < W_G.prob ab.1 y} ∪ Sum.inr '' {z : Z | 0 < W_H.prob ab.2 z} := by ext x cases x with | inl y => rw [mem_ofPred_eq, mem_union] constructor · intro h left simp only [random_switching_channel, mul_pos_iff_of_pos_left hp0] at h exact mem_image_of_mem Sum.inl h · rintro (h | h) · rcases (Set.mem_image Sum.inl _ _).mp h with ⟨y', hy', hEq⟩ injection hEq with hEq' rw [hEq'] at hy' simp only [random_switching_channel, mul_pos_iff_of_pos_left hp0] exact hy' · rcases (Set.mem_image Sum.inr _ _).mp h with ⟨z, hz, hz'⟩ exact absurd hz' (by simp) | inr z => rw [mem_ofPred_eq, mem_union] constructor · intro h right simp only [random_switching_channel] at h exact mem_image_of_mem Sum.inr (by rw [mul_pos_iff_of_pos_left] at h · exact h · linarith) · rintro (h | h) · rcases (Set.mem_image Sum.inl _ _).mp h with ⟨y', hy', hy'⟩ exact absurd hy' (by simp) · rcases (Set.mem_image Sum.inr _ _).mp h with ⟨z', hz', hEq⟩ injection hEq with hEq' rw [hEq'] at hz' simp only [random_switching_channel] rw [mul_pos_iff_of_pos_left] · exact hz' · linarithprivate lemma random_switching_distinguishability_graph_disj {A B Y Z : Type*} [Fintype Y] [Fintype Z] (W_G : DiscreteMemorylessChannel A Y) (W_H : DiscreteMemorylessChannel B Z) (p : ℝ) (hp0 : 0 < p) (hp1 : p < 1) (ab ab' : A × B) : Disjoint {x : Y ⊕ Z | 0 < (random_switching_channel W_G W_H p hp0 hp1).prob ab x} {x : Y ⊕ Z | 0 < (random_switching_channel W_G W_H p hp0 hp1).prob ab' x} ↔ Disjoint {y : Y | 0 < W_G.prob ab.1 y} {y : Y | 0 < W_G.prob ab'.1 y} ∧ Disjoint {z : Z | 0 < W_H.prob ab.2 z} {z : Z | 0 < W_H.prob ab'.2 z} := by rw [random_switching_distinguishability_graph_support_eq W_G W_H p hp0 hp1 ab, random_switching_distinguishability_graph_support_eq W_G W_H p hp0 hp1 ab'] rw [Set.disjoint_union_left, Set.disjoint_union_right, Set.disjoint_union_right] rw [Set.disjoint_image_iff Sum.inl_injective, Set.disjoint_image_iff Sum.inr_injective] simp only [Set.disjoint_image_inl_image_inr, Set.disjoint_image_inl_image_inr.symm, and_true, true_and]/-- The distinguishability graph of a random switching channel is the categorical product of the component distinguishability graphs. -/theorem random_switching_distinguishability_graph {A B Y Z : Type*} [Fintype Y] [Fintype Z] (W_G : DiscreteMemorylessChannel A Y) (W_H : DiscreteMemorylessChannel B Z) (p : ℝ) (hp0 : 0 < p) (hp1 : p < 1) : channel_distinguishability_graph (random_switching_channel W_G W_H p hp0 hp1) = simple_graph_categorical_prod (channel_distinguishability_graph W_G) (channel_distinguishability_graph W_H) := by apply SimpleGraph.ext funext u v apply propext simp only [channel_distinguishability_graph, simple_graph_categorical_prod] constructor · rintro ⟨hne, hdisj⟩ obtain ⟨hdG, hdH⟩ := (random_switching_distinguishability_graph_disj W_G W_H p hp0 hp1 u v).mp hdisj refine ⟨⟨?_, hdG⟩, ⟨?_, hdH⟩⟩ · intro h rw [← h] at hdG obtain ⟨y, hy⟩ := random_switching_distinguishability_graph_support_nonempty W_G u.1 exact (Set.disjoint_left.mp hdG hy) hy · intro h rw [← h] at hdH obtain ⟨z, hz⟩ := random_switching_distinguishability_graph_support_nonempty W_H u.2 exact (Set.disjoint_left.mp hdH hz) hz · rintro ⟨⟨hne1, hdG⟩, ⟨hne2, hdH⟩⟩ refine ⟨?_, (random_switching_distinguishability_graph_disj W_G W_H p hp0 hp1 u v).mpr ⟨hdG, hdH⟩⟩ intro h exact hne1 (congrArg Prod.fst h)