  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 that this scheme yields a maximum load of $\log\log
n/\log d+O(1)$ with high probability.
  Subsequent work analyzed the model when at each time, $d$ bins are sampled
through some correlated or non-uniform way. However, the case when the sampling
for different balls are correlated are rarely investigated. In this paper we
propose three schemes for the ball-in-bins allocation problem. We assume that
there is an underlying $k$-regular graph connecting the bins. The three schemes
are variants of power-of-$d$ choices, except that the sampling of $d$ bins at
each time are based on the locations of $d$ independently moving
non-backtracking random walkers, with the positions of the random walkers being
reset when certain events occurs. We show that under some conditions for the
underlying graph that can be summarized as the graph having large enough girth,
all three schemes can perform as well as power-of-$d$, so that the maximum load
is bounded by $\log\log n/\log d+O(1)$ with high probability.
