Bias of a halfspace after setting a coordinate

88 Views Asked by At

Consider a halfspace $T(x):= \sum_{i \in [n]} w_i x_i \geq b$, where $w_i \in \mathbb{Q}$ are fixed weights, $b \geq 0$ and $x_i \in \{-1,1\}^n$ Are variables. Define the bias of a coordinate $x_i$ as $bias(x_i,T) = \Pr_{\alpha \sim T^{-1}(1)}[\alpha_i = sign(w_i)]-1/2$ Where the probability is over a uniformy sampled $\alpha \in \{-1,1\}^n$ Such that $T(\alpha) =1$. That is, $$bias(x_i,T) = \frac{|\{x \in \{-1,1\}^{n-1}:\sum_{j \neq i, j \in [n]}w_jx_j\geq b-|w_i|\}|}{|\{x \in \{-1,1\}^{n} : \sum_{j=1}^n w_jx_j \geq b\}|} - \frac{1}{2}$$ Note that $bias(x_i) \geq 0$. Define $T \restriction_{x_1 \leftarrow sign(w_1)}(x) := \sum_{i =2}^n w_ix_i \geq b-|w_i|$.

I am wondering whether $bias(x_i,T) \geq bias(x_i, T \restriction_{x_1 \leftarrow sign(w_1)})$ for all $i \in [n]$, $i \neq 1$. Intuitively this seems correct. However, I am unable to prove it.

1

There are 1 best solutions below

1
On BEST ANSWER

This is false. A counter example is $$x_1+x_2+2x_3 \geq 0$$