Suppose we have an algorithm that gives either one of the two correct answers for a problem with probability $1-q = \frac{8}{\pi^2}$. I want to show that if we run this algorithm $O(\log_2 r)$ times and consider the most frequently occurring result as our answer then this will be correct with probability at least $1-\frac{1}{2^r}$.
My initial thought was to bound the probability of error by the probability of our algorithm returning the wrong answer in at least one-third of the runs. That is, we can model the algorithm runs as independent random variables $X_i \sim \text{Be}(q)$ and say that the probability of error in $3k$ runs is at most
$$\mathbb{P}\left(\sum_{i=1}^{3k} X_i\geq k\right)$$
The sum of $X_i$ follows the Binomial distribution $\text{Bin}(3k, q)$. I have asked this question related to my problem but the answer given there suggests this approach won't yield the bound I'm looking for.
Any help would be appreciated!
Best Answer
TL;DR: Unfortunately no. There is an exponential lower bound to the fail probability of the form $$ P_{fail}\geq 2^{-0.3 n+\epsilon n} $$ where $\epsilon>0$ can be made arbitrarily small. This means that if you use $\log r$ repeats your error probability is lower bounded by $1/\mathrm{poly}(r).$
Details:
Let $q=1-\frac{8}{\pi^2}\approx 0.19$ be the probability that the algorithm does not output one of the two right answers. So the probability of majority vote not working is the same as the probability that more than two thirds of the answers are wrong. So the probability of failure is: $$ P_{fail}=\sum_{k+1\leq i} \binom{3k}{i} q^i (1-q)^{3k-i} = \mathbb{P}(\mathrm{Bin}(3k,q)\geq k+1). $$ Let us lower bound the dominant term in the binomial sum which is the term $\binom{n}{k}$ where $k=f(qn)$ where $f$ is the nearest integer function. Use the lower bound (see the answer to this mathoverflow question here) but take the entropy in bits so the exponential is to the base 2: $$ \sqrt{\frac{n}{8k(n-k)}}2^{nh(k/n)} \leq \binom{n}{k} \quad(\ast) $$ dividing by $2^n$ to obtain a probability we get (with $h(\cdot)$ the binary entropy function $$ P_{fail}\geq \sqrt{\frac{n}{8k(n-k)}}2^{n(h(k/n)-1)}=\frac{1}{\sqrt{{8nq(1-q)}}}2^{-n(1-h(q))} $$ or plugging in $q=0.19,$ $$ P_{fail}\geq \exp_2\left\{-0.3 n -\frac{1}{2}\log_2(1.2312 n) \right\}\gg \exp_2\left\{-0.3 n+\epsilon n\right\} $$ where $\epsilon>0$ can be made arbitrarily small by taking $n$ large enough.