# On The Next Bit Test

I would like to know what $$O(v(n))$$ really means in detailed and simple words please. I found it everywhere in the literature I am reviewing but I cannot find what the intuition of it (especially if it means the Big O Notation, then what it has to do with the Probability here; also what is $$v$$, it is never defined except in another paper as a constant -but maybe not related directly to v in this formula-).

Many Thanks.

References 1 , 2

• can you give a reference to where you got the quote from and what [1] is? after all, others may be better than you in tracing references. took a quick look at two references, I did not see any $\nu(n)$. – kodlu Aug 31 '20 at 22:24
• @kodlu Just added the references. This (1) is the equation number whereas $s{_1}^{i-1}$ means the subsequence starting at the first bit and ends at $i-1$. – Mike Aug 31 '20 at 22:43

But this notation is defined (informally) in the first paper.

The notation $$O(\nu(n))$$ is used for any function, $$f(n)$$, that vanishes faster than the inverse of any polynomial, that is for every polynomial, $$\mathrm{poly} (n)$$, and $$n$$ large enough, $$f(n) \leq 1/\mathrm{poly}(n)$$

Therefore, what it means is no probabilistic polynomial time (PPT) algorithm $$A$$ can guess the next bit at inverse polynomially decreasing error rate.

Given any PPT algorithm $$A$$ this error probability decays super-polynomially, for example at a rate $$\exp(-\log^2 n)$$ which goes to zero faster than any polynomial.

Claim: $$\exp(-\log^2 n)$$ is less than $$n^{-c}$$ for any constant $$c$$ for $$n$$ large enough.

Proof: Look at the reciprocal. $$\exp(\log^2 n) > n^c$$ if and only if $$\log^2 n > c \log n$$ which will clearly happen as soon as $$\frac{\log^2 n}{\log n}>c$$ i.e., as soon as $$\log n>c$$.

Note that $$\exp(\log^{1+\epsilon} n)$$ is superpolynomial for all $$\epsilon>0.$$

Edit: The superpolynomial convergence is essentially what is referred to as negligibility.

• Thanks and +1. So a successful predictor should predict with a probability greater than or equal $1-O(ν(n))$, How is the latter evaluated numerically. That's from where should I derive the $O(ν(n))$ numerically? A simple example of a simple algorithm will be very much appreciated. – Mike Sep 1 '20 at 9:57
• Is O(v(n)) the error rate? And how is it derived? Practically from the experiment/simulation? Thanks. – Mike Sep 1 '20 at 10:38
• It is implicitly negligibility. Adding this into answer will increase the awareness. – kelalaka Sep 1 '20 at 18:17

First, that's not the Next Bit Test, which is purely theoretical, but rather an attempt at a practical approximation of it.

The notation $$O(\nu(n))$$ is used for any function, $$f(n)$$, that vanishes faster than the inverse of any polynomial, that is for every polynomial, $$poly(n)$$, and $$n$$ large enough, $$f (n) < 1/poly (n)$$.