極端な例として探索空間のグラフがパスであるとします。
この探索空間の状態数が10億だとして、テキトーな初期状態から1000万回ランダムウォークするとします。 そのとき実際に探索される状態は初期状態の近くに偏ります。
探索空間には無数の局所があり、その中でもより良い局所を見つけたいわけです。 そのためにはできるだけ多くの局所に到達する必要が（少なくとも）あります。 つまり多様性がいります。 ですが、前述のような偏りがあると、限られた局所ばかりが探索されてしまい良くないのです。 なので、まんべんのないランダムウォークになるようにしましょう。
1つの指針としてグラフが sparse すぎるとき（先の例を含む）、くまなくランダムウォークしない可能性があります。
より具体的にはグラフの直径が状態の要素数 * 定数より大きいときも、良くないかもと私は判断します。
もし、くまなくランダムウォークしないとしたらそれは近傍が小さい/少ないので、近傍を大きくする/種類を増やすのが有効です。