Certifying Shared Gumbel Couplings: Geometry, Query Complexity, and Marginal Error

Correct categorical marginals do not determine a sampler's coupling across inputs. We study certification of the shared Gumbel coupling through categorical queries to reusable hidden seeds. Certificates must be valid for every sampler satisfying a marginal promise, while being efficient under the Gumbel reference. For full-support targets on $n\ge 3$ labels, we characterize exactly when a fixed finite input family permits inverse-accuracy certification: the ordered ratios $r_i=q_i/p_i$ must satisfy $r_{(2)}=r_{(n-1)}$. At most three inputs then suffice. Otherwise, every fixed finite family has inverse-square complexity, but accuracy-dependent queries are faster. For fixed $n\ge 4$ and distinct targets bounded away from zero, the uniform optimal order is $\log (1/\delta )[{\rho }^{-1}+D{\rho }^{-4/3}]$, where $D=\log (r_{(n-1)}/r_{(2)})$. The order simultaneously characterizes reference expected seeds, reference expected calls, and an all-sampler deterministic call budget; lower bounds allow adaptation and stopping. We also characterize the marginal-tolerance transition for each fixed pair with $D>0$. Exact finite-law experiments expose both the advantage of affine certificates at the reference and their conservatism under auxiliary misspecification. Deterministic quadrature verifies the local variance mechanism, without claiming an end-to-end implementation of the general minimax construction.