1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Andrew Morgan
    Commented Jun 5, 2016 at 3:46
  • $\begingroup$ 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. $\endgroup$
    – Andrew Morgan
    Commented Jun 5, 2016 at 3:52

1 Answer 1

Reset to default
2
$\begingroup$

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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great, thank you! A tiny nit to pick: I think you mean $\rho = 1 - 2\epsilon$. $\endgroup$
    – Andrew Morgan
    Commented Jun 5, 2016 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.