# Uniform distribution on strings

Let $$x$$ be any binary string $$\in (0,1)^*.$$

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}.$$

The hamming weight of any given string $$x\in (0,1)^*.$$ is defined by, $$wt(x)=\sum_{i=1}^{|x|}x_i=|\{i\in[|x|]:x_i=1\}|.$$

Given $$n\in \mathbb{N},$$ define two distributions:

$$X_n=\text{uniform distribution over n-long strings satisfying} wt(x)=\left \lfloor \dfrac{n}{2} \right \rfloor+1$$

$$Z_n=\text{uniform distribution over n-long strings satisfying} wt(x)=\left \lfloor \dfrac{n}{2} \right \rfloor$$

And $$P[X_n\in \text{MAJ}]=1 \text{ and } P[Z_n\in \text{MAJ}]=0.$$

Now I want to prove the following claim: $$A:= \text{algorithm querying n-long sequences string in q locations,then}|P[A(X_n)=1)]-P[A(Z_n)=1)]|\leq \frac{q}{n}.$$

My advisor give the following proof:

Proof: Generate $$X_n$$ and $$Z_n$$ as follows,Sample $$i\in [n]$$ uniformly at random($$i$$index of the string). Sample $$y\in \{z\in (0,1)^n: wt(z) =\left \lfloor \dfrac{n}{2} \right \rfloor\ ,z_i=0\}.$$ For $$Z_n,$$ output $$y.$$ For $$X_n,$$ output $$y \oplus 0^{i-1}10^{n-i}(\text{copy y pointwise and place 1 at ith entry.})$$ As long as the algorithm $$A$$ doesn't query the $$i$$th location, it behaves exactly the same on $$X_n$$ and $$Z_n$$ as it effectively queries the same values. The distribution over $$i$$ is uniform and so the algorithm queries this location with probability $$\leq\frac{q}{n}.$$

My question I don't understand the above proof, how the output for $$X_n,$$ becomes $$y \oplus 0^{i-1}10^{n-i}?$$ And how the probability $$\leq\frac{q}{n}?$$ Anybody help me to understand above the algorithm.