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 &lt; 0, X_{n+k} &lt; 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 &lt; 0, X_{n+k} &lt; 0]$$

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