Shared Randomness and Parallel Rounds in Permutation Sampling
Abstract
We study the shared randomness needed to sample a uniform permutation in parallel output rounds. Coordinates committed in the same round are independent conditional on the complete history and the current shared choice. Previous outputs are public; local computation and private randomness are free. We charge each shared choice by the logarithm of its conditional support size and sum these costs along the worst execution path. At every fixed round density ρ∈(0,1), the optimal limiting total-variation error under any o(n) shared budget matches the conditional-marginal optimum, even with arbitrary local kernels and adaptive coordination. A fixed improvement requires linear cost. For exact sampling in R=Θ(n) rounds, the optimum is nΦ(R/n)+O(log n), where Φ linearly interpolates Φ(1/q)=log q. A protocol attaining this rate uses an initial seed and at most one further binary shared choice. When ⌈ n/2⌉≤ R≤ n, the finite optimum is logbinom2(n−R)n−R, attained by an initial seed alone. The approximate converse uses an entropy inequality for sparse injections to control overlap with the target. The exact construction reuses randomness retained in a shared label partition after the first-stage outputs are exposed.
Related
- Training Parallel Speculative Draft Models by Directly Minimizing Expected Decoding Rounds
- Differentially Private Distributed Optimization via the Intrinsic Randomness of Zeroth-Order Estimators: Sampling Geometry, Convergence, and Privacy Guarantees
- Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness
- Low-rank corrections to a shared reference Jacobian for GPU-parallel AC N − 1 contingency analysis
- Randomization Beyond Deterministic Adaptivity in Parallel Sampling
BibTeX
@misc{huang2026shared,
title = {{Shared Randomness and Parallel Rounds in Permutation Sampling}},
author = {Haoxiang Huang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01028},
eprint = {2611.01028},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01028},
}
RIS
TY - UNPB
TI - Shared Randomness and Parallel Rounds in Permutation Sampling
AU - Haoxiang Huang
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01028
UR - https://arxiv.org/abs/2611.01028
AB - We study the shared randomness needed to sample a uniform permutation in parallel output rounds. Coordinates committed in the same round are independent conditional on the complete history and the current shared choice. Previous outputs are public; local computation and private randomness are free. We charge each shared choice by the logarithm of its conditional support size and sum these costs along the worst execution path. At every fixed round density ρ∈(0,1), the optimal limiting total-variation error under any o(n) shared budget matches the conditional-marginal optimum, even with arbitrary local kernels and adaptive coordination. A fixed improvement requires linear cost. For exact sampling in R=Θ(n) rounds, the optimum is nΦ(R/n)+O(log n), where Φ linearly interpolates Φ(1/q)=log q. A protocol attaining this rate uses an initial seed and at most one further binary shared choice. When ⌈ n/2⌉≤ R≤ n, the finite optimum is logbinom2(n−R)n−R, attained by an initial seed alone. The approximate converse uses an entropy inequality for sparse injections to control overlap with the target. The exact construction reuses randomness retained in a shared label partition after the first-stage outputs are exposed.
ER -