  We consider the allocation problem in which $m \leq (1-\epsilon) dn $ items
are to be allocated to $n$ bins with capacity $d$. The items
$x_1,x_2,\ldots,x_m$ arrive sequentially and when item $x_i$ arrives it is
given two possible bin locations $p_i=h_1(x_i),q_i=h_2(x_i)$ via hash functions
$h_1,h_2$. We consider a random walk procedure for inserting items and show
that the expected time insertion time is constant provided $\epsilon =
\Omega\left(\sqrt{ \frac{ \log d}{d}} \right).$
