AI & ML
Shared Randomness and Parallel Rounds in Permutation Sampling
arXiv math.IT0 views
arXiv:2611.01028v2 Announce Type: replace Abstract: Sampling a uniformly random permutation of $[n]$ in parallel is a coordination problem: $n$ processors, one per coordinate, must output distinct values. A single round requires a shared seed of $\log n!$ nats, while $n$ rounds require no shared randomness. We determine the tradeoff in between for $R$ 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<\varepsilon<1$ shortens the seed by $O(1)$ nats in one round, where the least number of seed values, an approximate nonnegative tensor rank, is $(1-3\varepsilon/2)\,n!$ up to an additive two for $\varepsilon\le1/2$. The saving is $\Theta((\log n)^2)$ nats in two rounds, with a sharp constant, and of lower order for $R=o(n)$; for $R\sim\rho n$ with $0<\rho<1$ it is linear in $n$, with the optimal rate given by a variational formula. Here, errors above an explicit threshold need only $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.
Source:https://arxiv.org/abs/2611.01028PreviousOrbits as Strong Models: Kolmogorov Structure Function under SymmetryNextSIGMA: speaker-isolated, symptom-structured multimodal estimation of depression severity from clinical interviews
Related posts
Im looking fr any free ai models / tools are there?, leaVE UR Lights💡
0dev.to
I checked 10 SEO agency websites for AI-search readiness. The real bugs were the boring ones.
0dev.to

How much GPU memory does an LLM need? The whole sum, worked out on real cards
0dev.to

Routing Upscaling Jobs by Output Size, Not Input Size
0dev.to
A ten-second Flutter pause with a visible Skip button
0dev.to UX

Thống kê lịch sử đối đầu Aston Villa - Sunderland: Đại diện Midlands áp đảo toàn diện
0dev.to Data