4
$\begingroup$

Given two binary strings $x, y\in (0,1)^*$ such that $|x|=|y|$, then the set $$\delta{(x,y)}=\frac{|\{i\in[|x|]:x_i\neq y_i\}|}{|x|}$$ is called relative hamming distance.

Given $x\in (0,1)^*$ and $S:$= a collection of binary strings, define $$\delta_S(x)=\min_{y\in S, |x|=|y|}\delta(x,y).$$

Given $\epsilon>0,x\in (0,1)^*$ is said to be $\epsilon$-far from $S$ provided $\delta_S(x)>\epsilon.$

The majority language is given by: $$\text{MAJ}:=\{x\in (0,1)^*:\sum_{i=1}^ {|x|}x_i>\frac{|x|}{2}\},\text{where $x_i$ is the $i$-th position value(either $0$ or $1$) of $x$}.$$

My question is how can I prove if $\delta_{MAJ}(x)>\epsilon,$ then $$\frac{\sum_{i=1}^ {|x|} x_i}{|x|}<\frac{1}{2}-\epsilon?$$

$\endgroup$
6
  • $\begingroup$ What is $(0,1)^*$? $\endgroup$
    – Lorago
    Commented May 21 at 8:07
  • 2
    $\begingroup$ @Lorago It's set of strings. Like 0001,1001,0000,11,000....etc. That any strings made by 0 and 1. $\endgroup$
    – user1290851
    Commented May 21 at 8:13
  • $\begingroup$ I suppose also that it should be $$\delta_S(x)=\min_{\substack{y\in S \\ \lvert y\rvert=\lvert x\rvert}}\delta(x,y),$$as $\delta(x,y)$ is only defined when $\lvert x\rvert=\lvert y\rvert$? $\endgroup$
    – Lorago
    Commented May 21 at 8:22
  • $\begingroup$ @Lorago Yes, of course, otherwise it becomes $\infty$ $\endgroup$
    – user1290851
    Commented May 21 at 8:30
  • $\begingroup$ @Lorago I have one typo, I corrected just now. $\endgroup$
    – user1290851
    Commented May 21 at 9:18

1 Answer 1

4
$\begingroup$

The problem as written is not correct. Consider a string $x$ of even length and with exactly $|x|/2$ ones. By the definition of the majority language given, which requires the strict inequality, the string $x$ is not in the majority language and so $\delta_{\text{MAJ}}(x)>0$. If we fix some $0<\epsilon<\delta_{\text{MAJ}}(x)$ we have that $\delta_{\text{MAJ}}(x)>\epsilon$. But $\frac{\sum_i x_i}{|x|} = 1/2$ and so $\frac{\sum_i x_i}{|x|} > \frac{1}{2} - \epsilon$.

The problem can be fixed by allowing a non-strict inequality in the definition of majority language i.e., $\frac{\sum_i x_i}{|x|} \geq \frac{1}{2}$. We proceed to prove that.

Let $x$ be a given binary string. If it is a majority element, there is nothing to prove as $\delta_{\text{MAJ}}(x) = 0$. Thus we assume it has $\ell < |x|/2$ ones. A closest majority element $x^{*}$ to $x$ is formed by toggling any $|x|/2 - \ell$ zeroes in $x$. It follows that $\delta_{\text{MAJ}}(x) = 1/2 - \ell/|x|$, and this quantity is $>\epsilon$. The quantity $\frac{\sum_i x_i}{|x|}$ is equal to $\ell/|x|$. Thus we have

$$\epsilon < 1/2 - \ell/|x| = 1/2 - \frac{\sum_i x_i}{|x|}$$ as desired.

$\endgroup$
0

You must log in to answer this question.