PaperlayerView exact revision on arXiv

Source-linked AI summary

Local decisions, diffusive influence, and lower bounds for graphical balanced allocation

Obinna Okechukwu

arXiv:2609.38726v2math.PRcs.DS

TL;DR

The paper asks how endpoint-local load decisions constrain graphical two-choice allocation. It uses an exact discrepancy coupling and finite-horizon variance arguments to prove a transient square-root cycle lower bound, uniform over initial states.

  • Problem

    Endpoint-local monotone rules restrict decisions to the two endpoint loads, and the paper studies the resulting gap on cycles.

    Source: §1 · p. 1

  • Method

    An exact single-tag discrepancy coupling and a finite-horizon variance budget yield inequalities on influence propagation.

    Source: §1 · pp. 1, 4

  • Results

    The transient cycle lower bound is uniform over initial states and reaches a saturated scale of order √n.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    A smoothed threshold rule makes the cycle lower bound sharp within the endpoint-local class up to a logarithmic factor.

    Source: §1 · p. 2

    For greedy graphical allocation, the matching upper bound remains open; its stationary gap is known only between order √n and order n.

    Source: §9 · p. 26

Abstract

from arXiv · show

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. A smoothed threshold rule in the same class has expected gap $O(\sqrt n\log 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 $\sqrt{L/K}$ on the $L\times K$ rectangular torus $C_L\square C_K$; combined with a strategy-independent logarithmic bound, this gives order $\sqrt{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.

1 Introduction

The paper studies endpoint-local monotone allocation rules and argues that their limited information forces square-root-scale gaps on cycles. It develops a finite-horizon influence argument to establish lower bounds without relying on invariant-measure structure.

1 Introduction

  • Endpoint-local monotone rules on the cycle have a square-root gap because influence propagates only diffusively, allowing macroscopic imbalance to persist.The result concerns rules deciding from the two endpoint loads, including edge-dependent thresholds and fresh randomization.Source: §1 · p. 1
  • The cycle lower bound is transient and uniform over the initial state, and the same lower scale holds with probability at least 1/8.The introduction also states a fixed-allocation-count version of the cycle bound.Source: §1 · p. 2
  • The cycle lower bound is sharp within the endpoint-local monotone class up to a logarithmic factor, while whether greedy allocation itself has an O(√n) gap remains open.The cited smoothed-threshold result applies from the flat profile and over polynomial time horizons.Source: §1 · p. 2
  • The information restriction distinguishes these rules from global strategies that compare average loads on fixed vertex sets and achieve polylogarithmic gaps on cycles and tori.The distinction concerns available information, not the number of bins modified per ball.Source: §1 · p. 3
  • The proof characterizes exactly when synchronous coupling preserves one unit discrepancy, then uses a marked tag and a finite-horizon variance budget rather than invariant measures.For randomized rules, an auxiliary uniform mark realizes an update as a deterministic monotone threshold rule.Source: §1 · pp. 3–4
  • All 22 numbered theorems, lemmas, propositions, and corollaries are formalized and verified in Lean 4 with Mathlib.The paper reports no additional axioms or unproved assumptions.Source: §1 · p. 4

2 Endpoint-local monotone rules

Endpoint-local monotone rules decide from the two endpoint loads, with choices that are nonincreasing in their load difference. Their updates preserve a single discrepancy when one extra ball is added, and the characterization excludes rules that use off-edge loads or violate endpoint monotonicity.

2 Endpoint-local monotone rules

  • The model is invariant under common integer translations of all loads, and its normalized process is defined on the quotient by those translations.Rules that read off-edge loads or fail endpoint monotonicity can produce more than one discrepancy and fall outside the characterization.Source: §2 · pp. 5–6
  • A deterministic selector is a nonincreasing function of the difference between the two endpoint loads; edge rules may use different functions, including randomized thresholds.A common uniform mark realizes each randomized update as a deterministic threshold rule.Source: §2 · p. 5
  • Raising an endpoint load preserves a one-unit discrepancy: it either stays put or moves to the opposite endpoint if the selected endpoint changes.An off-edge perturbation cannot affect the decision under the endpoint-local characterization.Source: §2 · p. 5
  • The synchronous coupling tracks the discrepancy as a vertex-valued tag at every physical time and after any fixed number of allocation events.The event-indexed position after h events is the physical-time position at the random event count.Source: §2 · p. 6

3 The marked Palm tag

The marked Palm tag represents the discrepancy through an auxiliary mark whose conditional law follows the tag. Its transitions are conditional-expectation projections that preserve the mark distribution and act only on a local set of edge fibers.

3 The marked Palm tag

  • The auxiliary mark starts with law ρ, and its process has the same conditional law as the event-indexed discrepancy tag.The initialization weights the tag location by the instantaneous allocation rates, λ_w(x)/m.Source: §3 · pp. 6–7
  • Each mark transition is an orthogonal conditional-expectation projection on L2(ρ), preserving ρ while acting only on fibers incident to the selected vertex's closed neighborhood.The transition resamples within new selection cells in the affected union and leaves marks outside that union fixed.Source: §3 · p. 7, Figure 1 · p. 8
  • The conditional-law invariant is maintained by resampling marks within their new cells when the selected load changes; unaffected cells remain unchanged.This establishes the equality in conditional law between the auxiliary mark process and the coupling's discrepancy tag.Source: §3 · p. 7
  • The selection-cell proportions depend on the rule, but the representation relies only on the nesting forced by endpoint monotonicity.The cycle figure's outer fibers are included because neighboring vertices' new cells also involve their other incident edges.Source: §3 · pp. 6–7, Figure 1 · p. 8

4 Diffusive displacement

Products of conditional-expectation projections control how far the tag can move, even when the projections vary with time and do not commute. On the cycle, a Fourier-mode argument yields diffusive displacement bounds in event time and physical time.

4 Diffusive displacement

  • The projection-product estimate controls sequences of orthogonal projections without reordering them, which matters because the conditional mark process is time-inhomogeneous and its projections need not commute.The estimate also applies to Hilbert-valued functions.Source: §4 · p. 8
  • The first Fourier mode of the edge midpoints converts the projection estimate into a diffusive bound on the cycle.Each selection cell uses at most two adjacent edge midpoints, and the affected region is contained in four edge fibers.Source: §4 · p. 9
  • Proposition 4.2 gives a diffusive displacement bound for the tag after exactly h allocations, uniformly over starting profiles and endpoint-local monotone rules on the cycle.The proposition also states a corresponding bound at physical time s.Source: §4 · p. 9
  • The physical-time bound follows by averaging over the Poisson number of allocation events, whose mean at time s is ns on the n-cycle.The displacement argument is first conditioned on a base path with a fixed number of events.Source: §4 · p. 9

5 The transport-volume inequality

The transport-volume inequality combines slow tag displacement with finite-horizon response energy to bound the load gap. A clipped two-point test localizes response to metric balls, and a corollary converts the inequality into a gap lower bound under a small-displacement condition.

5 The transport-volume inequality

  • The finite-horizon argument does not require a stationary law or a long-time limit.The terminal time is fixed, and the proof uses a martingale variance identity.Source: §5 · p. 10
  • Finite-horizon response energy is controlled by a martingale variance identity for bounded translation-invariant observables.At an allocation to v, the martingale jump is D_vP_{t-u}f(X_{u-}); its expected predictable quadratic variation equals the stated response-energy integral.Source: §5 · p. 10
  • The transport-volume inequality bounds load-gap tails using the tag's displacement tail and the largest comparison-ball volume, with a radius that can vary over time.Varying the radius accommodates graphs whose ball volumes change growth rate, including rectangular tori.Source: §5 · p. 10
  • Averaged clipped two-point observables retain positive response while the tag stays inside a protected ball; cancellation requires displacement of at least the ball's radius.The two exceptional histories are a tag ending at i after starting outside B(i,R), or starting inside B(i,R) and ending sufficiently far away.Source: §5 · pp. 11–12, Figure 2 · p. 11
  • If the displacement tail stays at most 1/8 through time T, Corollary 5.4 converts the transport bound into a gap lower bound for t at least max{T,1/m}.The extra 1/m condition is handled by a load-sum phase bound for the small-scale regime.Source: §5 · p. 13

6 The cycle

The cycle arguments turn slow propagation of a tagged discrepancy into load-gap lower bounds in continuous and fixed-allocation time. A discrete transport-volume inequality supplies the bridge, with a variance correction needed for fixed allocation counts.

6 The cycle

  • A cycle quantile bound combines diffusive tag displacement with separated comparison points and balls of controlled volume.The proof pairs vertices separated around the cycle and applies the transport-volume estimate.Source: §6 · pp. 13–14
  • Diffusive tag displacement yields continuous-time cycle lower bounds on both the expected gap and its probability of exceeding a threshold, uniformly over initial laws.The proof uses a cycle quantile bound and a fixed comparison radius.Source: §6 · pp. 13–14

6.1 A deterministic number of allocations

  • The discrete proof uses a Doob martingale with terminal load tests; its distinct increments provide the variance accounting for fixed event counts.The construction aligns the lagged response with the gap tail at the terminal state.Source: §6.1 · pp. 16–17
  • A one-step nonflatness bound handles the small parameter ranges where the main transport argument does not supply the claimed threshold.A nonflat profile can become flat in one update only in a narrowly specified case, with selection probability at most 2/n.Source: §6.1 · pp. 17–18
  • For every fixed allocation count k ≥ 1, the discrete argument likewise derives expected-gap and probability lower bounds for arbitrary initial laws.It uses a discrete transport-volume inequality and accounts for a variance correction absent in continuous time.Source: §6.1 · pp. 15, 18

7 Other graphs

The paper extends its influence-to-gap approach beyond cycles using Hilbert embeddings and graph geometry. It obtains lower bounds for finite-width cylinders and rectangular tori, and combines the rectangular-torus result with a strategy-independent logarithmic bound.

7 Other graphs

  • Hilbert embeddings give displacement bounds, but the projection result does not claim graph-distance diffusion on arbitrary graphs.A separated permutation and controlled comparison-ball volume then permit a transport-volume lower bound.Source: §7 · pp. 18–19

7.1 Finite-width cylinders

  • For finite-width cylinders, the lower-bound conclusions hold for every endpoint-local monotone rule, including when the finite graph factor is disconnected.The cylinder is C_L □ H, with the stated time horizon t ≥ L^2.Source: §7.1 · p. 19

7.2 Rectangular tori

  • The rectangular-torus argument varies the protected radius while retaining a single family of terminal tests, rather than summing bounds from separate observable families.Its combined aspect-ratio and logarithmic scales are compared using the two separate probability lower bounds.Source: §7.2 · pp. 21–22
  • For every strategy on a regular graph, the logarithmic lower bound holds after sufficiently many allocations and also gives a physical-time probability bound.The stated physical-time bound has probability at least 7/16 for t ≥ (log N)/(4∆).Source: §7.2 · pp. 20–21
  • On rectangular tori CL□CK with 3 ≤ K ≤ L and N = LK, Corollary 7.6 gives a combined bound for every endpoint-local monotone rule and initial law when t ≥ L², including an aspect-ratio term.The same conclusions hold under every invariant normalized law.Source: §7.2 · pp. 22–23

8 A nearly matching rule

The paper constructs a smoothed threshold rule whose drift is linear below a cutoff, enabling a stopped linear-process analysis. On cycles, its expected gap is within a logarithmic factor of the lower-bound scale over polynomial time horizons.

8 A nearly matching rule

  • Below the cutoff, the rule’s linear drift makes the load process a stopped linear recursion driven by bounded martingale noise.The analysis bounds the stopped process and controls the probability of crossing the cutoff.Source: §8 · pp. 23–24
  • The smoothed threshold rule is endpoint-local and orientation-independent, equivalently using an independent uniform threshold on each event.Its probabilistic comparison noise places it in the same endpoint-local monotone class as the lower bounds.Source: §8 · p. 23
  • On cycles, the smoothed threshold rule has expected gap O(√n log n) up to any fixed polynomial time horizon.The rule starts from the flat profile and uses cutoff θ = 242 log n.Source: §8 · p. 25
  • On the square torus, the rule has expected gap O((log L)^(3/2)) up to polynomial horizons, while every strategy has a logarithmic gap lower bound with stated probability.The comparison is presented relative to the normalized Gaussian free-field scale.Source: §8 · pp. 25–26

9 Open problems

The open problems concern whether greedy allocation attains the cycle upper-bound scale, whether endpoint-local rules reach the Gaussian-free-field scale on square tori, and how to extend the theory to bounded-radius information.

9 Open problems

  • Whether greedy allocation on the cycle has an O(√n) upper bound remains open; its stationary gap is known only between order √n and order n.The cited equilibrium upper bound is O(n).Source: §9 · p. 26
  • On square tori, the paper asks whether greedy or any endpoint-local monotone rule can achieve expected gap O(log L), and whether Gaussian-free-field range lower bounds extend to bounded-degree regular graphs.The proposed extension concerns diffusive times and polylogarithmic factors.Source: §9 · p. 26
  • For bounded-radius rules, the open problem is to find a replacement for the single-discrepancy tag and determine whether polynomial cycle gaps still follow.Off-edge load information can produce a signed discrepancy with several nonzero coordinates.Source: §9 · p. 26
Loading 2609.38726v2…