# Show that RP is closed under concatenation

I'm trying to prove the following problem:

Show that $RP$ is closed under concatenation

Now, let's say that the two languages are $L_{1}$ and $L_{2}$ (both in $RP$). Then I accept a word iff the TM of $L_{1}$ accepted the first part of the word (with a probability $\geq\frac{1}{2}$), and the TM of $L_{2}$ accepted the second part of the word (with a probability $\geq\frac{1}{2}$).

But then each word in the language $L_{1} \circ L_{2}$ would be accept with a probability of $\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}$, so the language $L_{1} \circ L_{2}$ will not be in $RP$.

So what is the correct proof to the problem?

• Hint: amplify the success probability. – Yuval Filmus Sep 1 '18 at 22:16

Do the following $poly(|x|)$ times:
Check for every possible (contiguous) partition of the input string $x = x_1x_2$ and apply the $\mathrm{RP}$ machine to each of $x_i$ if the answer is $\mathrm{YES}\:\mathrm{YES}$ outputs $\mathrm{YES}$ and halt.
If after polynomially many times, still no definite $\mathrm{YES}$ answer has been put down, output $\mathrm{NO}$ with a little bit of fear as it is always like so with $\mathrm{RP}$ algorithms.