Lemma: Randomized strategies are mixtures of deterministic tables

For finite input, memory, query, and answer alphabets, every law of the form (eq:classicalfactor) is a mixture of deterministic encoding and decoding strategies, with mixture randomness independent of $X,J$.

Consequently a score upper bound valid for every deterministic strategy is valid for arbitrary local and shared randomness in the admitted class.

Proof. Condition first on $\lambda$. For each possible input $x$, independently sample an encoding-table entry from $a_{\lambda }(\cdot \mid x)$. For each possible pair $(m,j)$, independently sample a decoding-table entry from $d_{\lambda }(\cdot \mid m,j)$. Sample these complete tables before the fresh input is used.

Each realization gives deterministic functions

Averaging the table entries reproduces the two kernels and their composed law. Average also over $\lambda$.

The expected score of a mixture is the mixture of its expected scores. It cannot exceed a common deterministic upper bound.