← 研踪 PaperTrailarXiv:2611.01028 · v2
Shared Randomness and Parallel Rounds in Permutation Sampling
置换采样中的共享随机性与并行轮数
首次提交 2026-10-31 23:14
版本更新 2026-11-19 01:39
雷达观测 2026-11-19 15:04
摘要
Sampling a uniformly random permutation of in parallel is a coordination problem: processors, one per coordinate, must output distinct values. A single round requires a shared seed of nats, while rounds require no shared randomness. We determine the tradeoff in between for rounds, in which the values of each round are written independently given the shared randomness and the earlier output, and the output must be a uniform permutation, exactly or within total-variation error . Shared randomness is measured by its support size or by its entropy, and it is either fixed in advance or drawn adaptively during the execution. For exact sampling, all four costs equal one explicit combinatorial quantity up to an absolute additive constant. A fixed error shortens the seed by nats in one round, where the least number of seed values, an approximate nonnegative tensor rank, is up to an additive two for . The saving is nats in two rounds, with a sharp constant, and of lower order for ; for with it is linear in , with the optimal rate given by a variational formula. Here, errors above an explicit threshold need only nats, and at every positive error below it, shared randomness drawn adaptively has strictly smaller entropy than a seed fixed in advance. A central tool is a change of measure that turns lower bounds with error into entropy bounds for a single batch of distinct, nearly independent values. The results for sublinearly and linearly many rounds extend to sampling without replacement.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-19 01:39 · 最新观测版本
Shared Randomness and Parallel Rounds in Permutation Sampling
Sampling a uniformly random permutation of in parallel is a coordination problem: processors, one per coordinate, must output distinct values. A single round requires a shared seed of nats, while rounds require no shared randomness. We determine the tradeoff in between for rounds, in which the values of each round are written independently given the shared randomness and the earlier output, and the output must be a uniform permutation, exactly or within total-variation error . Shared randomness is measured by its support size or by its entropy, and it is either fixed in advance or drawn adaptively during the execution. For exact sampling, all four costs equal one explicit combinatorial quantity up to an absolute additive constant. A fixed error shortens the seed by nats in one round, where the least number of seed values, an approximate nonnegative tensor rank, is up to an additive two for . The saving is nats in two rounds, with a sharp constant, and of lower order for ; for with it is linear in , with the optimal rate given by a variational formula. Here, errors above an explicit threshold need only nats, and at every positive error below it, shared randomness drawn adaptively has strictly smaller entropy than a seed fixed in advance. A central tool is a change of measure that turns lower bounds with error into entropy bounds for a single batch of distinct, nearly independent values. The results for sublinearly and linearly many rounds extend to sampling without replacement.
查看此版本解读 →查看此版本原文 ↗