InformationTheory

InformationTheory.Shannon.BroadcastChannel.Achievability.Assembly

source

Broadcast channel — superposition random-coding assembly and the achievability theorems #

The superposition random-coding assembly (E0 vanishing, per-codebook error decomposition, two-codebook average bounds, random → deterministic two-tier pigeonhole, rate slack) and the three achievability forms it carries. bc_achievability_of_rate_lt asks only that the rate pair lie strictly inside the three superposition constraints, so it holds over any broadcast channel. bc_achievability_of_infoJoint_ge takes the information-level rate-sum inequality I(X; Y₁ ∣ U) + I(U; Y₂) ≤ I((U, X); Y₁) as a hypothesis rather than deriving it, so it serves any comparison class that supplies it, and the headline bc_achievability is the branch where degradedness discharges that inequality.

Assembly (superposition random-coding, two receivers) #

The receiver-1/receiver-2 swap lemmas of BroadcastChannel/Achievability/ErrorAnalysis.lean are stitched into the achievability theorems through the same skeleton as the MAC achievability assembly (MultipleAccess/Achievability.lean), adapted to the two-tier (cloud / conditional-satellite) codebook and the two per-receiver error probabilities:

  • E0 vanishing: the correct-cloud ((U, Y₂)) and correct-triple ((U, X, Y₁)) atypical masses tend to 0 (AEP / LLN).
  • per-codebook averageErrorProb.toReal decomposition into the Bonferroni terms.
  • two-codebook average bounds (weight-summed swaps).
  • pigeonhole to a deterministic codebook pair.
  • rate-slack vanishing under the sum constraint max R₁ 0 + R₂ < I((U, X); Y₁) on the rate pair.
theorem

InformationTheory.Shannon.BroadcastChannel.bcAmbient_pairwise_coord

source
{U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] {γ : Type u_5} [MeasurableSpace γ] (pU : MeasureTheory.Measure U) [MeasureTheory.IsProbabilityMeasure pU] (K : ProbabilityTheory.Kernel U α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] (g : U × α × β₁ × β₂γ) (hg : Measurable g) :
Pairwise fun (i j : ) => ProbabilityTheory.IndepFun (fun (ω : U × α × β₁ × β₂) => g (ω i)) (fun (ω : U × α × β₁ × β₂) => g (ω j)) (bcAmbientMeasure pU K W)

Pairwise independence of any BC coordinate selector under the ambient measure.

Used by

    Vanishing of the E0 terms #

    theorem

    InformationTheory.Shannon.BroadcastChannel.bc_chan_fold_UXY₁_set

    source
    {U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pU : MeasureTheory.Measure U) [MeasureTheory.IsProbabilityMeasure pU] (K : ProbabilityTheory.Kernel U α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] (n : ) (T : Set ((Fin nU) × (Fin nα) × (Fin nβ₁))) :
    (MeasureTheory.Measure.map (fun (ω : U × α × β₁ × β₂) => (jointRV bcUs n ω, jointRV bcXs n ω, jointRV bcY₁s n ω)) (bcAmbientMeasure pU K W)).real T = u : Fin nU, x : Fin nα, (MeasureTheory.Measure.pi fun (x : Fin n) => pU).real {u} * (MeasureTheory.Measure.pi fun (l : Fin n) => K (u l)).real {x} * (MeasureTheory.Measure.pi fun (i : Fin n) => W (x i)).real {y : Fin nβ₁ × β₂ | (u, x, fun (i : Fin n) => (y i).1) T}

    Channel fold on the (U, X, Y₁) axes: the (U, X, Y₁)-block law of a finite set T equals the cloud/satellite/channel average of the β₁-projected channel mass. Receiver-1 analogue of bc_chan_fold_UY₂_set, obtained from the master fold by projecting the pair output to β₁.

    Used by
      theorem

      InformationTheory.Shannon.BroadcastChannel.bc_random_codebook_E0₁_swap

      source
      {U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pU : MeasureTheory.Measure U) [MeasureTheory.IsProbabilityMeasure pU] (K : ProbabilityTheory.Kernel U α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] (hpU : ∀ (u : U), 0 < pU.real {u}) (hK : ∀ (u : U) (a : α), 0 < (K u).real {a}) (hW : ∀ (a : α) (b : β₁ × β₂), 0 < (W a).real {b}) {M₁ M₂ n : } {ε : } (m : Fin M₁ × Fin M₂) :
      cU : BCCloudCodebook M₂ n U, (bcCloudCodebookMeasure pU M₂ n).real {cU} * cX : BCSatelliteCodebook M₁ M₂ n α, (bcSatelliteCodebookMeasure K M₁ M₂ n cU).real {cX} * (MeasureTheory.Measure.pi fun (i : Fin n) => W (cX m i)).real {y : Fin nβ₁ × β₂ | (cU m.2, cX m, fun (i : Fin n) => (y i).1)MAC.macJointlyTypicalSet (bcAmbientMeasure pU K W) bcUs bcXs bcY₁s n ε} = (MeasureTheory.Measure.map (fun (ω : U × α × β₁ × β₂) => (jointRV bcUs n ω, jointRV bcXs n ω, jointRV bcY₁s n ω)) (bcAmbientMeasure pU K W)).real {q : (Fin nU) × (Fin nα) × (Fin nβ₁) | qMAC.macJointlyTypicalSet (bcAmbientMeasure pU K W) bcUs bcXs bcY₁s n ε}

      Receiver-1 correct-triple averaged swap for the E0 event: the two-tier random-codebook average of the correct-triple atypical event equals the joint (U, X, Y₁)-block law of the atypical set. Receiver-1 analogue of bc_random_codebook_E0₂_swap.

      Used by
        theorem

        InformationTheory.Shannon.BroadcastChannel.bc_E0₂_vanishing

        source
        {U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pU : MeasureTheory.Measure U) [MeasureTheory.IsProbabilityMeasure pU] (K : ProbabilityTheory.Kernel U α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] {ε : } ( : 0 < ε) :
        Filter.Tendsto (fun (n : ) => (MeasureTheory.Measure.map (fun (ω : U × α × β₁ × β₂) => (jointRV bcUs n ω, jointRV bcY₂s n ω)) (bcAmbientMeasure pU K W)).real {q : (Fin nU) × (Fin nβ₂) | qChannelCoding.jointlyTypicalSet (bcAmbientMeasure pU K W) bcUs bcY₂s n ε}) Filter.atTop (nhds 0)

        The receiver-2 E0 error term vanishes: the correct-cloud atypical (U, Y₂)-block mass tends to 0 by the two-variable joint AEP (jointlyTypicalSet_prob_tendsto_one).

        Used by
          theorem

          InformationTheory.Shannon.BroadcastChannel.bc_E0₁_vanishing

          source
          {U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pU : MeasureTheory.Measure U) [MeasureTheory.IsProbabilityMeasure pU] (K : ProbabilityTheory.Kernel U α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] {ε : } ( : 0 < ε) :
          Filter.Tendsto (fun (n : ) => (MeasureTheory.Measure.map (fun (ω : U × α × β₁ × β₂) => (jointRV bcUs n ω, jointRV bcXs n ω, jointRV bcY₁s n ω)) (bcAmbientMeasure pU K W)).real {q : (Fin nU) × (Fin nα) × (Fin nβ₁) | qMAC.macJointlyTypicalSet (bcAmbientMeasure pU K W) bcUs bcXs bcY₁s n ε}) Filter.atTop (nhds 0)

          The receiver-1 E0 error term vanishes: the correct-triple atypical (U, X, Y₁)-block mass tends to 0 by the three-variable joint AEP (macJointlyTypicalSet_prob_tendsto_one).

          Used by

            Per-codebook averageErrorProb.toReal decomposition #

            theorem

            InformationTheory.Shannon.BroadcastChannel.bc_averageErrorProb₂_toReal_le

            source
            {U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pU : MeasureTheory.Measure U) (K : ProbabilityTheory.Kernel U α) (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] {M₁ M₂ n : } (hM₁ : 0 < M₁) (hM₂ : 0 < M₂) {ε : } (cU : BCCloudCodebook M₂ n U) (cX : BCSatelliteCodebook M₁ M₂ n α) :
            ((bcCodebookToCode pU K W hM₁ hM₂ ε cU cX).averageErrorProb₂ W).toReal (↑(M₁ * M₂))⁻¹ * m : Fin M₁ × Fin M₂, ((MeasureTheory.Measure.pi fun (i : Fin n) => W (cX m i)).real {y : Fin nβ₁ × β₂ | (cU m.2, fun (i : Fin n) => (y i).2)ChannelCoding.jointlyTypicalSet (bcAmbientMeasure pU K W) bcUs bcY₂s n ε} + w₂'Finset.univ.erase m.2, (MeasureTheory.Measure.pi fun (i : Fin n) => W (cX m i)).real {y : Fin nβ₁ × β₂ | (cU w₂', fun (i : Fin n) => (y i).2) ChannelCoding.jointlyTypicalSet (bcAmbientMeasure pU K W) bcUs bcY₂s n ε})

            Per-codebook averaging bound for receiver 2: the .toReal of the receiver-2 average error probability of the deterministic code bcCodebookToCode cU cX is at most the uniform average of the two-event Bonferroni bound (bc_errorProbAt₂_le_bonferroni).

            Used by
              theorem

              InformationTheory.Shannon.BroadcastChannel.bc_averageErrorProb₁_toReal_le

              source
              {U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pU : MeasureTheory.Measure U) (K : ProbabilityTheory.Kernel U α) (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] {M₁ M₂ n : } (hM₁ : 0 < M₁) (hM₂ : 0 < M₂) {ε : } (cU : BCCloudCodebook M₂ n U) (cX : BCSatelliteCodebook M₁ M₂ n α) :
              ((bcCodebookToCode pU K W hM₁ hM₂ ε cU cX).averageErrorProb₁ W).toReal (↑(M₁ * M₂))⁻¹ * m : Fin M₁ × Fin M₂, ((MeasureTheory.Measure.pi fun (i : Fin n) => W (cX m i)).real {y : Fin nβ₁ × β₂ | (cU m.2, cX m, fun (i : Fin n) => (y i).1)MAC.macJointlyTypicalSet (bcAmbientMeasure pU K W) bcUs bcXs bcY₁s n ε} + m₁'Finset.univ.erase m.1, (MeasureTheory.Measure.pi fun (i : Fin n) => W (cX m i)).real {y : Fin nβ₁ × β₂ | (cU m.2, cX (m₁', m.2), fun (i : Fin n) => (y i).1) MAC.macJointlyTypicalSet (bcAmbientMeasure pU K W) bcUs bcXs bcY₁s n ε} + pFinset.univ.erase m.2 ×ˢ Finset.univ, (MeasureTheory.Measure.pi fun (i : Fin n) => W (cX m i)).real {y : Fin nβ₁ × β₂ | (cU p.1, cX (p.2, p.1), fun (i : Fin n) => (y i).1) MAC.macJointlyTypicalSet (bcAmbientMeasure pU K W) bcUs bcXs bcY₁s n ε})

              Per-codebook averaging bound for receiver 1: the .toReal of the receiver-1 average error probability of bcCodebookToCode cU cX is at most the uniform average of the three-event Bonferroni bound (bc_errorProbAt₁_le_bonferroni3).

              Used by

                Two-codebook average bounds #

                The two-tier codebook expectation is the nonnegative-weighted "linear functional" L f = ∑ cU, wU cU * ∑ cX, wX cU cX * f cU cX. The generic bc_weighted_two_tier_* lemmas express its monotonicity and linearity; the per-alias swaps evaluate L on each Bonferroni term, and bc_pair_aggregate₂/₁ fold them into the closed-form bounds.

                theorem

                InformationTheory.Shannon.BroadcastChannel.bc_weighted_two_tier_mono

                source
                {κU : Type u_5} {κX : Type u_6} [Fintype κU] [Fintype κX] (wU : κU) (wX : κUκX) (hwU : ∀ (cU : κU), 0 wU cU) (hwX : ∀ (cU : κU) (cX : κX), 0 wX cU cX) (f g : κUκX) (hfg : ∀ (cU : κU) (cX : κX), f cU cX g cU cX) :
                cU : κU, wU cU * cX : κX, wX cU cX * f cU cX cU : κU, wU cU * cX : κX, wX cU cX * g cU cX

                Monotonicity of the two-tier nonnegative-weighted codebook average.

                Used by
                  theorem

                  InformationTheory.Shannon.BroadcastChannel.bc_weighted_two_tier_add

                  source
                  {κU : Type u_5} {κX : Type u_6} [Fintype κU] [Fintype κX] (wU : κU) (wX f g : κUκX) :
                  cU : κU, wU cU * cX : κX, wX cU cX * (f cU cX + g cU cX) = cU : κU, wU cU * cX : κX, wX cU cX * f cU cX + cU : κU, wU cU * cX : κX, wX cU cX * g cU cX

                  Additivity of the two-tier weighted codebook average.

                  Used by
                    theorem

                    InformationTheory.Shannon.BroadcastChannel.bc_weighted_two_tier_const_mul

                    source
                    {κU : Type u_5} {κX : Type u_6} [Fintype κU] [Fintype κX] (wU : κU) (wX : κUκX) (c : ) (f : κUκX) :
                    cU : κU, wU cU * cX : κX, wX cU cX * (c * f cU cX) = c * cU : κU, wU cU * cX : κX, wX cU cX * f cU cX

                    Pulling a constant scalar out of the two-tier weighted codebook average.

                    Used by
                      theorem

                      InformationTheory.Shannon.BroadcastChannel.bc_weighted_two_tier_sum_index

                      source
                      {κU : Type u_5} {κX : Type u_6} {ι : Type u_7} [Fintype κU] [Fintype κX] (s : Finset ι) (wU : κU) (wX : κUκX) (h : ικUκX) :
                      cU : κU, wU cU * cX : κX, wX cU cX * is, h i cU cX = is, cU : κU, wU cU * cX : κX, wX cU cX * h i cU cX

                      Interchanging a finite index sum with the two-tier weighted codebook average.

                      Used by
                        theorem

                        InformationTheory.Shannon.BroadcastChannel.bc_pair_aggregate₂

                        source
                        {κU : Type u_5} {κX : Type u_6} [Fintype κU] [Fintype κX] {M₁ M₂ : } (hM₂ : 0 < M₂) (wU : κU) (wX : κUκX) (hwU : ∀ (cU : κU), 0 wU cU) (hwX : ∀ (cU : κU) (cX : κX), 0 wX cU cX) (P : κUκX) (E0 : Fin M₁ × Fin M₂κUκX) (wc : Fin M₁ × Fin M₂Fin M₂κUκX) (A e2 Minv : ) (hMinv : 0 Minv) (hMinvM : Minv * ↑(M₁ * M₂) = 1) (hP : ∀ (cU : κU) (cX : κX), P cU cX Minv * m : Fin M₁ × Fin M₂, (E0 m cU cX + w₂'Finset.univ.erase m.2, wc m w₂' cU cX)) (hE0 : ∀ (m : Fin M₁ × Fin M₂), cU : κU, wU cU * cX : κX, wX cU cX * E0 m cU cX = A) (hwc : ∀ (m : Fin M₁ × Fin M₂), w₂'Finset.univ.erase m.2, cU : κU, wU cU * cX : κX, wX cU cX * wc m w₂' cU cX e2) :
                        cU : κU, wU cU * cX : κX, wX cU cX * P cU cX A + (M₂ - 1) * e2

                        Receiver-2 aggregation: folding the per-message two-event Bonferroni bound together with the two evaluated swaps (E0 mass A, wrong-cloud exponent e2) bounds the two-tier weighted codebook average by the closed form A + (M₂ − 1) · e2.

                        Used by
                          theorem

                          InformationTheory.Shannon.BroadcastChannel.bc_pair_aggregate₁

                          source
                          {κU : Type u_5} {κX : Type u_6} [Fintype κU] [Fintype κX] {M₁ M₂ : } (hM₁ : 0 < M₁) (hM₂ : 0 < M₂) (wU : κU) (wX : κUκX) (hwU : ∀ (cU : κU), 0 wU cU) (hwX : ∀ (cU : κU) (cX : κX), 0 wX cU cX) (P : κUκX) (E0 : Fin M₁ × Fin M₂κUκX) (Eb : Fin M₁ × Fin M₂Fin M₁κUκX) (Ec : Fin M₁ × Fin M₂Fin M₂ × Fin M₁κUκX) (A eb ec Minv : ) (hMinv : 0 Minv) (hMinvM : Minv * ↑(M₁ * M₂) = 1) (hP : ∀ (cU : κU) (cX : κX), P cU cX Minv * m : Fin M₁ × Fin M₂, (E0 m cU cX + m₁'Finset.univ.erase m.1, Eb m m₁' cU cX + pFinset.univ.erase m.2 ×ˢ Finset.univ, Ec m p cU cX)) (hE0 : ∀ (m : Fin M₁ × Fin M₂), cU : κU, wU cU * cX : κX, wX cU cX * E0 m cU cX = A) (hEb : ∀ (m : Fin M₁ × Fin M₂), m₁'Finset.univ.erase m.1, cU : κU, wU cU * cX : κX, wX cU cX * Eb m m₁' cU cX eb) (hEc : ∀ (m : Fin M₁ × Fin M₂), pFinset.univ.erase m.2 ×ˢ Finset.univ, cU : κU, wU cU * cX : κX, wX cU cX * Ec m p cU cX ec) :
                          cU : κU, wU cU * cX : κX, wX cU cX * P cU cX A + (M₁ - 1) * eb + (M₂ - 1) * M₁ * ec

                          Receiver-1 aggregation: folding the per-message three-event Bonferroni bound together with the three evaluated swaps (E0 mass A, wrong-satellite exponent eb, wrong-cloud exponent ec) bounds the two-tier weighted codebook average by the corresponding closed form.

                          Used by
                            theorem

                            InformationTheory.Shannon.BroadcastChannel.bc_random_codebook_average₂_le

                            source
                            {U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pU : MeasureTheory.Measure U) [MeasureTheory.IsProbabilityMeasure pU] (K : ProbabilityTheory.Kernel U α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] (hpU : ∀ (u : U), 0 < pU.real {u}) (hK : ∀ (u : U) (a : α), 0 < (K u).real {a}) (hW : ∀ (a : α) (b : β₁ × β₂), 0 < (W a).real {b}) {M₁ M₂ n : } (hM₁ : 0 < M₁) (hM₂ : 0 < M₂) {ε : } ( : 0 < ε) :
                            cU : BCCloudCodebook M₂ n U, (bcCloudCodebookMeasure pU M₂ n).real {cU} * cX : BCSatelliteCodebook M₁ M₂ n α, (bcSatelliteCodebookMeasure K M₁ M₂ n cU).real {cX} * ((bcCodebookToCode pU K W hM₁ hM₂ ε cU cX).averageErrorProb₂ W).toReal (MeasureTheory.Measure.map (fun (ω : U × α × β₁ × β₂) => (jointRV bcUs n ω, jointRV bcY₂s n ω)) (bcAmbientMeasure pU K W)).real {q : (Fin nU) × (Fin nβ₂) | qChannelCoding.jointlyTypicalSet (bcAmbientMeasure pU K W) bcUs bcY₂s n ε} + (M₂ - 1) * Real.exp (n * (-bcInfo₂ pU K W + 3 * ε))

                            Two-codebook average bound for receiver 2: the random-codebook expectation of the receiver-2 average error is at most the (vanishing) E0 mass plus the wrong-cloud exponent.

                            Used by
                              theorem

                              InformationTheory.Shannon.BroadcastChannel.bc_random_codebook_average₁_le

                              source
                              {U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pU : MeasureTheory.Measure U) [MeasureTheory.IsProbabilityMeasure pU] (K : ProbabilityTheory.Kernel U α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] (hpU : ∀ (u : U), 0 < pU.real {u}) (hK : ∀ (u : U) (a : α), 0 < (K u).real {a}) (hW : ∀ (a : α) (b : β₁ × β₂), 0 < (W a).real {b}) {M₁ M₂ n : } (hM₁ : 0 < M₁) (hM₂ : 0 < M₂) {ε : } ( : 0 < ε) :
                              cU : BCCloudCodebook M₂ n U, (bcCloudCodebookMeasure pU M₂ n).real {cU} * cX : BCSatelliteCodebook M₁ M₂ n α, (bcSatelliteCodebookMeasure K M₁ M₂ n cU).real {cX} * ((bcCodebookToCode pU K W hM₁ hM₂ ε cU cX).averageErrorProb₁ W).toReal (MeasureTheory.Measure.map (fun (ω : U × α × β₁ × β₂) => (jointRV bcUs n ω, jointRV bcXs n ω, jointRV bcY₁s n ω)) (bcAmbientMeasure pU K W)).real {q : (Fin nU) × (Fin nα) × (Fin nβ₁) | qMAC.macJointlyTypicalSet (bcAmbientMeasure pU K W) bcUs bcXs bcY₁s n ε} + (M₁ - 1) * Real.exp (n * (-bcInfo₁ pU K W + 4 * ε)) + (M₂ - 1) * M₁ * Real.exp (n * (-bcInfoJoint pU K W + 3 * ε))

                              Two-codebook average bound for receiver 1: the random-codebook expectation of the receiver-1 average error is at most the (vanishing) E0 mass plus the wrong-satellite (E_b) and wrong-cloud (E_c) exponents.

                              Used by

                                Random → deterministic (two-tier pigeonhole) #

                                theorem

                                InformationTheory.Shannon.BroadcastChannel.bc_two_tier_pigeonhole

                                source
                                {κU : Type u_5} {κX : Type u_6} [Fintype κU] [Fintype κX] (wU : κU) (wX val : κUκX) (hwU_nn : ∀ (cU : κU), 0 wU cU) (hwX_nn : ∀ (cU : κU) (cX : κX), 0 wX cU cX) (hwU_sum : cU : κU, wU cU = 1) (hwX_sum : ∀ (cU : κU), cX : κX, wX cU cX = 1) (B : ) (h_avg : cU : κU, wU cU * cX : κX, wX cU cX * val cU cX B) :
                                ∃ (cU : κU) (cX : κX), val cU cX B

                                Abstract two-tier pigeonhole. Nonnegative outer weights wU summing to 1, and for every outer index a nonnegative inner-weight family wX cU summing to 1, whose weighted double average of val is ≤ B, force some index pair with val cU cX ≤ B. (If every pair had val > B the weighted average would strictly exceed B.)

                                Used by
                                  theorem

                                  InformationTheory.Shannon.BroadcastChannel.bc_exists_codebook_le_avg

                                  source
                                  {U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pU : MeasureTheory.Measure U) [MeasureTheory.IsProbabilityMeasure pU] (K : ProbabilityTheory.Kernel U α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] {M₁ M₂ n : } (hM₁ : 0 < M₁) (hM₂ : 0 < M₂) {ε : } (B : ) (h_avg : cU : BCCloudCodebook M₂ n U, (bcCloudCodebookMeasure pU M₂ n).real {cU} * cX : BCSatelliteCodebook M₁ M₂ n α, (bcSatelliteCodebookMeasure K M₁ M₂ n cU).real {cX} * (((bcCodebookToCode pU K W hM₁ hM₂ ε cU cX).averageErrorProb₁ W).toReal + ((bcCodebookToCode pU K W hM₁ hM₂ ε cU cX).averageErrorProb₂ W).toReal) B) :
                                  ∃ (cU : BCCloudCodebook M₂ n U) (cX : BCSatelliteCodebook M₁ M₂ n α), ((bcCodebookToCode pU K W hM₁ hM₂ ε cU cX).averageErrorProb₁ W).toReal + ((bcCodebookToCode pU K W hM₁ hM₂ ε cU cX).averageErrorProb₂ W).toReal B

                                  Two-tier pigeonhole for the superposition random code: if the random-codebook expectation of the summed per-receiver errors is ≤ B, some deterministic cloud/satellite codebook pair achieves the summed error ≤ B. Bounding the sum lets a single codebook meet both receivers' targets simultaneously.

                                  Used by

                                    Degradedness and rate slack #

                                    theorem

                                    InformationTheory.Shannon.BroadcastChannel.bcMarkovChain_UX_Y₁_Y₂

                                    source
                                    {U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pU : MeasureTheory.Measure U) [MeasureTheory.IsProbabilityMeasure pU] (K : ProbabilityTheory.Kernel U α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] (hdeg : IsBCDegraded W) :
                                    IsMarkovChain (bcJointDistribution pU K W) (fun (q : U × α × β₁ × β₂) => (q.1, q.2.1)) (fun (q : U × α × β₁ × β₂) => q.2.2.1) fun (q : U × α × β₁ × β₂) => q.2.2.2

                                    Base data-processing Markov chain (U, X) → Y₁ → Y₂ for the degraded broadcast joint law: under physical degradedness the degraded output Y₂ is a stochastic function of Y₁ alone (via the degrading kernel Q), hence conditionally independent of the cloud/input pair (U, X) given Y₁. @audit:ok

                                    Used by
                                      theorem

                                      InformationTheory.Shannon.BroadcastChannel.bc_degraded_infoJoint_ge

                                      source

                                      Superadditivity under degradedness: for a physically degraded channel X → Y₁ → Y₂, the joint information I((U, X); Y₁) dominates the sum of the two per-receiver informations I(X; Y₁ ∣ U) + I(U; Y₂). Chain rule I((U, X); Y₁) = I(U; Y₁) + I(X; Y₁ ∣ U) plus data processing I(U; Y₁) ≥ I(U; Y₂). This makes the receiver-1 joint-decoding rate sum R₁ + R₂ < I((U, X); Y₁) follow automatically from the two corner constraints. @audit:ok

                                      Used by
                                        theorem

                                        InformationTheory.Shannon.BroadcastChannel.bc_Ec_lt_of_rate

                                        source
                                        {Ijoint R₁ R₂ ε ε' : } (hR₁ : 0 R₁) (hgap : 0 < Ijoint - (R₁ + R₂) - 3 * ε) (hε' : 0 < ε') :
                                        ∃ (N : ), nN, (Real.exp (n * R₂)⌉₊ - 1) * Real.exp (n * R₁)⌉₊ * Real.exp (n * (-Ijoint + 3 * ε)) < ε'

                                        The receiver-1 wrong-cloud rate slack (E_c) vanishes: with the joint AEP gap I((U, X); Y₁) − (R₁ + R₂) − 3ε > 0 and non-negative rate 0 ≤ R₁, the wrong-cloud prefactor (⌈exp(nR₂)⌉−1)·⌈exp(nR₁)⌉ times exp(n(−I((U, X); Y₁) + 3ε)) falls below any tolerance for large n. The 0 ≤ R₁ hypothesis is essential: for R₁ < 0 the ceil ⌈exp(nR₁)⌉ floors at 1 instead of shrinking like exp(nR₁), so the negative slack the gap allocates to the R₁ factor is not delivered and the prefactor diverges. The bound is stated over abstract rates so that a superposition scheme may instantiate it at either the message rates or the subcodebook rates; every such instantiation runs at a strictly positive rate, so the precondition is met.

                                        Used by
                                          theorem

                                          InformationTheory.Shannon.BroadcastChannel.bc_ceil_exp_max_zero

                                          source
                                          (R : ) (n : ) :
                                          Used by
                                            theorem

                                            InformationTheory.Shannon.BroadcastChannel.bc_Ec_lt_of_clamped_rate

                                            source
                                            {Ijoint R₁ R₂ ε ε' : } (hgap : 0 < Ijoint - (max R₁ 0 + R₂) - 3 * ε) (hε' : 0 < ε') :
                                            ∃ (N : ), nN, (Real.exp (n * R₂)⌉₊ - 1) * Real.exp (n * R₁)⌉₊ * Real.exp (n * (-Ijoint + 3 * ε)) < ε'
                                            Used by

                                              Superposition achievability: the general forms and the degraded headline #

                                              theorem

                                              InformationTheory.Shannon.BroadcastChannel.bc_achievability_of_rate_lt

                                              source
                                              {U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pU : MeasureTheory.Measure U) [MeasureTheory.IsProbabilityMeasure pU] (K : ProbabilityTheory.Kernel U α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] (hpU : ∀ (u : U), 0 < pU.real {u}) (hK : ∀ (u : U) (a : α), 0 < (K u).real {a}) (hW : ∀ (a : α) (b : β₁ × β₂), 0 < (W a).real {b}) {R₁ R₂ : } (hR₁lt : R₁ < bcInfo₁ pU K W) (hR₂lt : R₂ < bcInfo₂ pU K W) (hJlt : max R₁ 0 + R₂ < bcInfoJoint pU K W) {ε' : } (hε' : 0 < ε') :
                                              ∃ (N : ), ∀ (n : ), N n∃ (M₁ : ) (M₂ : ) (_ : Real.exp (n * R₁)⌉₊ M₁) (_ : Real.exp (n * R₂)⌉₊ M₂) (c : BroadcastCode M₁ M₂ n α β₁ β₂), (c.averageErrorProb₁ W).toReal < ε' (c.averageErrorProb₂ W).toReal < ε'
                                              Used by
                                                theorem

                                                InformationTheory.Shannon.BroadcastChannel.bc_achievability_of_infoJoint_ge

                                                source
                                                {U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pU : MeasureTheory.Measure U) [MeasureTheory.IsProbabilityMeasure pU] (K : ProbabilityTheory.Kernel U α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] (hpU : ∀ (u : U), 0 < pU.real {u}) (hK : ∀ (u : U) (a : α), 0 < (K u).real {a}) (hW : ∀ (a : α) (b : β₁ × β₂), 0 < (W a).real {b}) (hsum : bcInfo₁ pU K W + bcInfo₂ pU K W bcInfoJoint pU K W) {R₁ R₂ : } (hR₁ : 0 < R₁) (_hR₂ : 0 < R₂) (hR₁lt : R₁ < bcInfo₁ pU K W) (hR₂lt : R₂ < bcInfo₂ pU K W) {ε' : } (hε' : 0 < ε') :
                                                ∃ (N : ), ∀ (n : ), N n∃ (M₁ : ) (M₂ : ) (_ : Real.exp (n * R₁)⌉₊ M₁) (_ : Real.exp (n * R₂)⌉₊ M₂) (c : BroadcastCode M₁ M₂ n α β₁ β₂), (c.averageErrorProb₁ W).toReal < ε' (c.averageErrorProb₂ W).toReal < ε'
                                                Used by
                                                  theorem

                                                  InformationTheory.Shannon.BroadcastChannel.bc_achievability

                                                  source
                                                  {U : Type u_1} {α : Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} [Fintype U] [DecidableEq U] [Nonempty U] [MeasurableSpace U] [MeasurableSingletonClass U] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pU : MeasureTheory.Measure U) [MeasureTheory.IsProbabilityMeasure pU] (K : ProbabilityTheory.Kernel U α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] (hpU : ∀ (u : U), 0 < pU.real {u}) (hK : ∀ (u : U) (a : α), 0 < (K u).real {a}) (hW : ∀ (a : α) (b : β₁ × β₂), 0 < (W a).real {b}) (hdeg : IsBCDegraded W) {R₁ R₂ : } (hR₁ : 0 < R₁) (_hR₂ : 0 < R₂) (hR₁lt : R₁ < bcInfo₁ pU K W) (hR₂lt : R₂ < bcInfo₂ pU K W) {ε' : } (hε' : 0 < ε') :
                                                  ∃ (N : ), ∀ (n : ), N n∃ (M₁ : ) (M₂ : ) (_ : Real.exp (n * R₁)⌉₊ M₁) (_ : Real.exp (n * R₂)⌉₊ M₂) (c : BroadcastCode M₁ M₂ n α β₁ β₂), (c.averageErrorProb₁ W).toReal < ε' (c.averageErrorProb₂ W).toReal < ε'

                                                  Achievability half of the degraded broadcast channel coding theorem, in the superposition inner-bound form of Cover–Thomas Elements of Information Theory. Over a physically degraded broadcast channel W with cloud law pU and conditional input kernel K, any rate pair strictly inside the auxiliary-variable region

                                                  • R₁ < I(X; Y₁ ∣ U) (= bcInfo₁, the strong receiver), and
                                                  • R₂ < I(U; Y₂) (= bcInfo₂, the degraded receiver)

                                                  is achievable: for all large enough block lengths n there is a BroadcastCode whose two per-receiver average error probabilities are both below any prescribed ε' > 0. The proof is the two-tier superposition random-coding argument; degradedness X → Y₁ → Y₂ is a structural precondition ensuring the receiver-1 joint-decoding rate sum is met automatically. @audit:ok

                                                  Used by