Lemma. A simultaneous finite partition bound [ftip-009C]
✍️source

    Let \(Q,H\) be nonempty finite sets with \(N=|Q|\) and \(r=|H|\), and let \(\mathfrak E\subseteq H^Q\) be nonempty and finite with \(p=|\mathfrak E|\). For every integer \(k\geq 1\), there is a map \(f:Q\to [k]\) such that, simultaneously for every \(e\in \mathfrak E\),

    \[ \begin {aligned} \sum _{z\in H}\max _{j\in [k]}X_{z,j}&\leq \frac Nk+D,\\ \sum _{z\in H}\min _{j\in [k]}X_{z,j}&\geq \frac Nk-D, \end {aligned} \]

    where \([k]=\{1,\ldots ,k\}\), logarithms are natural, and

    \[ X_{z,j}=|\{q\in Q:e(q)=z,\ f(q)=j\}|, \qquad D=\sqrt {Nr}+\sqrt {\frac N2\log (4p)}. \]

    Proof. 

      Choose the labels \(f(q)\) independently and uniformly from \([k]\). Fix \(e,z\), write \(n_z=|e^{-1}(z)|\), and put \(a_j=X_{z,j}-n_z/k\). Each occupancy has variance \(n_z(1/k)(1-1/k)\), so

      \[\mathbb E\sum _{j=1}^k a_j^2=n_z(1-1/k).\]

      The pointwise maximum and minimum satisfy

      \[ \begin {aligned} \max _jX_{z,j}&\leq n_z/k+\|a\|_2,\\ \min _jX_{z,j}&\geq n_z/k-\|a\|_2. \end {aligned} \]

      Jensen's inequality gives \(\mathbb E\|a\|_2\leq \sqrt {n_z(1-1/k)}\). Summing over \(z\) and applying Cauchy--Schwarz yields

      \[ \begin {aligned} \mathbb E\sum _z\max _jX_{z,j}&\leq N/k+\sqrt {Nr(1-1/k)},\\ \mathbb E\sum _z\min _jX_{z,j}&\geq N/k-\sqrt {Nr(1-1/k)}. \end {aligned} \]

      Changing one label changes only one representation group: one occupancy decreases by one and another increases by one. Its maximum and its minimum each change by at most one. Thus both sums have bounded differences with all \(N\) constants equal to one. McDiarmid's inequality, also used in Appendix A.1 of The limits of preference data for post-training[zhao2025limits], bounds each relevant one-sided deviation of size \(t\) by \(\exp (-2t^2/N)\).

      Choose \(t=\sqrt {(N/2)\log (4p)}\). A union bound over both tails and all \(p\) representations gives total failure probability at most

      \[2p\exp (-2t^2/N)=\frac 12<1.\]

      At least one deterministic labeling satisfies both claimed bounds, since \(\sqrt {Nr(1-1/k)}\leq \sqrt {Nr}\). Empty representation fibers have all occupancies zero and require no exception.

      The bound uses a second-moment estimate in place of the occupancy estimate in source Lemma A.2. The chosen labeling depends only on \(Q,H,\mathfrak E,k\); its existence uses proof randomness and does not assume randomness in the learning algorithm.