# Why an error probability of 1/3 in BPP?

BPP is defined as the class of polynomial-time random algorithms which have an error probability of at most 1/3.

But why was 1/3 chosen? If we have an algorithm with some error probability less than 1/2, then we can run it several times, taking the most common result, to obtain an error probability of less than 1/3 while still staying in the same complexity class.

So why isn't BPP instead defined as the algorithms which have an error probability of less than 1/2? Is there something special about 1/3?

• It even says in the article that In practice, an error probability of ​1⁄3 might not be acceptable, however, the choice of ​1⁄3 in the definition is arbitrary. It can be any constant between 0 and ​1⁄2 (exclusive) and the set BPP will be unchanged. See also Prove or refute: BPP(0.90,0.95) = BPP and Can BPP be bounded around any constant other than 1/2?. Sep 1, 2019 at 17:48
• Possible duplicate of Prove or refute: BPP(0.90,0.95) = BPP Sep 1, 2019 at 17:50
• It's not a duplicate of the other question. I understand that the classes are equivalent. I am simply trying to understand why the common definition uses 1/3, rather than 1/4, 1/5, or just "some probability less than 1/2". I guess there just isn't a reason and it was the first number the author thought of?
– user97294
Sep 1, 2019 at 18:09

The constant $$1/3$$ is completely arbitrary. Let's say that $$\mathsf{BPP}_p$$ is the class of problems solvable in polytime with error at most $$p$$. Then $$\mathsf{BPP}_p = \mathsf{BPP}_q$$ for any $$0 < p,q < 1/2$$. The simple proof can be found in any decent textbook or lectures notes on complexity theory, and is also a nice exercise. The idea is that you can boost the success probability by running the algorithm several times and take a majority vote (details left to you).
Why do we like $$1/3$$, then? It's the "simplest" rational number in $$(0,1/2)$$: for example, it is the rational number in $$(0,1/2)$$ with the minimal possible denominator, and with the minimal sum of numerator and denominator.