# Hamming distance in real analysis

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?$$

• What is $(0,1)^*$? Commented May 21 at 8:07
• @Lorago It's set of strings. Like 0001,1001,0000,11,000....etc. That any strings made by 0 and 1.
– user1290851
Commented May 21 at 8:13
• 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$? Commented May 21 at 8:22
• @Lorago Yes, of course, otherwise it becomes $\infty$
– user1290851
Commented May 21 at 8:30
• @Lorago I have one typo, I corrected just now.
– user1290851
Commented May 21 at 9:18

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.