Распишем формулу математического ожидания числа итераций. Обозначим количество итераций $l$ и $\alpha = \mathbb{P}(\sum\limits_{i=1}^m z_i < \frac{m}{2})$, где $z_i$ --- значение $i$-той скобки (0 или 1).
Теперь оценим $\alpha$. Пусть $i$-тая скобка содержит $k_i$ литералов. Чтобы значение скобки было равно нулю, необходимо, чтобы значения всех литералов были равны нулю. Вероятность такого события $2^{-k_i}$. Следовательно, вероятность $\mathbb{P}(z_i = 0) \leq \frac{1}{2}$. Если предположить, что все $z_i$ независимые случайные величины, то $\alpha = \mathbb{P}(\sum\limits_{i=1}^m z_i < \frac{m}{2}) \leq \frac{1}{2}$. Если же $z_i$ зависимы, то из неравенства $\mathbb{P}(A, B) \leq \mathbb{P}(A) + \mathbb{P}(B)$ получаем ту же оценку на $\alpha$. Отсюда имеем оценку ожидания числа итераций