5
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Bartolinio Oct 18 at 10:28
  • $\begingroup$ 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? $\endgroup$ – Bartolinio Oct 21 at 10:19
  • $\begingroup$ (The probabilities in the above comment refer to the compliment event of $\Pr[Maj(v) \neq Maj(v^{'})]$) $\endgroup$ – Bartolinio Oct 21 at 10:26
  • $\begingroup$ @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. $\endgroup$ – orlp Oct 21 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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