Absolute difference between the first and second half of a random vector Suppose I have a zero vector of length $2n$, and I randomly choose $k$ of the entries of this vector to be $1$. The choice is taken uniformly from all $\binom{2n}{k}$ possibilities. Now let $S_1$ denote the sum of the first half of the vector, and $S_2$ denote the sum of the second half. I want to know the percentage of vectors such that the difference between $S_1$ and $S_2$ is nontrivial. More precisely, I want to compute the probability that $P(\frac{|S_1-S_2|}{n} > \epsilon)$ as $n$ and $k$ become large. 

I'm almost sure that there is an established result somewhere, but since I'm not familiar with combinatorics, I don't know how to search for it. 
 A: TL;DR: I will show in this answer that
$$
\mathbb{P}\left(\frac{|S_1 - S_2|}{n} > \epsilon\right)
\le \frac{1}{\varepsilon^2 (2n-1)},
$$
independent of $k$ (better bounds can be given if $k$ is close to $1$ or $2n$).
In other words, the probability you ask for is bounded above by roughly $1 / (2 \varepsilon^2 n).$ In particular, it tends to $0$ as $n \to \infty$.

Markov's inequality is useful here. We consider the random variable $S_1 - S_2$ which is the sum of the first $n$ entries of the vector, minus the last $n$; that is, if the vector is $v$,
$$
S_1 - S_2 = (v_1 + v_2 + \cdots + v_n) - (v_{n+1} + v_{n+2} + \cdots + v_{2n}).
$$
We are interested in $\mathbb{P}\left(|S_1 - S_2| > n \epsilon\right)$.
But it will be more convenient to work with $(S_1 - S_2)^2$, so we note
$$
\mathbb{P}\left(|S_1 - S_2| > n \epsilon\right)
= \mathbb{P}\left((S_1 - S_2)^2 > n^2 \epsilon^2\right).
$$
We can then apply Markov's inequality as follows:
$$
\mathbb{P}\left((S_1 - S_2)^2 > n^2 \epsilon^2\right)
\le \frac{\mathbb{E}((S_1 - S_2)^2)}{n^2 \epsilon^2}.
$$
Now, observe that $S_1 + S_2 = k$, so $S_2 = k - S_1$. So we get
$$
= \frac{\mathbb{E}((2 S_1 - k)^2)}{n^2 \epsilon^2}.
$$
Now the expected value of $S_1$ is $\frac{k}{2}$, so the denominator is related to the variance. We get
$$
\mathbb{P}\left(|S_1 - S_2| > n \epsilon\right) \le \frac{4 \cdot \text{Var}(S_1)}{n^2 \varepsilon^2}. \tag{1}
$$
So the question becomes, what is the variance of $S_1$?
We can use this formula:
$$
\text{Var}(S_1)
= \text{Var}(v_1 + v_2 + \cdots + v_n)
= \sum_{i=1}^n \text{Var}(v_i) + \sum_{i \ne j} \text{Cov}(v_i, v_j).
$$
An individual $v_i$ is Bernoulli where the probability of being $1$ is $\frac{k}{2n}$, so the variance is $\frac{k}{2n} \left(1 - \frac{k}{2n}\right)$.
As for the covariance between $v_i$ and $v_j$, there are four possibilities for the pair of variables, and the covariance is calculated as
\begin{align*}
\text{Cov}(v_i, v_j)
= &\frac{k}{2n} \cdot \frac{k-1}{2n-1} \cdot \left(\frac{2n - k}{2n}\right)^2 \\
&+ 2 \cdot \frac{k}{2n} \cdot \frac{2n - k}{2n-1} \cdot \left( -\frac{k}{2n} \right) \left( \frac{2n - k}{2n} \right) \\
&+ \frac{2n - k}{2n} \cdot \frac{2n - k - 1}{2n-1} \cdot \left( -\frac{k}{2n} \right)^2 \\
&= \frac{k(2n-k)}{(2n)^3 (2n - 1)}
\left[ (k-1)(2n-k) - 2k(2n-k) + k(2n-k-1) \right] \\
&= \frac{k(2n-k)}{(2n)^3 (2n - 1)} \left[ -(2n- k) - k\right] \\
&= \frac{k(2n-k)}{(2n)^3 (2n - 1)} \cdot (-2n) \\
&= -\frac{k(2n-k)}{(2n)^2 (2n-1)}.
\end{align*}
Therefore,
\begin{align*}
\text{Var}(S_1)
&= n \cdot \frac{k}{2n} \left(1 - \frac{k}{2n}\right) + n(n-1) \cdot -\frac{k(2n-k)}{(2n)^2 (2n-1)} \\
&= \frac{n k (2n - k)}{(2n)^2} \left[ 1 - \frac{(n-1)}{2n-1}\right] \\
&= \frac{n^2 k (2n - k) }{(2n)^2 (2n-1)} \\
&= \frac{k(2n-k)}{4 (2n-1)}.
\end{align*}
Finally, we can return to (1). We get that
\begin{align*}
\mathbb{P}\left(|S_1 - S_2| > n \epsilon\right)
&\le \frac{4}{n^2 \varepsilon^2} \cdot \frac{k(2n-k)}{4 (2n-1)} \\
&= \frac{1}{\varepsilon^2} \cdot k (2n - k) \cdot \frac{1}{n^2 (2n-1)} \\
&\le \frac{1}{\varepsilon^2} \cdot n^2 \cdot \frac{1}{n^2 (2n-1)} \\
&= \frac{1}{\varepsilon^2} \cdot \frac{1}{2n-1}.
\end{align*}
Here, we used the fact that $k (2n - k)$ is maximized when $k = n$; better bounds can be given if $k$ is small (close to $1$) or large (close to $2n$).
In summary,
$$
\boxed{\mathbb{P}\left(|S_1 - S_2| > n \epsilon\right)
\le \frac{1}{\varepsilon^2 (2n-1)}.}
$$
We can make some concrete observations:


*

*This bound is independent of $k$.

*If $\varepsilon$ is fixed, the probability goes to $0$ as $n \to \infty$ (regardless of whether $k$ is held constant or also increasing).
A: We can use the normal approximation.  The expected number in the first half is $\frac k2$ with a standard deviation of $\frac 12\sqrt k$.  You are asking for the deviation to be greater than $\frac 12\epsilon n$, which grows faster than $\sqrt k$.  The probability tends to zero.  
You can use this approximation to look up the probability in a z-score table.
