<p>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&gt;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 &gt; 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$.</p>

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

CC BY-SA 3.0
2016-06-05T06:59:34.517Z
Great, thank you! A tiny nit to pick: I think you mean $\rho = 1 - 2\epsilon$.
Andrew Morgan
CC BY-SA 3.0
2016-06-05T06:11:02.897Z
2016-06-05T07:01:39.257Z
2016-06-05T07:01:39.257Z
Yuval Filmus
<p>Let $V = F_2^n$ be the $n$-dimensional vector space over the field of two elements. The <em>$\epsilon$-noise distribution</em> 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$.</p>

<p>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$:</p>

<ul>
<li><p>$E_1$ is the event that $x$ is in $C$</p></li>
<li><p>$E_2$ is the event that $x$ is in the coset $C + e$</p></li>
</ul>

<p>Some experimentation (picking some choices for $C$ at random and also some popular linear codes) suggests that, when $\epsilon &lt; 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?</p>

CC BY-SA 3.0
2016-06-05T03:46:17.560Z
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
CC BY-SA 3.0
2016-06-05T03:52:11.713Z
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
<co.combinatorics><pr.probability><coding-theory>
The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset
Andrew Morgan
# The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset

(Asked by: username_0 on 2016-06-05)

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?

**Tags:** co.combinatorics, pr.probability, coding-theory

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2016-06-05. Score: 2 | Accepted answer

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

> **Comments:**
> **username_0**: Great, thank you! A tiny nit to pick: I think you mean $\rho = 1 - 2\epsilon$.  

---

