Пусть $(\widetilde x_n\,|\, n\in\mathbb N)$ — семейство случайных величин, принимающих значения в множестве $\{0,1\}^*$. Для произвольной строки $x\in\{0,1\}^*$ обозначим через $B_x$ оракул, возвращающий при своем $i$-м вызове бит $x_{[i]}$ ($i\in\{1,\dots,\lvert{x}\rvert\}$). Тогда вышеуказанное семейство случайных величин удовлетворяет условию непредсказуемости следующего бита, если для $x\leftarrow\widetilde x_n$, для любого полиномиального вероятностного алгоритма $\mathcal A$, делающего при вычислении на входе $\left(1^n,1^{\lvert{x}\rvert}\right)$ строго меньше $\lvert{x}\rvert$ запросов к оракулу $B_x$ (обозначим число таких запросов через $k$), и для любого полинома $p$ неравенство \[ \Pr\left(\mathcal A^{B_x}\left(1^n,1^{\lvert{x}\rvert}\right) =x_{[k+1]}\right)\leqslant\frac12+\frac1{p(n)} \] выполняется при всех достаточно больших $n\in\mathbb N$.

Пусть $(\widetilde x_n\,|\, n\in\mathbb N)$ — семейство случайных величин, принимающих значения в множестве $\{0,1\}^*$. Предположим, что существуют полином $p$ и функция $m\colon\mathbb N\to\mathbb N$ такие, что $m(n)\leqslant p(n)$ для всех $n\in\mathbb N$ и величина $\Pr(\lvert{\widetilde x_n}\rvert\ne m(n))$ пренебрежимо мала как функция от $n\in\mathbb N$. Тогда следующие условия эквивалентны:

семейство $(\widetilde x_n\,|\, n\in\mathbb N)$ псевдослучайно;
семейство $(\widetilde x_n\,|\, n\in\mathbb N)$ удовлетворяет условию непредсказуемости следующего бита;
для $x\leftarrow\widetilde x_n$, $i\in_{\mathfrak U}\{1,\dots,\lvert{x}\rvert\}$, для любого полиномиального вероятностного алгоритма $\mathcal A$ и для любого полинома $p$ неравенство \[ \Pr\left(\mathcal A\left(1^n,1^{\lvert{x}\rvert},x_{[1,\dots,i-1]}\right) =x_{[i]}\right)\leqslant\frac12+\frac1{p(n)} \] выполняется при всех достаточно больших $n\in\mathbb N$.