# Partition data into two sets such that the difference of their variance is minimal

Suppose there are $n$ data values $x_1<x_2<\ldots<x_{n-1}<x_n$，and I've found a partition number $k$, such that $$\left|\frac{1}{k}\sum_{i=1}^k(x_i-\hat{\mu_k})^2-\frac{1}{n-k}\sum_{j=k+1}^n(x_j-\hat{\mu}_{n-k})^2\right|$$ is minimal. Here $\hat{\mu}_k$ is the mean of the first $k$ values, and $\hat{\mu}_{n-k}$ is the mean of the last $n-k$ values.
But is this optimal partition unique for any set of mutually different data values? How could I prove the uniqueness (or the opposite)? Furthermore, under what conditions would the solution be unique?

-- EDIT 1 --

@Glen_b has given a nice answer which let me notice that the original problem description is incomplete in some sense. The method to partition two datasets by minimizing their variance difference is a heuristic way to do binary classification, and it works in practice. So I'm thinking of the underlying theoretical aspects of the particular problem. In practice the data are affected by noise and will never distributed in some regular symmetric style. Now if I assume the data are generated by a mixture of two Gaussian distribution with equal variance, is it possible to prove that the method mentioned above generates a meaningful result?

• This is a very good question.Waiting for some ideas... – TPArrow Jul 18 '15 at 16:54
• If there were ties at the split point I would think there might be problems but you have prevented that. Can you show that any reallocation of two assignments will create a larger absolute difference? – DWin Jul 18 '15 at 20:43
• @DWin actually ties between two contiguous split point is permitted, I forgot to mention that. For your problem, I think there should be more assumptions to ensures that, but I'm not sure what the assumption are. – xyguo Jul 20 '15 at 12:00

## 1 Answer

Well, as long as I've understood the intent of "mutually different" correctly, counterexamples are trivial to construct, so the answers to the first two questions are:

1. No.

2. Proof of non-uniqueness can proceed by giving a counterexample to uniqueness.

Consider $x$ consisting of the numbers $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$; the minimum occurs twice.

Indeed one needn't invoke symmetry such as this; other counterexamples can readily be constructed.

One can construct cases - by solving a quadratic - where adding an observation in the right position at the far right of the data leaves variance unchanged; doing a similar exercise for two distinct samples, then flipping the second sample about the maximum of the first gives a sample where including or not including the pivotal observation in either subsample leaves both subsample variances unaltered.

e.g. consider $\{ 1,2 \}$ vs $\{1,2,x\}$; if we want the ($s^2_n$) variances of those two data sets to be equal we can write $x$ as the solution of a quadratic, and obtain $x=\frac{3}{2}+\sqrt{\frac{3}{8}}\approx 2.112372$. In both cases the variance is $0.25$.

We can in turn add a fourth observation in similar fashion, and by using a similar argument to the "pivoting" above, construct a sample of data such as this:

1.000000 2.000000 2.112372 2.281474 2.393847 3.393847


which can be partitioned with $k=2,3$ or $4$ and in each case yield a variance difference of $0$.

While both my numeric examples involve variance differences of $0$, it's possible to set up other non-unique variance differences than $0$.

I don't have a good answer for the third question (at least not so far), but I figured I'd at least post the relatively obvious part so other readers understand that the last question is the one to focus on, since the rest is straightforward.

• Most likely I understood only 10% of this post. Is what you are talking about something I could use as solution for a question posted here: stats.stackexchange.com/q/315472/133561 ? – blazej Nov 25 '17 at 20:04
• Uh, not really, because the way this question works you only insert a single dividing line among ordered values, rather than allocate things to groups regardless of such ordering (this is a simpler problem than yours) ... but I am glad you asked because I see a problem with this answer. – Glen_b Nov 26 '17 at 0:02
• Heh, Ok. Any chance you could help me out with my question? Part of the problem is I miss vocabulary and proper terms to make a decent search. Feels like problem itself is not something new (i could be wrong) but I fail to find right words to describe it (or basic math to solve it). Anyway, it's off topic here. Regards – blazej Nov 26 '17 at 8:30