Set balancing


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 and control group, 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.
is the number of subjects in the general population.
is the number of potential features.
The subjects are described by, an matrix with entries in. Each column represents a subject and each row represents a feature. if subject has feature, and if subject does not have feature.
The partition to groups is described by, an vector with entries in. if subject is in the treatment group T and is subject is in the control group C.
The balance of features is described by. This is an vector. The numeric value of is the imbalance in feature : if then there are more subjects with in T and if then there are more subjects with in C.
The imbalance of a given partition is defined as:
The set balancing problem is to find a vector which minimizes the imbalance.

Randomized algorithm

An approximate solution can be found with the following very simple randomized algorithm:
In matrix formulation:
Surprisingly, although this algorithm completely ignores the matrix, it achieves a small imbalance with high probability when there are many features. Formally, for a random vector :
PROOF:
Let be the total number of subjects that have feature . Consider the following two cases:
Easy case:. Then, with probability 1, the imbalance in feature is at most.
Hard case:. For every, let. Each such is a random variable that can be either 1 or -1 with probability 1/2. The imbalance in feature is:. Since the are independent random variables, by the Chernoff bound, for every :
Select: and get:
By the union bound,