[proofplan] Start with a probabilistic polynomial-time machine for $L$ whose error probability is at most $1/3$. Use the polynomial boundedness of $k$ to fix, once and for all, a polynomial upper bound for the desired error exponent, and hardwire this bound into the amplified machine. On each input, run the base machine independently an odd number of times proportional to that upper bound and take a majority vote. For a fixed input, the wrong trials are independent Bernoulli random variables with expectations at most $1/3$, so an exponential-moment bound makes the majority-failure probability exponentially small in the number of repetitions. The chosen number of repetitions forces this probability below $2^{-k(|x|)}$, while preserving polynomial running time. [/proofplan] [step:Choose the base bounded-error machine and define the amplified machine] Since $L$ is in BPP, there exist a probabilistic Turing machine $M$ and a polynomial $p:\mathbb{N}\to\mathbb{N}$ such that $M$ halts within $p(|x|)$ steps on every input $x\in\{0,1\}^*$ and \begin{align*} x\in L \implies \mathbb{P}[M(x)=1]\geq \frac{2}{3}, \end{align*} while \begin{align*} x\notin L \implies \mathbb{P}[M(x)=0]\geq \frac{2}{3}. \end{align*} Because $k:\mathbb{N}\to\mathbb{N}$ is polynomially bounded, choose constants $C\in\mathbb{N}$ and $d\in\mathbb{N}$ such that \begin{align*} k(n)\leq C(n+1)^d \end{align*} for every $n\in\mathbb{N}$. These constants are fixed once $k$ is fixed and are hardwired into the construction of $M_k$; the machine does not need to compute or query the function $k$ on its input. Define the computable polynomial upper bound \begin{align*} r:\mathbb{N}\to\mathbb{N},\qquad r(n)=C(n+1)^d. \end{align*} Then $k(n)\leq r(n)$ for every $n\in\mathbb{N}$, and $r(n)$ is computable in time polynomial in $n$ by repeated multiplication and binary integer arithmetic. Define the repetition-count map \begin{align*} m:\{0,1\}^*\to\mathbb{N} \end{align*} as follows: for each input $x\in\{0,1\}^*$ with $n:=|x|$, let $m(x)$ be the smallest odd integer satisfying \begin{align*} m(x)\geq 24r(n). \end{align*} Thus \begin{align*} 24r(n)\leq m(x)\leq 24r(n)+1. \end{align*} The amplified probabilistic machine $M_k$ is the following machine. On input $x$, it computes $r(|x|)$, computes $m(x)$ from $r(|x|)$ by adding $1$ exactly when $24r(|x|)$ is even, runs $M(x)$ independently $m(x)$ times using disjoint blocks of random bits, and outputs $1$ if strictly more than half of the runs output $1$ and outputs $0$ otherwise. Since $m(x)$ is odd, there is no tie. The running time of $M_k$ on input $x$ is at most $m(x)p(n)$ plus the polynomial-time overhead needed to compute $r(n)$, compute $m(x)$, and count the outputs. Since $m(x)\leq 24r(n)+1=24C(n+1)^d+1$, this running time is bounded by a polynomial in $n$. Hence $M_k$ is probabilistic polynomial time. [/step] [step:Encode wrong trials by independent Bernoulli random variables] Fix an input $x\in\{0,1\}^*$ and set $n:=|x|$ and $m:=m(x)$. Let \begin{align*} Y_i:\Omega\to\{0,1\} \end{align*} be the indicator [random variable](/page/Random%20Variable) of the event that the $i$th run of $M(x)$ gives the wrong answer, for $i\in\{1,\dots,m\}$, where $\Omega$ is the finite probability space of all random-bit strings used by the $m$ independent trials, equipped with the uniform probability measure $\mathbb{P}$. Because the $m$ runs use disjoint independent random-bit blocks, the random variables $Y_1,\dots,Y_m$ are independent. By the correctness guarantee for $M$, \begin{align*} \mathbb{P}[Y_i=1]\leq \frac{1}{3} \end{align*} for every $i\in\{1,\dots,m\}$. Define the total number of wrong trials by \begin{align*} S:\Omega\to\{0,1,\dots,m\},\qquad S=\sum_{i=1}^{m}Y_i. \end{align*} The majority vote is wrong only if at least half of the individual trials are wrong. Since $m$ is odd, this event is contained in $\{S\geq m/2\}$. [/step] [step:Bound the probability that at least half of the trials are wrong] We prove the exponential tail estimate \begin{align*} \mathbb{P}\left[S\geq \frac{m}{2}\right]\leq \left(\frac{4}{3\sqrt{2}}\right)^m. \end{align*} Let $\lambda:=\log 2$. Since $e^{\lambda S}$ is a non-negative random variable, Markov's inequality gives \begin{align*} \mathbb{P}\left[S\geq \frac{m}{2}\right]=\mathbb{P}\left[e^{\lambda S}\geq e^{\lambda m/2}\right]\leq e^{-\lambda m/2}\mathbb{E}[e^{\lambda S}]. \end{align*} By independence of $Y_1,\dots,Y_m$, \begin{align*} \mathbb{E}[e^{\lambda S}]=\mathbb{E}\left[\prod_{i=1}^{m}e^{\lambda Y_i}\right]=\prod_{i=1}^{m}\mathbb{E}[e^{\lambda Y_i}]. \end{align*} For each $i$, since $Y_i$ takes values in $\{0,1\}$ and $\mathbb{P}[Y_i=1]\leq 1/3$, \begin{align*} \mathbb{E}[e^{\lambda Y_i}]=\mathbb{P}[Y_i=0]+e^\lambda\mathbb{P}[Y_i=1]=1+(e^\lambda-1)\mathbb{P}[Y_i=1]\leq 1+\frac{e^\lambda-1}{3}. \end{align*} Since $e^\lambda=2$, this becomes \begin{align*} \mathbb{E}[e^{\lambda Y_i}]\leq \frac{4}{3}. \end{align*} Combining the preceding estimates, \begin{align*} \mathbb{P}\left[S\geq \frac{m}{2}\right]\leq e^{-\lambda m/2}\left(\frac{4}{3}\right)^m=\left(\frac{4}{3\sqrt{2}}\right)^m. \end{align*} [guided] We want to estimate the probability that the sum $S=\sum_{i=1}^{m}Y_i$ is much larger than its expected scale. The expected number of wrong runs is at most $m/3$, while the majority vote fails only when at least $m/2$ runs are wrong. The standard way to convert this gap into an exponentially small probability is to apply Markov's inequality to an exponential function of $S$. Set $\lambda:=\log 2$. The random variable \begin{align*} e^{\lambda S}:\Omega\to[0,\infty) \end{align*} is non-negative, so Markov's inequality applies. The event $\{S\geq m/2\}$ is the same as the event $\{e^{\lambda S}\geq e^{\lambda m/2}\}$ because the map $t\mapsto e^{\lambda t}$ is increasing. Therefore \begin{align*} \mathbb{P}\left[S\geq \frac{m}{2}\right]=\mathbb{P}\left[e^{\lambda S}\geq e^{\lambda m/2}\right]\leq e^{-\lambda m/2}\mathbb{E}[e^{\lambda S}]. \end{align*} Now we use independence. Since $S=\sum_{i=1}^{m}Y_i$, the exponential turns the sum into a product: \begin{align*} e^{\lambda S}=e^{\lambda\sum_{i=1}^{m}Y_i}=\prod_{i=1}^{m}e^{\lambda Y_i}. \end{align*} The random variables $Y_1,\dots,Y_m$ are independent because the runs of $M$ use independent random bits. Hence the random variables $e^{\lambda Y_1},\dots,e^{\lambda Y_m}$ are also independent, and the expectation of their product factors: \begin{align*} \mathbb{E}[e^{\lambda S}]=\prod_{i=1}^{m}\mathbb{E}[e^{\lambda Y_i}]. \end{align*} For a single trial, $Y_i$ is a Bernoulli random variable indicating failure. Thus $Y_i=1$ with probability at most $1/3$ and $Y_i=0$ otherwise. We compute its exponential moment directly: \begin{align*} \mathbb{E}[e^{\lambda Y_i}]=\mathbb{P}[Y_i=0]+e^\lambda\mathbb{P}[Y_i=1]. \end{align*} Since $e^\lambda-1>0$ and $\mathbb{P}[Y_i=1]\leq 1/3$, \begin{align*} \mathbb{E}[e^{\lambda Y_i}]=1+(e^\lambda-1)\mathbb{P}[Y_i=1]\leq 1+\frac{e^\lambda-1}{3}. \end{align*} With $\lambda=\log 2$, we have $e^\lambda=2$, so \begin{align*} \mathbb{E}[e^{\lambda Y_i}]\leq \frac{4}{3}. \end{align*} Substituting this bound into the Markov estimate gives \begin{align*} \mathbb{P}\left[S\geq \frac{m}{2}\right]\leq e^{-\lambda m/2}\left(\frac{4}{3}\right)^m. \end{align*} Finally, $e^{-\lambda/2}=2^{-1/2}=1/\sqrt{2}$, and therefore \begin{align*} \mathbb{P}\left[S\geq \frac{m}{2}\right]\leq \left(\frac{4}{3\sqrt{2}}\right)^m. \end{align*} This is the required exponential decay in the number of repetitions. [/guided] [/step] [step:Choose enough repetitions to reach error $2^{-k(|x|)}$] We now compare the exponential bound with $2^{-k(n)}$ through the computable upper bound $r(n)$. Since \begin{align*} \left(\frac{4}{3\sqrt{2}}\right)^{24}=\frac{4^{24}}{3^{24}2^{12}}=\frac{2^{36}}{3^{24}}=\left(\frac{8}{9}\right)^{12}\leq \frac{1}{2}, \end{align*} we have \begin{align*} \left(\frac{4}{3\sqrt{2}}\right)^{24r(n)}\leq 2^{-r(n)}. \end{align*} Because $m\geq 24r(n)$ and $0<4/(3\sqrt{2})<1$, \begin{align*} \left(\frac{4}{3\sqrt{2}}\right)^m\leq \left(\frac{4}{3\sqrt{2}}\right)^{24r(n)}\leq 2^{-r(n)}. \end{align*} Since $k(n)\leq r(n)$, monotonicity of $a\mapsto 2^{-a}$ on $\mathbb{R}$ gives \begin{align*} 2^{-r(n)}\leq 2^{-k(n)}. \end{align*} Therefore \begin{align*} \mathbb{P}\left[S\geq \frac{m}{2}\right]\leq 2^{-k(n)}. \end{align*} [/step] [step:Conclude correctness for both membership cases] If $x\in L$, then a trial is wrong exactly when that run outputs $0$. The amplified machine $M_k$ outputs $0$ only if at least half of the $m$ trials are wrong. Hence \begin{align*} \mathbb{P}[M_k(x)=0]\leq \mathbb{P}\left[S\geq \frac{m}{2}\right]\leq 2^{-k(|x|)}. \end{align*} Equivalently, \begin{align*} \mathbb{P}[M_k(x)=1]\geq 1-2^{-k(|x|)}. \end{align*} If $x\notin L$, then a trial is wrong exactly when that run outputs $1$. The amplified machine $M_k$ outputs $1$ only if at least half of the $m$ trials are wrong. Hence \begin{align*} \mathbb{P}[M_k(x)=1]\leq \mathbb{P}\left[S\geq \frac{m}{2}\right]\leq 2^{-k(|x|)}. \end{align*} Equivalently, \begin{align*} \mathbb{P}[M_k(x)=0]\geq 1-2^{-k(|x|)}. \end{align*} Thus $M_k$ decides $L$ with error probability at most $2^{-k(|x|)}$ on every input $x$, and $M_k$ runs in probabilistic polynomial time. This proves the theorem. [/step]