跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

Sampling a uniformly random permutation of [n][n] in parallel is a coordination problem: nn processors, one per coordinate, must output distinct values. A single round requires a shared seed of log⁡n!\log n! nats, while nn rounds require no shared randomness. We determine the tradeoff in between for RR 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 ε\varepsilon. 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 0<ε<10<\varepsilon<1 shortens the seed by O(1)O(1) nats in one round, where the least number of seed values, an approximate nonnegative tensor rank, is (1−3ε/2) n!(1-3\varepsilon/2)\,n! up to an additive two for ε≤1/2\varepsilon\le1/2. The saving is Θ((log⁡n)2)Θ((\log n)^2) nats in two rounds, with a sharp constant, and of lower order for R=o(n)R=o(n); for R∼ρnR\simρn with 0<ρ<10<ρ<1 it is linear in nn, with the optimal rate given by a variational formula. Here, errors above an explicit threshold need only o(n)o(n) 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.

AI 论文解读

基于摘要 · 非全文审阅

本文确定了并行置换采样中共享随机性与轮数之间的精确权衡,并给出了误差容忍下的种子节省量。

正在读取账号与研究记录…

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-19 01:39 · 最新观测版本

Shared Randomness and Parallel Rounds in Permutation Sampling

Sampling a uniformly random permutation of [n][n] in parallel is a coordination problem: nn processors, one per coordinate, must output distinct values. A single round requires a shared seed of log⁡n!\log n! nats, while nn rounds require no shared randomness. We determine the tradeoff in between for RR 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 ε\varepsilon. 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 0<ε<10<\varepsilon<1 shortens the seed by O(1)O(1) nats in one round, where the least number of seed values, an approximate nonnegative tensor rank, is (1−3ε/2) n!(1-3\varepsilon/2)\,n! up to an additive two for ε≤1/2\varepsilon\le1/2. The saving is Θ((log⁡n)2)Θ((\log n)^2) nats in two rounds, with a sharp constant, and of lower order for R=o(n)R=o(n); for R∼ρnR\simρn with 0<ρ<10<ρ<1 it is linear in nn, with the optimal rate given by a variational formula. Here, errors above an explicit threshold need only o(n)o(n) 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.

查看此版本解读 →查看此版本原文 ↗