# Majority function stability under deletion and addition of entries

It is well known that the majority function is stable under random flipping of bits. That is, if $$v$$ is a random binary vector, and then we re-sample each bit of $$v$$ with probability $$\delta$$ and get $$v^{'}$$, then $$\Pr[Maj(v) = Maj(v^{'})] = 1 - \frac{arccos(\delta)}{\pi}$$

However, how will the majority function behave under addition or substruction of entries? Say we delete t random bits of v and add s random bits to get $$v^{'}$$. Is there any similar connection between $$Maj(v)$$ and $$Maj(v^{'})$$ in this scenario?

I conjecture that yes because the two cases are of course equivalent when s=t, however, I'm not sure how the connection behaves as a function of s,t, nor how to formally start to prove such connection.

Thanks!

$$\newcommand{\bm}{\boldsymbol}$$The two scenarios are not equal even when $$s = t$$. In the $$s,t$$ case you always re-sample the same number of bits, while in the $$\delta$$ case you get a binomial distribution in the number of bits flipped.

Let us define $$\text{Maj}$$ in a slightly different way than you might be used to, but assure yourself it is correct.

$$\text{Maj}(\bm{v}) := \left[\text{Sign}(\bm v) \geq 0\right]\\ \text{Sign}(\bm{v}) = \sum_i (-1)^{\bm v_i}$$ Now because $$\bm v$$ is a uniform random boolean vector, if we remove an element (say $$v_i$$) from it to from $$\bm v'$$ we can we can see that

$$\text{Sign}(\bm v') = \text{Sign}(\bm v) - (-1)^{v_i}$$

but this is very similar to the expression we'd get when adding a new bit $$u_i$$:

$$\text{Sign}(\bm v') = \text{Sign}(\bm v) + (-1)^{u_i}$$

Since $$u_i$$ is sampled from the uniform distribution of bits, we can replace it with random variable $$u'_i = 1 - u_i$$ which has an equivalent distribution, giving:

$$\text{Sign}(\bm v') = \text{Sign}(\bm v) - (-1)^{u'_i}$$

In other words, removing a bit from the vector is not distinguishable from adding a new bit from the perspective of the majority function. Therefore we can just assume $$k = s+t$$ and only add $$k$$ bits to the original $$n$$ in $$v$$.

So what is the chance that when we add those bits our majority function doesn't change? If $$\bm v$$ contained $$n$$ bits originally, that question is equivalent (again using $$\text{Sign}$$ as insight) to starting a simple symmetric random walk on the unit line and asking what the chance is that we are at the same side of the origin after $$n + k$$ steps as we were at $$n$$ steps. If we let $$X_n$$ be our random walk at step $$n$$ this works out to (for the positive side):

$$\Pr[X_n \geq 0, X_{n+k} \geq 0] = \Pr[X_n \geq 0]\Pr[X_{n+k} \geq 0 \mid X_n \geq 0]$$

With $$Y$$ being an independent random walk (and thus identical to $$X$$), we can say due to a random walks lack of memory that:

$$\Pr[X_{n+k} \geq 0 \mid X_n \geq 0] =\\ \sum_{i = 0}^n\Pr[X_n + Y_k \geq 0 \mid X_n = i] =\\ \sum_{i = 0}^n\Pr[X_k \geq -i]\Pr[X_n = i]$$

And thus:

$$\Pr[X_n \geq 0, X_{n+k} \geq 0] = \Pr[X_n \geq 0]\sum_{i = 0}^n\Pr[X_k \geq -i]\Pr[X_n = i]$$

We can apply a similar series of steps to find $$\Pr[X_n < 0, X_{n+k} < 0]$$. Then finally

$$\Pr[\text{Maj}(\bm v') = \text{Maj}(\bm v)] = \Pr[X_n \geq 0, X_{n+k} \geq 0] + \Pr[X_n < 0, X_{n+k} < 0]$$

Now as an exercise to the reader, fill in $$\Pr[X_n = q], \Pr[X_n \geq q]$$ and $$\Pr[X_n < q]$$ and simplify. These probabilities for random symmetric walk $$X$$ are well-known (see any textbook on random walks).

• Thank you very much for the detailed answer and the connection to random walks. For future students with the same problem: look the continuous arcsine distribution that approximates the location of the last sign change to complete the calculation, as $Maj(v) = Maj(v^{'})$ w.p. 1 if there was no sign-change in the last k steps, and w.p. half otherwise. – Bartolinio Oct 18 '19 at 10:28
• On second thought, I think that your logic of "adding a bit is equivalent to removing a bit" is very wrong. Consider the case when $v, v^{'}^ are random binary vectors of length three that share their first bit. Your claim is that$\Pr[Maj(v) = Maj(v^{'})]$is the same as the probability that the sign of random binary vector with length 5 that starts with v[0] is equal to v[0]. However, it's immediate to see that in the first case the probability is 2*0.25*0.75 (one of the vectors "switch sides" and the other does not), and in the second case, the probability is 5/16. Am I missing something? – Bartolinio Oct 21 '19 at 10:19 • (The probabilities in the above comment refer to the compliment event of$\Pr[Maj(v) \neq Maj(v^{'})]\$) – Bartolinio Oct 21 '19 at 10:26
• @Bartolinio Hrm, I just did some combinatorical exhaustive experiments and it seems that for even length bitstrings removing a random bit is indistinguishable from adding one, but the same doesn't hold for odd length bitstrings. I don't see why that's the case though. – orlp Oct 21 '19 at 12:38