In Regev's Paper "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography" he considers in the introduction of the paper the "learning from parity with error". Where we have an unknown $s \in \mathbb{Z}_2^n$ our goal is to find this $s$, given a list of equations with errors e.g. $\langle s,a_i \rangle \approx b_i (\text{ mod } 2)$ etc. The $a_i$'s are chosen independently from the uniform distribution on $\mathbb{Z}_2^n$, $\langle s, a_i\rangle = \sum_j s_j (a_i)_j$ is the inner product modulo 2 of $s$ and $a$, each equation is correct with probability $1-\epsilon$. With no error we would be able to solve a system of equations using Gaussian elimination, this is understandable.
Regev goes a bit further and considers the Gaussian elimination process and assuming that we are interested in recovering only the first bit of $s$. He says using Gaussian elimination, we can find a set $S$ of $O(n)$ equations such that $\sum_S a_i$ is $(1,0,...,0)$. Summing the corresponding values $b_i$ gives us a guess for the first bit of $s$.
The part that I don't understand and this is my question: He says with a standard calculation one can show that this guess is correct with probability $\frac{1}{2} + 2^{-\Theta(n)}$. How exactly does one arrive this estimate, what is this standard calculation? I don't quite understand it, so I wanted to ask this question here.
I hope that my question is understandable. I thank you for helpful comments/answers.
