The set balancing problem in mathematics is the problem of dividing a set to two subsets that have roughly the same characteristics. It arises naturally in design of experiments.
There is a group of subjects. Each subject has several features, which are considered binary. For example: each subject can be either young or old; either black or white; either tall or short; etc. The goal is to divide the subjects to two sub-groups: treatment group (T) and control group (C), such that for each feature, the number of subjects that have this feature in T is roughly equal to the number of subjects that have this feature in C. E.g., both groups should have roughly the same number of young people, the same number of black people, the same number of tall people, etc.
Matrix representation.
Formally, the set balancing problem can be described as follows.
formula_1 is the number of subjects in the general population.
formula_2 is the number of potential features.
The subjects are described by formula_3, an formula_4 matrix with entries in formula_5. Each column represents a subject and each row represents a feature. formula_6 if subject formula_7 has feature formula_8, and formula_9 if subject formula_7 does not have feature formula_8.
The partition to groups is described by formula_12, an formula_13 vector with entries in formula_14. formula_15 if subject formula_7 is in the treatment group T and formula_17 is subject formula_7 is in the control group C.
The balance of features is described by formula_19. This is an formula_20 vector. The numeric value of formula_21 is the imbalance in feature formula_8: if formula_23 then there are more subjects with formula_8 in T and if formula_25 then there are more subjects with formula_8 in C.
The "imbalance" of a given partition is defined as:
formula_27
The set balancing problem is to find a vector formula_12 which minimizes the imbalance formula_29.
Randomized algorithm.
An approximate solution can be found with the following very simple randomized algorithm:
Send each subject to the treatment group with probability 1/2.
In matrix formulation:
Choose the elements of formula_12 randomly with probability 1/2 to each value in {1,-1}.
Surprisingly, although this algorithm completely ignores the matrix formula_3, it achieves a small imbalance with high probability when there are many features. Formally, for a random vector formula_12:
formula_33
PROOF:
Let formula_34 be the total number of subjects that have feature formula_8 (equivalently, the number of ones in the formula_8-th of the matrix formula_3). Consider the following two cases:
Easy case: formula_38. Then, with probability 1, the imbalance in feature formula_8 (that we marked by formula_21) is at most formula_41.
Hard case: formula_42. For every formula_7, let formula_44. Each such formula_45 is a random variable that can be either 1 or -1 with probability 1/2. The imbalance in feature formula_8 is: formula_47. Since the formula_45 are independent random variables, by the Chernoff bound, for every formula_49:
formula_50
Select: formula_51 and get:
formula_52
By the union bound, 
formula_53.
References.
 ;templatestyles src="Reflist/styles.css" / ;