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.
[1]: 71–72 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.
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.
matrix with entries in
Each column represents a subject and each row represents a feature.
The partition to groups is described by
vector with entries in
is in the treatment group T and
is in the control group C. The balance of features is described by
is the imbalance in feature
in C. The imbalance of a given partition is defined as: The set balancing problem is to find a vector
which minimizes the imbalance
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
be the total number of subjects that have feature
(equivalently, the number of ones in the
Consider the following two cases: Easy case:
Then, with probability 1, the imbalance in feature
Hard case:
is a random variable that can be either 1 or -1 with probability 1/2.
The imbalance in feature
are independent random variables, by the Chernoff bound, for every
and get: By the union bound,