arXiv preprint ·
Local decisions, diffusive influence, and lower bounds for graphical balanced allocation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In graphical two-choice allocation, each arriving ball is assigned to one endpoint of a random edge. We study rules whose decision is a monotone function of the two endpoint loads, allowing edge-dependent thresholds and fresh randomization. Such a rule has an exact unit-discrepancy coupling: adding one ball to the initial state produces one tagged discrepancy at every later time. We represent the tag by conditional-expectation projections on the marked edge space and obtain diffusive displacement bounds. A transport-volume inequality then converts slow propagation of influence into lower bounds for the load gap. On the cycle with $n$ vertices, from every initial distribution and at every physical time $t\ge 1/n$, the expected gap is at least a constant times $\min\{\sqrt n,t^{1/4}\}$, and the gap exceeds this scale with probability at least $1/8$. After exactly $k\ge1$ allocations, the corresponding scale is $\min\{\sqrt n,(k/n)^{1/4}\}$. No stationarity, symmetry, recurrence, or moment assumption is used. The general inequality also yields a lower bound of order $\sqrt{L/K+\log K}$ on the $L\times K$ discrete torus $C_L\square C_K$. These results separate endpoint-local rules from global-information strategies that achieve polylogarithmic gaps on cycles.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Probability
Distribution-constrained maximum stopping of maximum type
MultiTable: A Faster Hash Table at any Physical Load Factor up to and Including One
Stable and Online Algorithms for Random Matrix Discrepancy
Stochastic Knothe-Rosenblatt: Light-speed Calibration of Stochastic Local Volatility Models
Ballistic Speed and Potential-Theoretic Recurrence for Homogeneous Open Quantum Random Walks
Get the few papers worth your time in Probability every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.