Why is the probability used in the definition of RP complexity classes, arbitrary?

I was looking at the following wikipedia article on the RP complexity class:

https://en.wikipedia.org/wiki/RP_(complexity)

In its definition it states:

• If the correct answer is NO then it always returns NO

• If the correct answer is YES then it returns YES with a probability of 1/2

At the end of the introduction it says:


The fraction 1/2 in the definition is arbitrary. The set RP will contain exactly the same problems, even if the 1/2 is replaced by any constant nonzero probability less than 1; here constant means independent of the input to the algorithm.

What I don't understand is why this 1/2 is arbitrary? If you change it to 1/3 does it really still contain the same set of decision problems as with 1/2?

Yes, the constant is entirely arbitrary. Call an algorithm a $p$-algorithm if:

-
When the correct answer is NO, it always answers NO.

-
When the correct answer is YES, it answers YES with probability at least $p$.

Note that the probability in the YES case is only over the algorithm's coin tosses.

Given a $p$-algorithm and a constant parameter $m$, we construct a new algorithm which runs the original algorithm $m$ times (with independent coin tosses) and takes the OR of the result. This algorithm is a $1-(1-p)^m$-algorithm (exercise). For every constant $q < 1$ you can find a constant $m$ such that $1-(1-p)^m \geq q$. Hence if a problem admits a $p$-algorithm it also admits a $q$-algorithm, for every $0 < p,q < 1$.

StackExchange Computer Science Q#47422, answer score: 8