Finite equal-load theorem — two-sided bound
ProvedABKUFinite.finite_balanced_allocationFor every natural number , there exists a nonnegative real such that for every positive real , there exists a natural number such that, for every natural number , the uniform probability that the maximum load differs from by at most is at least . The process allocates balls sequentially to initially empty bins, each ball making independent uniform choices with replacement and joining the earliest minimum-load choice. The constant may depend on but not on or ; may depend on and .
import Definitions.Def_ABKUFinite_Model
namespace ABKUFinite theorem finite_balanced_allocation (d : ℕ) : TwoSided d := by sorry end ABKUFinite
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every natural number , there exists a nonnegative real such that for every positive real , there exists a natural number such that, for every natural number , the uniform probability that the maximum load differs from by at most is at least . The process allocates balls sequentially to initially empty bins, each ball making independent uniform choices with replacement and joining the earliest minimum-load choice. The constant may depend on but not on or ; may depend on and .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.