Accurate definition of BPP

Question

I'm a bit confused about the definition of BPP. The way BPP is defined in typical text books (Arora/Barak for example) is that if M(x) is a Probabilistic Turing Machine (PTM) that recognizes a language $L(x)$, then $Pr[M(x)=L(x)]> 2/3$. My question is, what is the probability taken over? Arora/Barak remark (7.2) that the probability is taken over internal coin tosses of $M(x)$, i.e., fix a value of $x$, and run all possible $2^{T(|x|)}$ experiments of internal coin tosses, and compute the majority of accept state. But if this is true, then Amplification theorem cannot hold because by definition if the probability is computed by executing all $2^{T(|x|)}$ possible coin-flips, then no matter how many times I run the algorithm, the probability is not going to change. (For example, if I have a bag with 2 red balls and 1 blue ball, then no matter how many times I pick a ball from the bag (and return it), the probability of picking a red ball is going to remain 2/3.)

Basically, a PTM is a random process in two variables: The input string $x \in \{0,1\}^*$ and random coin tosses $ r \in \{0,1\}^{T(|x|)}$. For the amplification theorem to hold, I think one needs to fix a value of $r$ and run the machine on all values of $x$, and compute $Pr[M(x) = L(x)]$. Then for a fixed $x$, running $M(x)$ multiple times will have amplification effect, but if the probability is computed over internal coin tosses, then the Amplification theorem cannot hold.

What am I misunderstanding here?

Answer 1

Repeating what MCH said, every time you run the algorithm, you use fresh random bits.

As an example, here is a BPP algorithm that computes the number $1$:

Toss a biased coin (heads w.p. 2/3, tails w.p. 1/3). If heads, output 1, else output 0.

The algorithm "succeeds" with probability $2/3$. The amplification procedure amounts to tossing $n$ biased coins, outputting $1$ if the majority of them were heads, and $0$ otherwise. Since we expect roughly $(2/3)n > n/2$ of the coins to be heads, it is very likely that the amplified algorithm is successful (outputs $1$).

In other words, when you run your algorithm $n$ times, each time you run it, you re-toss all the coins. So the amplified algorithm tosses $n$ times as many coins, and the probability is taken over all these coin tosses.