Manuscript Psy04-B@1 · Psy04-B-v1.tex · lemma · 62c2b6f0
Lemma: Deterministic-table reduction
The sharp classical benchmark on the cut · lines 840–861 · proof included or linked
Psy04-B@1#lem:tables
Every finite-alphabet law of the form (eq:classicalfactor) is a mixture of deterministic encoding and decoding tables with mixture randomness independent of .
Proof. Condition on . Before the fresh input is used, sample an encoding-table entry for every possible according to , and a decoding-table entry for every possible according to . Use independent table samples conditional on .
Each table realization is deterministic. Averaging its entries reproduces the two kernels and their composition. Average also over .
Nearby in this section
- section: The sharp classical benchmark on the cut
- section: The sharp classical benchmark on the cut
- theorem: Theorem: Sharp two-state classical bound
- section: The sharp classical benchmark on the cut
- proposition: Proposition: Storage processing cannot improve a fixed classical encoder's optimum
- section: The sharp classical benchmark on the cut