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.
Contents
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.
The subjects are described by
The partition to groups is described by
The balance of features is described by
The imbalance of a given partition is defined as:
The set balancing problem is to find a vector
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
PROOF:
Let
Easy case:
Hard case:
Select:
By the union bound,