# Scott Aaronson's Proof of $\textbf{BPP} \subset \textbf{P/poly}$

The proof is in the image below, taken from "Quantum Computing Since Democritus": Here's what I don't totally get: my understanding of random algorithms is that randomization is not done over the input space; the inputs are still worst case. So that when a random algorithm has some error, what I interpret that to mean is that given any input string to the algorithm, there is at most such-and-such probability of outputting a wrong answer.

If I take the same string $$s$$ and run it through the random algorithm with error rate $$e<1$$ an $$n$$ amount of times, I should expect $$ne$$ wrong answers.

I haven't been able to reconcile the above with the technique used in the linked proof; in particular, the jump from $$2^{-n^2}$$ being the error rate of the BPP algorithm to saying that a $$2^{-n^2}$$ fraction of random strings cause us to err. If someone could explain this proof a little more verbosely I think I'd find that very helpful.

What he here means by a "random string" is not an element of the input space, but rather a string of random choices, i.e. a series of coin flips that have been taken while executing the randomized algorithm. If you enumerated every possible such series of coin flips, you would see that at most a $$2^{-n^2}$$ fraction of them would lead the algorithm to conclude with the wrong answer.