InformationTheory

InformationTheory.Shannon.BroadcastChannel.Marton.MarkovCore.Receiver1

source

Marton's inner bound — the conditional AEP for receiver 1 #

The receiver-1 error event of the Marton ensemble opens with the transmitted auxiliary word failing to be jointly typical with the received word. The selection the encoder performs makes the law of the transmitted auxiliary word depend on the whole pair of subcodebooks, so the transmitted word is not distributed as an i.i.d. draw from the ambient and the ordinary AEP does not apply to it. What does apply is a conditional statement: for whatever auxiliary and input blocks the encoder ends up transmitting, as long as their empirical type is close to the ambient (V₁, X)-law, the channel output makes the pair (V₁, Y₁) weakly jointly typical with probability close to one.

The type closeness has to be at a radius strictly smaller than the band radius ε, because pinning the conditional mean of the log-likelihood costs a Lipschitz factor; martonStrongRadius is that smaller radius and martonBandConst the factor. Weak typicality of the transmitted blocks at radius ε is not enough: it pins an entropy alone, which leaves the conditional means free.

The type pin itself is supplied by the encoder's selection rule, which picks a strongly typical auxiliary pair. Passing that pin from the auxiliary pair to the transmitted (V₁, X) block costs one more radius separation, because the conditional mean of a letter statistic of the input is the auxiliary type averaged against the input kernel; martonCoveringRadius is the radius at which the auxiliary pair has to be pinned for the transmitted block to be pinned at martonStrongRadius.

Main definitions #

Main statements #

Coordinate laws of the Marton ambient measure — receiver 1 #

The Markov identity V₁ — X — Y₁ #

The radius separation — receiver 1 #

noncomputable def

InformationTheory.Shannon.BroadcastChannel.Marton.martonBandConst

source
{V₁ : Type u_1} {V₂ : Type u_2} {α : Type u_3} {β₁ : Type u_4} {β₂ : Type u_5} [Fintype V₁] [MeasurableSpace V₁] [MeasurableSpace V₂] [Fintype α] [MeasurableSpace α] [MeasurableSpace β₁] [MeasurableSpace β₂] (pV : MeasureTheory.Measure (V₁ × V₂)) (K : ProbabilityTheory.Kernel (V₁ × V₂) α) (W : BCChannel α β₁ β₂) :

The Lipschitz factor relating the type radius of the transmitted (V₁, X)-block to the width of the three entropy bands it has to pin. The sum runs over the whole alphabet, so letters carrying no ambient mass are budgeted for as well.

@audit:ok

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    Used by
      noncomputable def

      InformationTheory.Shannon.BroadcastChannel.Marton.martonStrongRadius

      source
      {V₁ : Type u_1} {V₂ : Type u_2} {α : Type u_3} {β₁ : Type u_4} {β₂ : Type u_5} [Fintype V₁] [MeasurableSpace V₁] [MeasurableSpace V₂] [Fintype α] [MeasurableSpace α] [MeasurableSpace β₁] [MeasurableSpace β₂] (pV : MeasureTheory.Measure (V₁ × V₂)) (K : ProbabilityTheory.Kernel (V₁ × V₂) α) (W : BCChannel α β₁ β₂) (ε : ) :

      The type radius at which the transmitted (V₁, X)-block has to be pinned for the output bands to hold at radius ε. It is a computed term of ε rather than a further parameter, so the signatures downstream carry one radius only. It is strictly smaller than ε, and its amplification by martonBandConst stays strictly inside ε/2, for every ensemble.

      @audit:ok

      Equations
      Instances For
        Used by
          theorem

          InformationTheory.Shannon.BroadcastChannel.Marton.martonStrongRadius_pos

          source
          {V₁ : Type u_1} {V₂ : Type u_2} {α : Type u_3} {β₁ : Type u_4} {β₂ : Type u_5} [Fintype V₁] [DecidableEq V₁] [Nonempty V₁] [MeasurableSpace V₁] [MeasurableSingletonClass V₁] [Fintype V₂] [DecidableEq V₂] [Nonempty V₂] [MeasurableSpace V₂] [MeasurableSingletonClass V₂] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pV : MeasureTheory.Measure (V₁ × V₂)) (K : ProbabilityTheory.Kernel (V₁ × V₂) α) (W : BCChannel α β₁ β₂) {ε : } ( : 0 < ε) :
          0 < martonStrongRadius pV K W ε
          Used by

            The three bands — receiver 1 #

            The conditional AEP — receiver 1 #

            theorem

            InformationTheory.Shannon.BroadcastChannel.Marton.marton_condAEP_jointlyTypical

            source
            {V₁ : Type u_1} {V₂ : Type u_2} {α : Type u_3} {β₁ : Type u_4} {β₂ : Type u_5} [Fintype V₁] [DecidableEq V₁] [Nonempty V₁] [MeasurableSpace V₁] [MeasurableSingletonClass V₁] [Fintype V₂] [DecidableEq V₂] [Nonempty V₂] [MeasurableSpace V₂] [MeasurableSingletonClass V₂] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pV : MeasureTheory.Measure (V₁ × V₂)) [MeasureTheory.IsProbabilityMeasure pV] (K : ProbabilityTheory.Kernel (V₁ × V₂) α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] {ε tol : } ( : 0 < ε) (htol : 0 < tol) :
            ∃ (N : ), ∀ (n : ), N n∀ (v₁ : Fin nV₁) (x : Fin nα), (fun (i : Fin n) => (v₁ i, x i)) stronglyTypicalSet (martonAmbientMeasure pV K W) (ChannelCoding.jointSequence martonV₁s martonXs) n (martonStrongRadius pV K W ε)(MeasureTheory.Measure.pi fun (i : Fin n) => W (x i)).real {y : Fin nβ₁ × β₂ | (v₁, fun (i : Fin n) => (y i).1)ChannelCoding.jointlyTypicalSet (martonAmbientMeasure pV K W) martonV₁s martonY₁s n ε} tol

            Whatever auxiliary word v₁ and input word x the encoder transmits, as long as their empirical type is pinned to the ambient (V₁, X)-law at radius martonStrongRadius, the channel output leaves the pair (v₁, y₁) outside the weakly jointly typical set with probability at most tol, for every block length past a threshold depending on ε and tol alone.

            The threshold is uniform in v₁, x and hence in the code, which is what lets the receiver-1 error decomposition consume it after the encoder's selection has already distorted the law of the transmitted words. The hypotheses on pV, K, W are the Markov-kernel regularity of the ensemble; no full-support assumption is needed. Both properties a free reference law would have to assume are structural here: it is a probability law because the ensemble is built from a probability measure and two Markov kernels, and its (V₁, X)- and (V₁, Y₁)-marginals are consistent because both are marginals of the same compProd chain. A letter of zero ambient mass therefore needs no separate treatment — it enters the type radius and the band constant like any other.

            @audit:ok

            Used by
              theorem

              InformationTheory.Shannon.BroadcastChannel.Marton.marton_strongRadius_prob_tendsto_one

              source
              {V₁ : Type u_1} {V₂ : Type u_2} {α : Type u_3} {β₁ : Type u_4} {β₂ : Type u_5} [Fintype V₁] [DecidableEq V₁] [Nonempty V₁] [MeasurableSpace V₁] [MeasurableSingletonClass V₁] [Fintype V₂] [DecidableEq V₂] [Nonempty V₂] [MeasurableSpace V₂] [MeasurableSingletonClass V₂] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pV : MeasureTheory.Measure (V₁ × V₂)) [MeasureTheory.IsProbabilityMeasure pV] (K : ProbabilityTheory.Kernel (V₁ × V₂) α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] {ε : } ( : 0 < ε) :

              The hypothesis of marton_condAEP_jointlyTypical is met by the ambient ensemble itself with probability tending to one: an i.i.d. (V₁, X)-block is type-pinned at the strong radius. This certifies that the conditional AEP is not vacuous — it is the ambient counterpart of the pinning the encoder's selection has to preserve.

              @audit:ok

              Used by
                theorem

                InformationTheory.Shannon.BroadcastChannel.Marton.marton_condAEP_jointlyTypical_ge

                source
                {V₁ : Type u_1} {V₂ : Type u_2} {α : Type u_3} {β₁ : Type u_4} {β₂ : Type u_5} [Fintype V₁] [DecidableEq V₁] [Nonempty V₁] [MeasurableSpace V₁] [MeasurableSingletonClass V₁] [Fintype V₂] [DecidableEq V₂] [Nonempty V₂] [MeasurableSpace V₂] [MeasurableSingletonClass V₂] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pV : MeasureTheory.Measure (V₁ × V₂)) [MeasureTheory.IsProbabilityMeasure pV] (K : ProbabilityTheory.Kernel (V₁ × V₂) α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] {ε tol : } ( : 0 < ε) (htol : 0 < tol) :
                ∃ (N : ), ∀ (n : ), N n∀ (v₁ : Fin nV₁) (x : Fin nα), (fun (i : Fin n) => (v₁ i, x i)) stronglyTypicalSet (martonAmbientMeasure pV K W) (ChannelCoding.jointSequence martonV₁s martonXs) n (martonStrongRadius pV K W ε)1 - tol (MeasureTheory.Measure.pi fun (i : Fin n) => W (x i)).real {y : Fin nβ₁ × β₂ | (v₁, fun (i : Fin n) => (y i).1) ChannelCoding.jointlyTypicalSet (martonAmbientMeasure pV K W) martonV₁s martonY₁s n ε}

                The complement reading of marton_condAEP_jointlyTypical.

                @audit:ok

                Used by

                  From a type-pinned auxiliary pair to a type-pinned transmitted pair — receiver 1 #

                  noncomputable def

                  InformationTheory.Shannon.BroadcastChannel.Marton.martonCoveringRadius

                  source
                  {V₁ : Type u_1} {V₂ : Type u_2} {α : Type u_3} {β₁ : Type u_4} {β₂ : Type u_5} [Fintype V₁] [MeasurableSpace V₁] [Fintype V₂] [MeasurableSpace V₂] [Fintype α] [MeasurableSpace α] [MeasurableSpace β₁] [MeasurableSpace β₂] (pV : MeasureTheory.Measure (V₁ × V₂)) (K : ProbabilityTheory.Kernel (V₁ × V₂) α) (W : BCChannel α β₁ β₂) (ε : ) :

                  The type radius at which the selected auxiliary pair has to be pinned for the transmitted (V₁, X) block to be pinned at martonStrongRadius. The two are separated by the alphabet size because the conditional mean of a letter statistic of the input is an average of the auxiliary type against the input kernel, so a type deviation of the pair is amplified by the number of auxiliary letters before it reaches the input.

                  @audit:ok

                  Equations
                  • One or more equations did not get rendered due to their size.
                  Instances For
                    Used by
                      theorem

                      InformationTheory.Shannon.BroadcastChannel.Marton.martonCoveringRadius_pos

                      source
                      {V₁ : Type u_1} {V₂ : Type u_2} {α : Type u_3} {β₁ : Type u_4} {β₂ : Type u_5} [Fintype V₁] [DecidableEq V₁] [Nonempty V₁] [MeasurableSpace V₁] [MeasurableSingletonClass V₁] [Fintype V₂] [DecidableEq V₂] [Nonempty V₂] [MeasurableSpace V₂] [MeasurableSingletonClass V₂] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pV : MeasureTheory.Measure (V₁ × V₂)) (K : ProbabilityTheory.Kernel (V₁ × V₂) α) (W : BCChannel α β₁ β₂) {ε : } ( : 0 < ε) :
                      Used by
                        theorem

                        InformationTheory.Shannon.BroadcastChannel.Marton.marton_transmitted_stronglyTypical_le

                        source
                        {V₁ : Type u_1} {V₂ : Type u_2} {α : Type u_3} {β₁ : Type u_4} {β₂ : Type u_5} [Fintype V₁] [DecidableEq V₁] [Nonempty V₁] [MeasurableSpace V₁] [MeasurableSingletonClass V₁] [Fintype V₂] [DecidableEq V₂] [Nonempty V₂] [MeasurableSpace V₂] [MeasurableSingletonClass V₂] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pV : MeasureTheory.Measure (V₁ × V₂)) [MeasureTheory.IsProbabilityMeasure pV] (K : ProbabilityTheory.Kernel (V₁ × V₂) α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] {ε tol : } ( : 0 < ε) (htol : 0 < tol) :
                        ∃ (N : ), ∀ (n : ), N n∀ (v₁ : Fin nV₁) (v₂ : Fin nV₂), (v₁, v₂) jointStronglyTypicalSet (martonAmbientMeasure pV K W) martonV₁s martonV₂s n (martonCoveringRadius pV K W ε)(MeasureTheory.Measure.pi fun (i : Fin n) => K (v₁ i, v₂ i)).real {x : Fin nα | (fun (i : Fin n) => (v₁ i, x i))stronglyTypicalSet (martonAmbientMeasure pV K W) (ChannelCoding.jointSequence martonV₁s martonXs) n (martonStrongRadius pV K W ε)} tol

                        The transmitted (V₁, X) block inherits the type pin of the selected auxiliary pair: drawing the input word letterwise from K applied to a pair whose joint type is pinned at martonCoveringRadius leaves the pair (v₁, x) outside the strongly typical set of radius martonStrongRadius with probability at most tol, uniformly in the selected pair.

                        The pin the hypothesis supplies is the full empirical type of the pair, which is finer than the (V₁, X)-type the conclusion pins, and the ambient ensemble meets it with probability tending to one at every positive radius, so the statement is not vacuous.

                        @audit:ok

                        Used by
                          theorem

                          InformationTheory.Shannon.BroadcastChannel.Marton.marton_condAEP_selected_avg_le

                          source
                          {V₁ : Type u_1} {V₂ : Type u_2} {α : Type u_3} {β₁ : Type u_4} {β₂ : Type u_5} [Fintype V₁] [DecidableEq V₁] [Nonempty V₁] [MeasurableSpace V₁] [MeasurableSingletonClass V₁] [Fintype V₂] [DecidableEq V₂] [Nonempty V₂] [MeasurableSpace V₂] [MeasurableSingletonClass V₂] [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β₁] [DecidableEq β₁] [Nonempty β₁] [MeasurableSpace β₁] [MeasurableSingletonClass β₁] [Fintype β₂] [DecidableEq β₂] [Nonempty β₂] [MeasurableSpace β₂] [MeasurableSingletonClass β₂] (pV : MeasureTheory.Measure (V₁ × V₂)) [MeasureTheory.IsProbabilityMeasure pV] (K : ProbabilityTheory.Kernel (V₁ × V₂) α) [ProbabilityTheory.IsMarkovKernel K] (W : BCChannel α β₁ β₂) [ProbabilityTheory.IsMarkovKernel W] {ε tol : } ( : 0 < ε) (htol : 0 < tol) :
                          ∃ (N : ), ∀ (n : ), N n∀ (v₁ : Fin nV₁) (v₂ : Fin nV₂), (v₁, v₂) jointStronglyTypicalSet (martonAmbientMeasure pV K W) martonV₁s martonV₂s n (martonCoveringRadius pV K W ε)x : Fin nα, (MeasureTheory.Measure.pi fun (i : Fin n) => K (v₁ i, v₂ i)).real {x} * (MeasureTheory.Measure.pi fun (i : Fin n) => W (x i)).real {y : Fin nβ₁ × β₂ | (v₁, fun (i : Fin n) => (y i).1)ChannelCoding.jointlyTypicalSet (martonAmbientMeasure pV K W) martonV₁s martonY₁s n ε} tol

                          The receiver-1 error term of a selected auxiliary pair, averaged over the input tier: whatever type-pinned pair the encoder selects, drawing the input word from K and passing it through the channel leaves (v₁, y₁) outside the weakly jointly typical set with probability at most tol.

                          This is the form the error decomposition of Marton.ErrorAnalysis consumes, since the threshold is uniform in the selected pair and hence in the code.

                          @audit:ok

                          Used by