Scott Aaronson's Proof of $\textbf{BPP} \subset \textbf{P/poly}$
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.