I am learning basic cryptography from Coursera's cryptography I course and am a bit confused about the negligible and non-negligible function epsilon and how it relates to the predictability of pseudo random generators (PRG).
In the video lecture, it says that the PRG (as a function called "G") is predictable if:
If there exists such an algorithm A and there exists an i; 1 <= i <= n-1 (n is the length of the string defined in the universe U: {0,1}^n)
such that:
Probability of the algorithm being able to predict the next bit (i+1) is >= 1/2 + epsilon
where epsilon can be a number like 1/(2^30).
The thing that I am confused about is the examples he gave of what is negligible and what is not negligible.
In particular, here is the example that the lecture said is negligible:
e(lambda) = 1/(2^lambda) is negligible.
From what I am able to understand, if I plug in 1 for lambda, I get e(1)=1/2 and in the inequality I gave above, the right side adds to 1 (1/2 + 1/2), so that means that the probability of the PRG being predictable is impossible?
Note: lambda is supposed to be a polynomial, but it is still a bit confusing as to what it means in the equation.
The probability of an algorithm correctly predicting the next bit in a perfectly random sequence, is exactly 0.5 - because there are two potential outcomes of equal likelihood and it's selecting one of them. So for a perfectly random generator, any next-bit-predicting algorithm will have a probability of correct prediction, of exactly 0.5.
That means, if you have a NBP algorithm that is able to give better predictions than perfect randomness, it is necessarily not perfectly random any more - so it is pseudorandom by definition.
If you have an algorithm that has accuracy of less than 0.5, then you are able to flip all bits, and its accuracy is then more than 0.5; this allows us to reduce the consideration to only cases where the probability of correct prediction P is above 0.5. Then you can simply define epsilon to be eps' = (P - 0.5)/2. From there you can plug values into the equation and solve, so:
0.5 + eps' = 0.5 + (P - 0.5)/2 = 0.5 - 0.25 + P/2 = 0.25 + P/2 =< P/2 + P/2 =< P
and you're done.