Difference between Bernoulli random variables Given are $n$ independent Bernoulli random variables with parameters $p_1,\dots,p_n$. We want to split them into two parts so as to minimize the expectation $\mathbb{E}[|X-Y|]$, where $X$ is the sum of the first part and $Y$ the sum of the second part. 
What is the best way to split so that this expectation is minimized? A reasonable guess is that it is always to make the sums of the parameters $p_i$'s in the two parts as close as possible. Are there examples where this is not optimal?
 A: UPDATE: There is a counter-example!
The set is $[p_i] = [0.24, 0.24, 0.24, 0.28, 0.5, 0.5],$  and I considered two splits.  The first one is a perfect split ($E[X-Y] = 0$) while the second one isn't.  If my code has no bugs, here are the relevant values, with minima in red.
$$
\begin{matrix}
\text{Split} & E[|X-Y|^2] & E[|X-Y|] & E[X-Y] \\
[0.24, 0.24, 0.24, 0.28] \text{   vs   } [0.5, 0.5] & \color{red}{1.2488} &0.84330 & \color{red}{0} \\
[0.24, 0.24, 0.5] \text{    vs    } [0.24, 0.28, 0.5] & 1.2504 & \color{red}{0.84003} & 0.04
\end{matrix}
$$
So the perfect split ($E[X-Y] = 0$) does minimize $E[|X-Y|^2]$ as my older answer proved.  However, the imperfect split actually has a lower $E[|X-Y|]$.
Speculation: It so happens that $P(X-Y=0)$ is higher for the imperfect split ($0.3476$) than for the perfect split ($0.3429$).  I wonder if this has any bearing on the question.  Also, I wonder if some kind of "symmetry" plays a role, although I did not bother to calculate the skews. 
P.S. I found this by considering $[0.25, 0.25, 0.25, 0.25, 0.5, 0.5]$ and evaluating the two different perfect splits.  As my older answer shows, both perfect splits have the same $E[|X-Y|^2]$ value.  But as I hoped, they have different $E[|X-Y|]$ values.  Then I simply perturb them a bit to arrive at the counter-example.

ORIGINAL: Not an answer, but too long for a comment.
I don't know how to minimize $E[|X-Y|]$, but your intuition (split the $p_i$'s as evenly as possible) actually minimizes $E[|X-Y|^2]$.  Note that the two are not the same thing in general.


*

*$E[|X-Y|^2] = E[(X-Y)^2] = E[X-Y]^2 + Var(X-Y)$

*$E[X-Y] = \sum_{i \in \mathcal{X}} p_i - \sum_{j \in \mathcal{Y}} p_i,$ so $E[X-Y]^2$ is minimized when the $p_i$'s are as evenly split as possible.  (Note that this is conceptually simple but computationally... NP-complete I think.)

*Meanwhile, $Var(X - Y) = Var(X) + Var(Y) = Var(X+Y) = \sum_{all\ i} p_i (1-p_i) =$ constant.  So this does not figure in the minimization.
In conclusion: splitting them as evenly as possible minimizes $E[|X-Y|^2]$.  
Further thoughts: Since $E[|X-Y|^2] = E[|X-Y|]^2 + Var(|X-Y|),$ any counter-example would be such that the optimal (uneven) split has higher $E[|X-Y|^2]$, higher $Var(|X-Y|)$, but lower $E[|X-Y|]$, compared to the even split.
I found such a situation rather improbable (pardon the pun), but I don't have a proof either way.
