Scott Aaronson's Proof of $\textbf{BPP} \subset \textbf{P/poly}$ The proof is in the image below, taken from &quot;Quantum Computing Since Democritus&quot;:

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&lt;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 &quot;random string&quot; 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.