Balanced Allocation with Random Walk Based Sampling

Dengwang Tang, Vijay G. Subramanian

In the standard ball-in-bins experiment, a well-known scheme is to sample $d$ bins independently and uniformly at random and put the ball into the least loaded bin. It can be shown…