Nevermind. I actually started to think about it. You can just make a cutoff at the 50% cdf point in your probability distribution over infinity.

Eliezer, may I ask, I'm having trouble figuring this out, what is your algorithm which is superior to Thrun's?

""" Moreover, once you realized how you were using your prior knowledge, you could see a derandomized version of the algorithm which was superior, even though it didn't make the exact guarantee Thrun had made. """