Spencer's conjecture on infinitely recurring bin orderings

About 21 years old · traced to

Consider a balls-in-bins process (Im(i))i∈[B],m≥0(I_m(i))_{i\in[B],m\geq 0} with feedback function ff in the almost-balanced regime. Here [B]={1,…,B}[B]=\{1,\ldots,B\}, and Π\Pi ranges over all permutations of [B][B]. Spencer's conjecture. For every permutation Π\Pi of [B][B] and every initial condition, with probability 11 there are infinitely many m≥0m\geq 0 such that

Im(Π(1))<Im(Π(2))<⋯<Im(Π(B)).I_m(\Pi(1))<I_m(\Pi(2))<\dots<I_m(\Pi(B)).

Equivalently, every possible ordering of the bins occurs infinitely often almost surely. The conjecture concerns the almost-balanced regime and asks whether the process visits every strict ordering infinitely often, regardless of its initial state; the supplied text gives no resolution.

References

Primary source

Roberto Oliveira, “Balls-in-bins with feedback and Brownian Motion”, arXiv:math/0510648 (2005).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.