Balanced allocation through random walk

We consider the allocation problem in which m≤(1−ε)dn items are to be allocated to n bins with capacity d. The items x1,x2,…,xm arrive sequentially and when item xi arrives it is given two possible bin locations pi=h1(xi),qi=h2(xi) via hash functions h1,h2. We consider a random walk procedure for inserting items and show that the expected time insertion time is constant provided ε=Ω(log⁡dd).