Resampling operation

Question

I am reading from an arXiv.org paper the following math text:

"Let $x\in \{−1, 1\}^I$ be random and uniform, and let $y$ be obtained from $x$ by resampling each coordinate with probability $\varepsilon$ independently, where $\varepsilon \in (0, 1)$. Then $y$ is referred to as an $\varepsilon$-noise of $x$ and $\mathbb{E}(x_iy_i) = 1 - \varepsilon$."

My question is how in the probability theory we define the resampling operation considered in the text above ? I am sorry for the problem but I cannot find any answer in google

Answer 1

With the amount of context given, this means Sampling again from underlying distribution. So you end up updating some of your coordinates with probabilities $\epsilon$, while others are not updated with probability $1-\epsilon$.

Answer 2

The procedure the authors describe to get $y$ from $x$ is done independently on each component.

With probability $\varepsilon$ we choose $y_i$ to be a random (uniform independently distributed) value of $\pm 1$. With probability $1-\varepsilon$ we keep $y_i = x_i$.

So let's compute the expected value of $x_i y_i$. With chance $\varepsilon/2$ we "resample" $x_i$ and get $y_i=-1$. Also with chance $\varepsilon/2$ we "resample" $x_i$ and get $y_i=1$. Finally with chance $1-\varepsilon$ we keep $y_i = x_i$.

Now the latter outcomes have $x_i y_i = 1$ and so contribute $(1-\varepsilon)$ to the expected value. The first two outcomes have opposite signs but equal probability, so together they net contribute zero to the expected value. Thus the expected value $\mathbb{E}(x_i y_i) = 1-\varepsilon$.

Note that the authors have a footnote about this, contrasting their resampling procedure with the "bit-flipping" procedure defined in the 1999 paper by Benjamini et al. The difference in definitions contributes a factor of two in the formulas on $\varepsilon$, and in the opinion of the present authors gives simpler expressions.