Alternative definitions of ZPP and probabilistic Turing Machines

Question

There are two ways to define a probabilistic Turing Machine:

1. A Turing Machine that can toss coins during its computation.
2. A deterministic Turing Machine that takes two inputs: $(x,r)$, where $x$ is the original input and $r$ is taken from a distribution of coin tosses.

For example, Arora and Barak give an "alternative definition" for $\mathrm{BPP}$:

Definition 7.4 (BPP, alternative definition)
$\mathrm{BPP}$ contains a language $L$ if there exists a polynomial-time TM $M$ and a polynomial $p\colon \mathbb{N}\to \mathbb{N}$ such that for every $x \in \{ 0, 1 \}^{∗}$, $\Pr_{r \in \{ 0,1 \}^{p(|x|)}} [M (x, r) = L(x)]\geq 2 / 3 $.

My problem is formulating a similar alternative definition for $\mathrm{ZPP}$.

$\mathrm{ZPP}$ can be defined as the class of languages with a randomized algorithm that always outputs the correct answer, and for every input the expected running time of the algorithm is polynomial.

If we want a similar alternative definition for $\mathrm{ZPP}$, then $r$ should be an infinite stream because the algorithm may need to use any number of coin tosses before it finishes (with small probability).

Is there any problem with a Turing Machine that takes as a second input an infinite long stream?

Answer 1

The definition works fine if you allow $r$ to be infinite, and require that $M(x,r)$ agrees with $L$ with probability $1$ when $r$ is distributed according to the coin toss measure on $\{0,1\}^{\mathbb{N}}$ (toss a fair coin an infinite number of times). In this setting, in order to get $\mathsf{ZPP}$, you need to require that the expected running time will be polynomial in $|x|$.

However, you don't really need an infinite number of coins to get $\mathsf{ZPP}$, and could do with an exponential amount of coins. Suppose $L\in\mathsf{ZPP}$, hence there exists a probabilistic Turing machine $M(x)$, such that for all $x\in\Sigma^*$ it holds that $M(x)=L(x)$ and $\mathbb{E}[T_x]\le |x|^c$, where $T_x$ is the running time of $M$ on input $x$. You can now define an equivalent Turing machine $M'$ which is exponential in the worst case (rather than unbounded), and still satisfies the above conditions. Given input $x$, $M'$ simulates $M$ for $2^{|x|^c}$ steps, and if $M$ did not halt in this time, check "manually" if $x\in L$. This can be done by running a PSPACE machine for $L$ (which exists since $\mathsf{ZPP\subseteq PSPACE})$. You can now show that $M'$ is also polynomial in expectation (think about the appropriate choice of $c$ for this to work).