The Stack Overflow podcast is back! Listen to an interview with our new CEO.
6 of 8 deleted 22 characters in body

"this class of problems lie"s in RE, so its name is "RE".

$$\begin{align*}\operatorname{Prob}(M \text{ accepts}) &= \operatorname{Prob}\big((\exists n)(M \text{ accepts after exactly $n$ steps})\big)\\ &=\sum_n \operatorname{Prob}(M \text{ accepts after exactly $n$ steps})\\ &=\lim_N \sum_{n\leq N} \operatorname{Prob}(M \text{ accepts after exactly $n$ steps})\\ &=\lim_N \;\operatorname{Prob}(M \text{ accepts in at most $N$ steps}) \\ &= \lim_n \; \operatorname{Prob}(M \text{ accepts in at most $n$ steps})\,. \end{align*}$$

For all $m$ and $n$ with $m\leq n$, and for all randomness strings $r$, $M$ accepts in at most $m$ steps if and only if it accepts in exactly some $t\leq m$ steps. But then $t\leq n$ so this occurs if and only if $M$ accepts in at most $n$ steps with randomness string $r$.

For all $m$ and $n$, with $m\leq n$, the probability that $M$ accepts in at most $m$ steps does not exceed the probability that it accepts in at most $n$ steps.

$$\begin{align*} &\tfrac12 < \operatorname{Prob}(M \text{ accepts}) \\ &\iff \tfrac12 < \lim_n \; \operatorname{Prob}(M \text{ accepts in at most $n$ steps})\\ &\iff (\exists n)\left(\tfrac12 < \operatorname{Prob}(M \text{ accepts in at most $n$ steps})\right)\,. \end{align*}$$

Therefore, a machine that loops over the positive integers $n$ and accepts if and only if $\tfrac12 < \operatorname{Prob}(M \text{ accepts in at most $n$ steps})$ will accept exactly the inputs that $M$ has a probability greater than $\tfrac12$ of accepting.