Поскольку в L = O(2^N) (L – период генератора, N – длина состояния генератора в битах), N находится под управлением программиста – это такое слабое ограничение, что мне о нём было лень думать. Но если Вы настаиваете – пожалуйста. Я брожу с шагом 1 пока не выберу период, возвращаюсь в начало и начинаю бродить с шагом, вдвое большим, чем предыдущий. И т.д. Вероятность того, что они не встретятся, наверное, останется (выполняя случайные танцы можно увернуться друг от друга даже в 1D), но она будет, я думаю, O(2^(-L/x)), где x – некоторое число, а не 1/2.

Ну или, как я уже говорил, можно медленно растить шаг по времени, log(t) точно подойдёт, можно, наверное, и степень подобрать.