Пусть имеется гиперкуб (вершины - битовые строки длины \(d\)) и некоторая перестановка \(\sigma\) на вершинах. Каждая вершина \(x\) хочет отправить посылку в \(\sigma(x)\), и её можно пересылать по рёбрам (на каждом шаге она перевозится по одному ребру, при этом другие посылки по нему на этом шаге везти нельзя). Как выбрать пути пересылки, чтобы посылки друг другу не мешали и наибольшая задержка была бы \(O(d)\)? Детерминированно это сделать нельзя (если считать, что каждая вершина знает только своего адресата и должна назначить путь перевозки). Но есть такой вероятностный алгоритм: выбрать случайную вершину и отправить сначала по кратчайшему пути (определённого вида) в неё, а потом уже к настоящему адресату. (Ср. истории о gps трекинге почты России)