InformationTheory.Shannon.MultipleAccess.TimeSharingConverse.Assembly
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.
InformationTheory.Shannon.MAC.mac_perletter_superadd
sourcePer-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
InformationTheory.Shannon.MAC.mac_converse_rate_mul_one_sub_errorProb_mem_of_ceil_exp_le
sourceMembership 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
InformationTheory.Shannon.MAC.mac_timesharing_converse_interior
sourceInterior case of the converse: for strictly positive rates, an achievable pair lies in the closed convex hull of the per-input pentagons.
Used by
InformationTheory.Shannon.MAC.mac_converse_from_code_bound₁
sourceFinite-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
InformationTheory.Shannon.MAC.mac_converse_from_code_bound₂
sourceFinite-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
InformationTheory.Shannon.MAC.mac_converse_rate₁_mul_one_sub_errorProb_mem_of_ceil_exp_le
sourceMembership 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
InformationTheory.Shannon.MAC.mac_converse_rate₂_mul_one_sub_errorProb_mem_of_ceil_exp_le
sourceMembership 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
InformationTheory.Shannon.MAC.mac_timesharing_converse_rate₁
sourceConverse 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
InformationTheory.Shannon.MAC.mac_timesharing_converse_rate₂
sourceConverse 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
InformationTheory.Shannon.MAC.mac_timesharing_converse
sourceTime-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.
InformationTheory.Shannon.MAC.mac_achievable_clamp_iff
sourceClamping 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
InformationTheory.Shannon.MAC.mac_timesharing_capacity_region
sourceFull 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).