InformationTheory

InformationTheory.Shannon.MultipleAccess.TimeSharingConverse.Assembly

source

Multiple access channel — time-sharing converse and the capacity region #

The converse-half headline mac_timesharing_converse: an achievable rate pair in the first quadrant lies in the closed convex hull of the union of all per-input pentagons. Assembled from the Fano → 0 weak-converse limit, the uniformly-shrunk rate-point construction, and the axis casework, on top of the geometric gateway and measure bridge in TimeSharingConverse.Bridge.

Pairing that converse with the achievability half mac_achievability_region_allprob gives the headline mac_timesharing_capacity_region: for a channel with strictly positive transition probabilities, the operational capacity region intersected with the first quadrant equals that closed convex hull. Rate pairs with a negative coordinate are folded back onto the axes by mac_achievable_clamp_iff, so the converse only ever has to see first-quadrant pairs.

Converse assembly: Fano → 0 limit, point construction, axis casework #

The converse-half headline mac_timesharing_converse. An achievable rate pair (R₁, R₂) in the first quadrant lies in the closed convex hull of the union of all per-input pentagons. The core is the interior case 0 < R₁, 0 < R₂: for a sequence of block codes with error → 0 and length → ∞, the uniformly-shrunk rate point (R₁(1−Pe) − log2/n, R₂(1−Pe) − log2/n) lies in the hull (per-code, via the geometric gateway mac_avgPentagon_mem_convexHull), and converges to (R₁, R₂), which is therefore in the closed hull.

theorem

InformationTheory.Shannon.MAC.mac_perletter_superadd

source
{α₁ : Type u_1} {α₂ : Type u_2} {β : Type u_3} [Fintype α₁] [DecidableEq α₁] [Nonempty α₁] [MeasurableSpace α₁] [MeasurableSingletonClass α₁] [StandardBorelSpace α₁] [Fintype α₂] [DecidableEq α₂] [Nonempty α₂] [MeasurableSpace α₂] [MeasurableSingletonClass α₂] [StandardBorelSpace α₂] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] [StandardBorelSpace β] (p₁ : MeasureTheory.Measure α₁) [MeasureTheory.IsProbabilityMeasure p₁] (p₂ : MeasureTheory.Measure α₂) [MeasureTheory.IsProbabilityMeasure p₂] (W : MACChannel α₁ α₂ β) [ProbabilityTheory.IsMarkovKernel W] :
macInfoBoth p₁ p₂ W macInfo₁ p₁ p₂ W + macInfo₂ p₁ p₂ W

Per-letter mutual-information superadditivity under input independence: I((X₁, X₂); Y) ≤ I(X₁; Y | X₂) + I(X₂; Y | X₁). This is the hsub well-formedness hypothesis of mac_avgPentagon_mem_convexHull; it is a universal geometric fact about the product input, threaded here exactly like the existing hac/hbc corners mac_macInfo₁/₂_le_macInfoBoth. Proved by the two chain-rule decompositions I((X₁, X₂); Y) = I(X₂; Y) + I(X₁; Y | X₂) and the identity I(X₂; Y | X₁) = I(X₂; Y) + I(X₁; X₂ | Y) (the I(X₁; X₂) = 0 term drops under the independent product input), so I(X₂; Y) ≤ I(X₂; Y | X₁) and the claim follows.

Used by
    theorem

    InformationTheory.Shannon.MAC.mac_converse_rate_mul_one_sub_errorProb_mem_of_ceil_exp_le

    source
    {α₁ : Type u_1} {α₂ : Type u_2} {β : Type u_3} [Fintype α₁] [DecidableEq α₁] [Nonempty α₁] [MeasurableSpace α₁] [MeasurableSingletonClass α₁] [StandardBorelSpace α₁] [Fintype α₂] [DecidableEq α₂] [Nonempty α₂] [MeasurableSpace α₂] [MeasurableSingletonClass α₂] [StandardBorelSpace α₂] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] [StandardBorelSpace β] {M₁ M₂ n : } (c : MACCode M₁ M₂ n α₁ α₂ β) (W : MACChannel α₁ α₂ β) [ProbabilityTheory.IsMarkovKernel W] (hn : 0 < n) (hcard₁ : 2 M₁) (hcard₂ : 2 M₂) {R₁ R₂ : } (hR₁ : 0 R₁) (hR₂ : 0 R₂) (hM₁ : Real.exp (n * R₁)⌉₊ M₁) (hM₂ : Real.exp (n * R₂)⌉₊ M₂) (hx1 : 0 R₁ * (1 - (c.averageErrorProb W).toReal) - Real.log 2 / n) (hx2 : 0 R₂ * (1 - (c.averageErrorProb W).toReal) - Real.log 2 / n) :
    (R₁ * (1 - (c.averageErrorProb W).toReal) - Real.log 2 / n, R₂ * (1 - (c.averageErrorProb W).toReal) - Real.log 2 / n) (closedConvexHull ) (⋃ (p₁ : MeasureTheory.Measure α₁), ⋃ (p₂ : MeasureTheory.Measure α₂), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₁), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₂), macPentagon p₁ p₂ W)

    Membership of the shrunk rate point of a single code: for a length-n two-user code with 2 ≤ M₁, 2 ≤ M₂ and ⌈exp (n Rⱼ)⌉ ≤ Mⱼ, if the uniformly-shrunk rate point (R₁(1−Pe) − log2/n, R₂(1−Pe) − log2/n) (with Pe the average error probability) is in the first quadrant, then it lies in the closed convex hull of all per-input pentagons. Combines the finite-n Fano bounds with the geometric gateway mac_avgPentagon_mem_convexHull and the per-letter identifications mac_condMI_eq_macInfo₁_at and friends.

    Used by
      theorem

      InformationTheory.Shannon.MAC.mac_timesharing_converse_interior

      source
      {α₁ : Type u_1} {α₂ : Type u_2} {β : Type u_3} [Fintype α₁] [DecidableEq α₁] [Nonempty α₁] [MeasurableSpace α₁] [MeasurableSingletonClass α₁] [StandardBorelSpace α₁] [Fintype α₂] [DecidableEq α₂] [Nonempty α₂] [MeasurableSpace α₂] [MeasurableSingletonClass α₂] [StandardBorelSpace α₂] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] [StandardBorelSpace β] (W : MACChannel α₁ α₂ β) [ProbabilityTheory.IsMarkovKernel W] {R₁ R₂ : } (hR₁ : 0 < R₁) (hR₂ : 0 < R₂) (hach : MACAchievable W R₁ R₂) :
      (R₁, R₂) (closedConvexHull ) (⋃ (p₁ : MeasureTheory.Measure α₁), ⋃ (p₂ : MeasureTheory.Measure α₂), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₁), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₂), macPentagon p₁ p₂ W)

      Interior case of the converse: for strictly positive rates, an achievable pair lies in the closed convex hull of the per-input pentagons.

      Used by
        theorem

        InformationTheory.Shannon.MAC.mac_converse_from_code_bound₁

        source
        {α₁ : Type u_1} {α₂ : Type u_2} {β : Type u_3} [Fintype α₁] [DecidableEq α₁] [Nonempty α₁] [MeasurableSpace α₁] [MeasurableSingletonClass α₁] [StandardBorelSpace α₁] [Fintype α₂] [DecidableEq α₂] [Nonempty α₂] [MeasurableSpace α₂] [MeasurableSingletonClass α₂] [StandardBorelSpace α₂] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] [StandardBorelSpace β] {M₁ M₂ n : } [NeZero M₁] [NeZero M₂] (c : MACCode M₁ M₂ n α₁ α₂ β) (W : MACChannel α₁ α₂ β) [ProbabilityTheory.IsMarkovKernel W] (hcard₁ : 2 M₁) :
        Real.log M₁ (∑ i : Fin n, condMutualInfo (macConverseAmbient c W) (fun (ω : (Fin M₁ × Fin M₂) × (Fin nβ)) => c.encoder₁ (macConverseMsg₁ ω) i) (macConverseYs i) fun (ω : (Fin M₁ × Fin M₂) × (Fin nβ)) => c.encoder₂ (macConverseMsg₂ ω) i).toReal + Real.binEntropy (MeasureFano.errorProb (macConverseAmbient c W) macConverseMsg₁ (fun (ω : (Fin M₁ × Fin M₂) × (Fin nβ)) => (macConverseMsg₂ ω, fun (i : Fin n) => macConverseYs i ω)) fun (p : Fin M₂ × (Fin nβ)) => (c.decoder p.2).1) + (MeasureFano.errorProb (macConverseAmbient c W) macConverseMsg₁ (fun (ω : (Fin M₁ × Fin M₂) × (Fin nβ)) => (macConverseMsg₂ ω, fun (i : Fin n) => macConverseYs i ω)) fun (p : Fin M₂ × (Fin nβ)) => (c.decoder p.2).1) * Real.log (M₁ - 1)

        Finite-n Fano corner bound for user 1: the single user-1 corner inequality log |M₁| ≤ ∑ᵢ I(X₁ᵢ; Yᵢ | X₂ᵢ) + h(Pe₁) + Pe₁ log(|M₁| − 1), obtained directly from mac_converse_bound₁ and mac_singleletterize_bound₁ on the canonical ambient measure, without routing through the two-user mac_converse_from_code. Requires only 2 ≤ M₁; user 2 enters only through NeZero M₂, so this survives the M₂ = 1 axis degeneracy that blocks the joint converse.

        Used by
          theorem

          InformationTheory.Shannon.MAC.mac_converse_from_code_bound₂

          source
          {α₁ : Type u_1} {α₂ : Type u_2} {β : Type u_3} [Fintype α₁] [DecidableEq α₁] [Nonempty α₁] [MeasurableSpace α₁] [MeasurableSingletonClass α₁] [StandardBorelSpace α₁] [Fintype α₂] [DecidableEq α₂] [Nonempty α₂] [MeasurableSpace α₂] [MeasurableSingletonClass α₂] [StandardBorelSpace α₂] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] [StandardBorelSpace β] {M₁ M₂ n : } [NeZero M₁] [NeZero M₂] (c : MACCode M₁ M₂ n α₁ α₂ β) (W : MACChannel α₁ α₂ β) [ProbabilityTheory.IsMarkovKernel W] (hcard₂ : 2 M₂) :
          Real.log M₂ (∑ i : Fin n, condMutualInfo (macConverseAmbient c W) (fun (ω : (Fin M₁ × Fin M₂) × (Fin nβ)) => c.encoder₂ (macConverseMsg₂ ω) i) (macConverseYs i) fun (ω : (Fin M₁ × Fin M₂) × (Fin nβ)) => c.encoder₁ (macConverseMsg₁ ω) i).toReal + Real.binEntropy (MeasureFano.errorProb (macConverseAmbient c W) macConverseMsg₂ (fun (ω : (Fin M₁ × Fin M₂) × (Fin nβ)) => (macConverseMsg₁ ω, fun (i : Fin n) => macConverseYs i ω)) fun (p : Fin M₁ × (Fin nβ)) => (c.decoder p.2).2) + (MeasureFano.errorProb (macConverseAmbient c W) macConverseMsg₂ (fun (ω : (Fin M₁ × Fin M₂) × (Fin nβ)) => (macConverseMsg₁ ω, fun (i : Fin n) => macConverseYs i ω)) fun (p : Fin M₁ × (Fin nβ)) => (c.decoder p.2).2) * Real.log (M₂ - 1)

          Finite-n Fano corner bound for user 2, symmetric to mac_converse_from_code_bound₁: requires only 2 ≤ M₂, surviving the M₁ = 1 axis degeneracy.

          Used by
            theorem

            InformationTheory.Shannon.MAC.mac_converse_rate₁_mul_one_sub_errorProb_mem_of_ceil_exp_le

            source
            {α₁ : Type u_1} {α₂ : Type u_2} {β : Type u_3} [Fintype α₁] [DecidableEq α₁] [Nonempty α₁] [MeasurableSpace α₁] [MeasurableSingletonClass α₁] [StandardBorelSpace α₁] [Fintype α₂] [DecidableEq α₂] [Nonempty α₂] [MeasurableSpace α₂] [MeasurableSingletonClass α₂] [StandardBorelSpace α₂] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] [StandardBorelSpace β] {M₁ M₂ n : } [NeZero M₂] (c : MACCode M₁ M₂ n α₁ α₂ β) (W : MACChannel α₁ α₂ β) [ProbabilityTheory.IsMarkovKernel W] (hn : 0 < n) (hcard₁ : 2 M₁) {R₁ : } (hR₁ : 0 R₁) (hM₁ : Real.exp (n * R₁)⌉₊ M₁) (hx1 : 0 R₁ * (1 - (c.averageErrorProb W).toReal) - Real.log 2 / n) :
            (R₁ * (1 - (c.averageErrorProb W).toReal) - Real.log 2 / n, 0) (closedConvexHull ) (⋃ (p₁ : MeasureTheory.Measure α₁), ⋃ (p₂ : MeasureTheory.Measure α₂), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₁), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₂), macPentagon p₁ p₂ W)

            Membership of the shrunk rate point when user 2 is silent (R₂ = 0): the analogue of mac_converse_rate_mul_one_sub_errorProb_mem_of_ceil_exp_le for the point (R₁(1−Pe) − log2/n, 0), which uses only the user-1 Fano bound (mac_converse_from_code_bound₁, needing just 2 ≤ M₁) plus per-letter nonnegativity, so it survives the M₂ = 1 degeneracy.

            Used by
              theorem

              InformationTheory.Shannon.MAC.mac_converse_rate₂_mul_one_sub_errorProb_mem_of_ceil_exp_le

              source
              {α₁ : Type u_1} {α₂ : Type u_2} {β : Type u_3} [Fintype α₁] [DecidableEq α₁] [Nonempty α₁] [MeasurableSpace α₁] [MeasurableSingletonClass α₁] [StandardBorelSpace α₁] [Fintype α₂] [DecidableEq α₂] [Nonempty α₂] [MeasurableSpace α₂] [MeasurableSingletonClass α₂] [StandardBorelSpace α₂] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] [StandardBorelSpace β] {M₁ M₂ n : } [NeZero M₁] (c : MACCode M₁ M₂ n α₁ α₂ β) (W : MACChannel α₁ α₂ β) [ProbabilityTheory.IsMarkovKernel W] (hn : 0 < n) (hcard₂ : 2 M₂) {R₂ : } (hR₂ : 0 R₂) (hM₂ : Real.exp (n * R₂)⌉₊ M₂) (hx2 : 0 R₂ * (1 - (c.averageErrorProb W).toReal) - Real.log 2 / n) :
              (0, R₂ * (1 - (c.averageErrorProb W).toReal) - Real.log 2 / n) (closedConvexHull ) (⋃ (p₁ : MeasureTheory.Measure α₁), ⋃ (p₂ : MeasureTheory.Measure α₂), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₁), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₂), macPentagon p₁ p₂ W)

              Membership of the shrunk rate point when user 1 is silent (R₁ = 0), symmetric to mac_converse_rate₁_mul_one_sub_errorProb_mem_of_ceil_exp_le.

              Used by
                theorem

                InformationTheory.Shannon.MAC.mac_timesharing_converse_rate₁

                source
                {α₁ : Type u_1} {α₂ : Type u_2} {β : Type u_3} [Fintype α₁] [DecidableEq α₁] [Nonempty α₁] [MeasurableSpace α₁] [MeasurableSingletonClass α₁] [StandardBorelSpace α₁] [Fintype α₂] [DecidableEq α₂] [Nonempty α₂] [MeasurableSpace α₂] [MeasurableSingletonClass α₂] [StandardBorelSpace α₂] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] [StandardBorelSpace β] (W : MACChannel α₁ α₂ β) [ProbabilityTheory.IsMarkovKernel W] {R₁ : } (hR₁ : 0 < R₁) (hach : MACAchievable W R₁ 0) :
                (R₁, 0) (closedConvexHull ) (⋃ (p₁ : MeasureTheory.Measure α₁), ⋃ (p₂ : MeasureTheory.Measure α₂), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₁), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₂), macPentagon p₁ p₂ W)

                Converse on the single-user axis with user 2 silent: for a strictly positive rate R₁ achievable with R₂ = 0, the pair (R₁, 0) lies in the closed convex hull of the per-input pentagons. Uses the user-1-only finite-n Fano bound mac_converse_from_code_bound₁ (which needs only 2 ≤ M₁, and thus survives the M₂ = 1 degeneracy of the axis), then takes the Fano → 0 limit as in the interior case.

                Used by
                  theorem

                  InformationTheory.Shannon.MAC.mac_timesharing_converse_rate₂

                  source
                  {α₁ : Type u_1} {α₂ : Type u_2} {β : Type u_3} [Fintype α₁] [DecidableEq α₁] [Nonempty α₁] [MeasurableSpace α₁] [MeasurableSingletonClass α₁] [StandardBorelSpace α₁] [Fintype α₂] [DecidableEq α₂] [Nonempty α₂] [MeasurableSpace α₂] [MeasurableSingletonClass α₂] [StandardBorelSpace α₂] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] [StandardBorelSpace β] (W : MACChannel α₁ α₂ β) [ProbabilityTheory.IsMarkovKernel W] {R₂ : } (hR₂ : 0 < R₂) (hach : MACAchievable W 0 R₂) :
                  (0, R₂) (closedConvexHull ) (⋃ (p₁ : MeasureTheory.Measure α₁), ⋃ (p₂ : MeasureTheory.Measure α₂), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₁), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₂), macPentagon p₁ p₂ W)

                  Converse on the single-user axis with user 1 silent, symmetric to mac_timesharing_converse_rate₁: uses the user-2-only finite-n Fano bound mac_converse_from_code_bound₂ (needing only 2 ≤ M₂, surviving the M₁ = 1 degeneracy), then takes the Fano → 0 limit.

                  Used by
                    theorem

                    InformationTheory.Shannon.MAC.mac_timesharing_converse

                    source
                    {α₁ : Type u_1} {α₂ : Type u_2} {β : Type u_3} [Fintype α₁] [DecidableEq α₁] [Nonempty α₁] [MeasurableSpace α₁] [MeasurableSingletonClass α₁] [StandardBorelSpace α₁] [Fintype α₂] [DecidableEq α₂] [Nonempty α₂] [MeasurableSpace α₂] [MeasurableSingletonClass α₂] [StandardBorelSpace α₂] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] [StandardBorelSpace β] (W : MACChannel α₁ α₂ β) [ProbabilityTheory.IsMarkovKernel W] :
                    {p : × | MACAchievable W p.1 p.2 0 p.1 0 p.2} (closedConvexHull ) (⋃ (p₁ : MeasureTheory.Measure α₁), ⋃ (p₂ : MeasureTheory.Measure α₂), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₁), ⋃ (_ : MeasureTheory.IsProbabilityMeasure p₂), macPentagon p₁ p₂ W)

                    Time-sharing converse for the MAC: every achievable first-quadrant rate pair lies in the closed convex hull of the union of all per-input pentagons macPentagon p₁ p₂ W over probability inputs p₁, p₂. Assembled by casework on whether each rate is zero or positive: the interior case uses the Fano → 0 limit mac_timesharing_converse_interior, the origin (0,0) lies in any pentagon, and the two axis cases reduce to the single-user Fano corner via mac_timesharing_converse_rate₁ and mac_timesharing_converse_rate₂.

                    Used by

                      Capacity region: converse and achievability combined #

                      The headline mac_timesharing_capacity_region. Achievability contributes the inclusion of the closed convex hull in the capacity region; the converse contributes the reverse inclusion on the first quadrant, extended to the whole region by the clamping equivalence mac_achievable_clamp_iff, which lets a rate pair with a negative coordinate be replaced by its projection onto the axes without changing achievability.

                      theorem

                      InformationTheory.Shannon.MAC.mac_achievable_clamp_iff

                      source
                      {α₁ : Type u_1} {α₂ : Type u_2} {β : Type u_3} [MeasurableSpace α₁] [MeasurableSpace α₂] [MeasurableSpace β] (W : MACChannel α₁ α₂ β) (R₁ R₂ : ) :
                      MACAchievable W R₁ R₂ MACAchievable W (max R₁ 0) (max R₂ 0)

                      Clamping a rate pair into the first quadrant does not change achievability. MACAchievable depends on the rates R₁, R₂ only through the message-count thresholds ⌈exp (n Rⱼ)⌉ ≤ Mⱼ, and ⌈exp (n R)⌉ = ⌈exp (n (max R 0))⌉ for every block length n (for R < 0 both ceilings equal 1, since exp (n R) ∈ (0, 1]). This lets the antisymmetry argument fold a negative achievable rate back onto the axis.

                      Used by
                        theorem

                        InformationTheory.Shannon.MAC.mac_timesharing_capacity_region

                        source
                        {α₁ : Type u_1} {α₂ : Type u_2} {β : Type u_3} [Fintype α₁] [DecidableEq α₁] [Nonempty α₁] [MeasurableSpace α₁] [MeasurableSingletonClass α₁] [StandardBorelSpace α₁] [Fintype α₂] [DecidableEq α₂] [Nonempty α₂] [MeasurableSpace α₂] [MeasurableSingletonClass α₂] [StandardBorelSpace α₂] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] [StandardBorelSpace β] (W : MACChannel α₁ α₂ β) [ProbabilityTheory.IsMarkovKernel W] (hW : ∀ (a : α₁ × α₂) (b : β), 0 < (W a).real {b}) :

                        Full first-quadrant characterization of the MAC capacity region (Cover–Thomas): for a channel whose transition probabilities are all strictly positive, the operational capacity region, intersected with the first quadrant, equals the closed convex hull of the union of all per-input pentagons macPentagon p₁ p₂ W over probability inputs p₁, p₂. The half is the converse (mac_timesharing_converse, with negative rates clamped back to the axis via mac_achievable_clamp_iff); the half is achievability (mac_achievability_region_allprob, whose pentagons already lie in the first quadrant).

                        Used by