Pseudorandomness when the odds are against you