To illustrate how we do this, let us do this for the input search algorithm, both for the Classical Turing machine (CTM) and the Probabilistic Turing Machine (PTM).
In both cases, it makes sense to express the number of steps needed to find the input as functions $t_{\textrm{CTM}}(d)$ and $t_{\textrm{PTM}}(d)$ of the distance $d$ of the reading head to the input, represented by the (unknown) number of cells between the reading head and the input when we start the CTM.
The CTM spends most of its time zig-zagging to find the input: given $d$, it needs at most $$1+2+3+ \cdots + 2d = \frac{2d(2d+1)}{2}$$ many steps. So $$t_{\textrm{CTM}}(d) \le K \cdot d^2,$$ where $K>0$ is a constant.
In contrast, because PTM involves random events, we want to find an upper bound $B(d)$ of $t_{\textrm{PTM}}(d)$ that holds with a certain fixed probability $p_0 > 0$, that is, such that $$t_{\textrm{PTM}}(d) \le B(d)$$ with probability $p_0$, independent of $d$. Once we have found such a probability $p_0$, it then suffices to run $1/p_0$ many instances of PTM in parallel in order to find the input in at most $B(d)$ many steps with probability 1. This is the most certainty we can get for a PTM!
The situation is similar for the Quantum Turing Machines (QTM) that we will define. The exercise here is to illustrate how we arrive at such a statement for our input-searching PTM. The corresponding computations for QTMs are similar but possibly more involved, and we will simply cite the corresponding statements without confirming them.
Back to our input-searching PTM: instead of zig-zagging, our PTM uses its random generator to decide whether to move left or right at each step. This makes for a simpler Turing program, and to compare its performance with that of our CTM, we need to determine $p_0$ and corresponding bound $B(d)$ as mentioned above.
To do so, denote by $p(d,n)$ the probability that our PTM finds the input in $n$ steps, assuming it was initially $d$ cells away. There are two easy cases to compute $p(d,n)$:
- if $d=0$, the reading head happens to start out on one of the cells of the input, so $p(d,n) = 1$ for all $n$;
- if $n < d$, then the input is more than $n$ cells away, so $p(d,n) = 0$.
So for our computation, we may assume that $n \ge d > 0$.
Next, we can code each possible movement outcome of our PTM after $n$ steps as as a binary number with $n$ digits, where we use the digit 1 to indicate movement by one cell towards the input, and the digit 0 to indicate movement by one cell away from the input.
With this coding, a binary $n$-digit number corresponds to a run of our PTM that detects the input, exactly if the number contains at least $d$ more 1s than 0s, which is the same as having at least $\frac{n+d}2$ many digits of 1. So to compute $p(d,n)$, we need to count the number of all binary $n$-digit numbers with at least $\frac{n+d}2$ many digits of 1, and divide that number by the number of all $n$-digit binary numbers (i.e., by $2^n$).
Now, there are exactly $\tbinom{n}{k} = \frac{n!}{k!(n-k)!}$ many binary $n$-digit numbers with exactly $k$ many digits of 1 (the same as there are $k$-element subsets of a set of $n$ elements). Therefore, $$p(d,n) = \frac1{2^n}\sum_{k \ge \frac{n+d}2} \binom{n}{k}.$$ To extract the information of $p_0$ and corresponding bound $B(d)$ is very tricky!
We need some help: We use the observation that the probabilities $p(d,n)$ correspond to so-called cumulative probabilities corresponding to partial areas under the curve representing the binomial distribution. This observation gives us the following fact from Probability Theory:
Theorem (closed formula lower bound)
If $n \ge 2d$, then $$p(d,n) \ge \frac1{15} \exp\left( -4\frac dn \right).$$
Let’s write $l(d,n)$ for the right-hand side $\frac1{15} \exp\left( -4\frac dn \right)$; this is a closed formula lower bound for $p(d,n)$. It can be much more easily manipulated: for instance, since $-4\frac dn$ is always negative, its exponential is always at most 1, so that $l(d,n) \le \frac1{15}$. On the other hand, if $d$ is fixed and $n$ goes to $\infty$, then $-4\frac dn$ approaches $0$. This means that, for any number $p_0 < \frac1{15}$, there exists some $n_0$ such that $l(d,n) > p_0$ for all $n \ge n_0$.
Therefore, the Theorem above tells us that we can take $p_0$ to be any number less than $\frac1{15}$. We will choose $p_0 = \frac1{30}$ to illustrate the remainder of the argument.
The other good thing about the closed form of $l(d,n)$ is that we can solve the inequality $l(d,n) \ge \frac1{30}$ for $n$: doing so yields $n \ge \frac{4d^2}{\log 2}$. Since $\log 2$ is a constant between $0$ and $1$, we can take $$n \ge 4d^2.$$ The right-hand side of this inequality can serve as our $B(d)$: if $B(d) = 4d^2$, then by the above we have $l(d,B(d)) \ge \frac1{30}$, so by the Theorem we also get $p(d,B(d)) \ge \frac1{30}$.
Thus we have proved the following:
Proposition
With probability at least $\frac1{30}$, given an input located $d$ cells away from the reading head, our PTM will detect the input in at most $4d^2$ many steps.
This is exactly the kind of statement we were looking for, with $p_0 = \frac1{30}$ and $B(d) = 4d^2$. This shows that our PTM is at least as efficient at finding the input as our CTM, since both need $K d^2$ many steps to do so, for some $K>0$.
Could the estimates above be improved to show that our PTM is actually more efficient than our CTM? This would require us to find a lower bound for $p(d,n)$ that grows like $d^r$ for some $r < 2$. Choosing a different number below $\frac1{15}$ for our $p_0$ will not do this, as you can verify. So we would need a better closed formula lower bound—which I have not found.