Local decisions, diffusive influence, and lower bounds for graphical balanced allocation
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≥ 1/n, the expected gap is at least a constant times min{√n,t1/4}, and the gap exceeds this scale with probability at least 1/8. After exactly k≥1 allocations, the corresponding scale is min{√n,(k/n)1/4}. No stationarity, symmetry, recurrence, or moment assumption is used. A smoothed threshold rule in the same class has expected gap O(√nlog n) up to any fixed polynomial time horizon, so the saturated cycle bound is sharp within the class up to a logarithmic factor. The general inequality also yields a lower bound of order √(L/K) on the L× K rectangular torus CL□ CK; combined with a strategy-independent logarithmic bound, this gives order √(L/K)+log(LK). These results separate endpoint-local rules from global-information strategies that achieve polylogarithmic gaps on cycles. All numbered results are verified in Lean.
Related
- Sharper Bounds for Graphical Two-Choice Allocation
- A double-scale diffusive wave equation for river flow modeling from satellite altimetry
- Hamiltonian Monte Carlo vs. event-chain Monte Carlo: An appraisal of sampling strategies beyond the diffusive regime
- Uniform bounds for a thermo-diffusive system beyond exponential growth
- The diffusive spectral gap of the qubit eSWAP chain
BibTeX
@misc{okechukwu2026local,
title = {{Local decisions, diffusive influence, and lower bounds for graphical balanced allocation}},
author = {Obinna Okechukwu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.38726},
eprint = {2609.38726},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38726},
}
RIS
TY - UNPB
TI - Local decisions, diffusive influence, and lower bounds for graphical balanced allocation
AU - Obinna Okechukwu
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.38726
UR - https://arxiv.org/abs/2609.38726
AB - 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≥ 1/n, the expected gap is at least a constant times min{√n,t^1/4}, and the gap exceeds this scale with probability at least 1/8. After exactly k≥1 allocations, the corresponding scale is min{√n,(k/n)^1/4}. No stationarity, symmetry, recurrence, or moment assumption is used. A smoothed threshold rule in the same class has expected gap O(√nlog n) up to any fixed polynomial time horizon, so the saturated cycle bound is sharp within the class up to a logarithmic factor. The general inequality also yields a lower bound of order √(L/K) on the L× K rectangular torus C_L□ C_K; combined with a strategy-independent logarithmic bound, this gives order √(L/K)+log(LK). These results separate endpoint-local rules from global-information strategies that achieve polylogarithmic gaps on cycles. All numbered results are verified in Lean.
ER -