# Analysis of brute force decoder in a $q$-ary erasure channel

Consider the $q$-ary erasure channel with erasure probability $\alpha$, i.e. given $x\in\mathbb{F}_q$ with probability $\alpha$ it outputs $?$ and with probability $1-\alpha$ outputs $x$.

For a linear code $\mathcal{C}$ generated by an $n\times k$ matrix $G$ over $\mathbb{F}_q$, we take a decoder $D:(\mathbb{F}_q\cup\{?\})^n\to\mathcal{C}\cup\{\text{fail}\}$ such that:

$$D(y) = \begin{cases} c & \text{if}\ \exists!\ c\in\mathcal{C}:y\ \text{agrees with}\ c\ \text{on the unerased entries in}\ \mathbb{F}_q \\ \text{fail} & \text{otherwise} \\ \end{cases}$$

For a set $J\subseteq [n]$ let $p_G(J)$ be the probability that $D$ outputs “fail” conditioned on the erasures being indexed by $J$.

Prove that $\mathop{\mathbb{E}}\limits_{G\in \mathbb{F}_q^{n\times k}}[p_G(J)]\leq q^{k-n+|J|}$.

Let $p_G$ be the probability that $D$ outputs “fail”. Show that when $k = Rn$ for $R<1-\alpha$, $\mathop{\mathbb{E}}\limits_{G\in \mathbb{F}_q^{n\times k}}[p_G]$ is exponentially small in $n$.

For the first part I think that if the errors occurred are indexed by $J$, we are left with $n-|J|$ correct entries, so $D$ fails when the corresponding $n-|J|$ rows of $G$ does not imply a unique solution to the set of linear equations. But I don't know how to compute the probability of such an event.

For the second part I took random variables $\forall\ J\subseteq [n]:\mathbf{1}_J$ which indicates whether the errors occurred are indexed by $J$. It is clear that $\mathbb{E}[\mathbf{1}_J]=\alpha^{|J|}(1-\alpha)^{n-|J|}$ and I tried to use the above bound for all the $J$'s with $|J|\leq n-k$ and a bound of $1$ with the other $J$'s, but it doesn't seem to be sub-exponential at the end. Moreover I ended up with partial binomial theorem sums and I failed to estimate them.

To upper bound the first probability, we can assume without loss of generality that the sent codeword is the zero codeword. After deleting $|J|$ rows, we are left with a random $(n-|J|)\times k$ matrix $A$, and we want to bound the probability that its (right) kernel is non-trivial, that is, that there is a non-zero vector $x$ such that $Ax=0$. For any non-zero vector $x$, $Ax$ is a uniformly random vector (why?), and so the probability that $Ax=0$ is $q^{-(n-|J|)}$. Since there are $q^k-1$ many non-zero vectors $x$, the union bound shows that the probability that one of them satisfies $Ax=0$ is at most $q^k \cdot q^{-(n-|J|)}$. We can slightly improve on this by considering vectors up to scalar products, which reduces the probability by a factor of $q-1$.
The second half involves applying Chernoff's bound (also known as Hoeffding's bound) to show that it is unlikely that there are many erasures, and then applying the bound in the first half. Choose the threshold so that $q^{k-n+|J|} \leq q^{-\epsilon n}$.