Fano Error Bounds after Finite Channels

Abstract

Finite Fano inversion and Markov data processing give estimator-error floors after arbitrary finite garbling and after explicit row-stochastic channels.

Theorem 1.1 (Markov garbling preserves the pre-channel Fano floor).

$$\begin{array}{c}\forall X,Y,Z,\\ p:X\times (Y\times Z)\to \mathbb{R},g:Z\to X,\\ ((\forall x,y,z,0\le p(x,(y,z)))\wedge \sum _{x,y,z}p(x,(y,z))=1)\wedge \\ (\forall x,y,z,p(x,(y,z))\times \mathrm{marginal}(\mathrm{yFirstLaw}(p))(y)=\mathrm{xyProjection}(p)(x,y)\times \mathrm{xzProjection}(\mathrm{yFirstLaw}(p))(y,z))\wedge \\ (\forall x,\mathrm{marginal}(p)(x)=\frac{1}{\mathrm{card}(X)})\wedge 2\le \mathrm{card}(X))\Rightarrow \\ 1-\frac{\mathrm{mutualInformation}(\mathrm{xyProjection}(p))+\log 2}{\log \mathrm{card}(X)}\le \sum _{x,z:g(z)\ne x}\mathrm{xzProjection}(p)(x,z).\end{array}$$

Proof. Machine-checked in Lean as D5/S3/Estimation/DataProcessing/FanoAfterChannel.fano_error_probability_lower_bound_of_markov (✓ std3). ∎

Source. Repository-derived.

Commentary.

Let p be a normalized nonnegative law on the right-nested product X times (Y times Z). The theorem keeps the Markov assumption in the repository’s raw cross-multiplied form: p(x,y,z) times the Y marginal equals the XY marginal times the YZ marginal. No conditional division or named Markov predicate is introduced.

The estimator sees only Z. To apply the frozen Fano endpoint, the proof swaps the XZ projection into the observation-first order Z times X. It verifies normalization after that swap, transports the uniform X marginal, and uses mutual-information symmetry to identify the swapped information term with I(X;Z).

Fano then lower-bounds the estimator’s XZ error using I(X;Z). The Markov data-processing inequality gives I(X;Z) <= I(X;Y), and positivity of log(card X), supplied exactly by 2 <= card X, makes substitution of the larger pre-garbling information budget order-correct.

Theorem 1.2 (Row-stochastic channels inherit the pre-channel Fano floor).

$$\begin{array}{c}\forall pXY,W,g,\\ ((\forall x,y,0\le pXY(x,y))\wedge \sum _{x,y}pXY(x,y)=1)\wedge \\ (\forall y,z,0\le W(y,z))\wedge (\forall y,\sum _{z}W(y,z)=1)\wedge \\ (\forall x,\mathrm{marginal}(pXY)(x)=\frac{1}{\mathrm{card}(X)})\wedge 2\le \mathrm{card}(X))\Rightarrow \\ 1-\frac{\mathrm{mutualInformation}(pXY)+\log 2}{\log \mathrm{card}(X)}\le \sum _{x,z:g(z)\ne x}\sum _{y}pXY(x,y)\times W(y,z).\end{array}$$

Proof. Machine-checked in Lean as D5/S3/Estimation/DataProcessing/FanoAfterChannel.fano_error_probability_lower_bound_after_channel (✓ std3). ∎

Source. Repository-derived.

Commentary.

The explicit channel law is p(x,y,z) = pXY(x,y) W(y,z). The input joint pXY is a normalized nonnegative law with a uniform X marginal, while W is pointwise nonnegative and every row sums to one. The estimator g is otherwise arbitrary.

Row normalization does all of the transport work. Summing the generated joint over Z recovers pXY, so the generated law has total mass one, its X marginal remains uniform, and its XY projection has exactly the pre-channel mutual information appearing in the displayed floor.

The existing channel lemma supplies the raw Markov identity for the generated joint. Applying the preceding theorem therefore bounds the error mass of every estimator based on the garbled output Z by the information available before the channel. No invertibility, positivity of individual channel entries, or estimator construction is assumed.

References

• Truth anchor: D5/S3/Estimation/DataProcessing/FanoAfterChannel.fano_error_probability_lower_bound_after_channel
• Truth anchor: D5/S3/Estimation/DataProcessing/FanoAfterChannel.fano_error_probability_lower_bound_of_markov
• Dependency: D5/S3/Entropy/MutualInformationSymm
• Dependency: D5/S3/Entropy/Submodularity/MarkovDataProcessing
• Dependency: D5/S3/Estimation/FanoErrorBound