# The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset

Let $V = F_2^n$ be the $n$-dimensional vector space over the field of two elements. The $\epsilon$-noise distribution on $V$, denoted $\mu_\epsilon$, is a probability distribution on $V$ for which sampling a vector $w$ is done by setting each coordinate of $w$ independently, and a particular coordinate is set to $1$ with probability $\epsilon$ and to $0$ with probability $1-\epsilon$.

Let $C \subseteq V$ be a linear subspace, and let $e \in V \setminus C$ be a vector not in $C$. Consider the following pair of events concerning a vector $x$ drawn from $\mu_\epsilon$:

• $E_1$ is the event that $x$ is in $C$

• $E_2$ is the event that $x$ is in the coset $C + e$

Some experimentation (picking some choices for $C$ at random and also some popular linear codes) suggests that, when $\epsilon < 1/2$, the probability of $E_1$ occurring is at least the probability that $E_2$ occurs, for any $C$. Does anyone have any solid intuition or a proof for why this might be true? Or know of an example where it is false?

• For typical applications of the noise distribution, we're interested in $\epsilon$ near zero. The expression $\mathbb{P}[E_1] - \mathbb{P}[E_2]$ can be expressed as a polynomial in $\epsilon$, and it's easy to check that it evaluates to $1$ when $\epsilon = 0$. Hence by continuity, the claim holds when $\epsilon$ is sufficiently small. This argument is quick and easy, but the meaning of "sufficiently small" can (a priori) degrade quickly as $n$ increases, so a more uniform argument is desirable. – Andrew Morgan Jun 5 '16 at 3:46
• Concerning the polynomial in my previous comment: one idea is to try to show that, after changing variables according to $\epsilon \gets 1/4 + z/4$ (so that $0 \le \epsilon \le 1/2$ translates to $-1 \le z \le 1$), the polynomial has no roots in the unit disk. However, there are some (moderately rare) random examples where there are complex roots with modulus less than 1. This is a barrier to many simple analytic arguments. – Andrew Morgan Jun 5 '16 at 3:52

The probability that $x \in C + e$ is equal to $2^n \langle T_\rho 1_{0}, 1_{C+e} \rangle$, where $T_\rho$ is the noise operator and $\rho = 1-2\epsilon>0$. Now $$2^n \langle T_\rho 1_0, 1_{C+e} \rangle = 2^n \langle T_\rho 1_e, 1_C \rangle = \frac{2^n}{|C|} \langle T_\rho 1_{C+e}, 1_C \rangle.$$ In terms of the Fourier expansion, this quantity equals $$\frac{2^n}{|C|} \sum_S \rho^{|S|} \widehat{1_C}(S) \widehat{1_{C+e}}(S) = \frac{2^n}{|C|} \sum_S \rho^{|S|} \widehat{1_C}(S)^2 \chi_S(e).$$ Since $\rho > 0$, this is maximized uniquely when $\chi_S(e) = 1$ whenever $\widehat{1_C}(S) \neq 0$. In other words, the quantity is maximized uniquely for $e$ satisfying $C + e = C$.
Note that even when $C$ isn't a code, we have shown that if you start at a random point in $C$, apply the noise, and measure the probability that you reach $C + e$, then this probability is maximized for $e$ satisfying $C + e = C$, and in particular for $e = 0$.
• Great, thank you! A tiny nit to pick: I think you mean $\rho = 1 - 2\epsilon$. – Andrew Morgan Jun 5 '16 at 6:59