In Aurora and Barak, they give the following alternative definition of $BPP$:

enter image description here

What is the meaning of the subscript to $Pr$? Is that $Pr_{r \in_R \{0,1\}^{p(|x|)}}$? My guess is this is supposed to represent $poly(|x|)$ many coin toss results, but what is $R$? And why is this a subscript to $Pr$?


1 Answer 1


The subscript to $\Pr$ denotes which random variable the probability is over. In this case the probability is over $r$, which is samples uniformly at random (this is what is conveyed by $\in_R$) from $\{0,1\}^{p(n)}$. You can think of $r$ as representing a sequence of $p(n)$ many random coin tosses.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.