Binary operation for which "negligible" functions are closed
Answers
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.