# Amplifying success probability for PTMs with $poly(n) / \exp(n)$ gap?

The following is a well-known result of BPP in complexity theory, e.g., Theorem 1 and its proof from here:

Consider a probabilistic Turing Machine (PTM) $$M$$, and a language $$L \in BPP$$:

1. If $$x \in L$$ (YES instance), then $$M$$ outputs YES with probability $$\geq 1/2 + 1 / poly(n)$$,

2. If $$x \notin L$$ (NO instance), then $$M$$ outputs NO with probability $$\leq 1/2 - 1 / poly(n)$$.

We can amplify the success probability of $$M$$ to $$1 - \frac{1}{2^{q(n)}}$$, for some polynomial $$q(n)$$. This can be shown by running the PTM $$M$$ for a total of polynomial times, taking the majority vote, and using the Chernoff bound.

If I am not mistaken, this result also implies that the new PTM $$M'$$ from the procedure above has the probability gap of some constant (for instance, it's $$2 / poly(n)$$ for $$M$$).

My question: This result leads to me thinking that what would happen if we have $$1/2 + 1 / \exp(n)$$ instead of only $$poly(n)$$? Can we also run it for polynomial times, take the majority vote, and then use some tail bounds and concentration inequalities to show that the new probability gap from the new PTM is $$t(n) / \exp(n)$$ for some polynomial $$t(n)$$?

My progress: I don't achieve much success with the traditional Chernoff bounds, I also read some results but am not sure if they are really helpful. This survey by Fan Chung and Linyuan Lu also mentioned martingales, do you think it could be helpful here?