Введём ещё одно базовое средство анализа рандомизированных алгоритмов: границы Чернова. Они говорят нам о том, что сумма независимых друг от друга случайных 0/1-величин существенно отклоняются от ожидаемого значения лишь с очень маленькой вероятностью.

Используем границы Чернова для анализа рандомизированного алгоритма для доставки пакетов между процессорами, связанными друг с другом коммуникационной сетью топологии n-мерного гиперкуба. Поскольку сеть имеет диаметр n, доставка одного пакета от отправителя до получателя в худшем случае требует не менее n шагов. Однако доставка всех пакетов может требовать гораздо больше шагов, если они блокируют друг друга, создавая пробки: известно, что любой детерминированный алгоритм, в котором маршруты пакетов зависят только от адресов отправителя и получателя, в худшем случае требует \(O(\sqrt{2^n}/n)\) шагов. Однако можно использовать случайность для равномерного распределения нагрузки по сети. Это приводит к простому алгоритму, который с высокой вероятностью доставит каждый пакет до его назначения за O(n) шагов.