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 (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.

[math]\displaystyle{ m }[/math] is the number of subjects in the general population.

[math]\displaystyle{ n }[/math] is the number of potential features.

The subjects are described by [math]\displaystyle{ A }[/math], an [math]\displaystyle{ n\times m }[/math] matrix with entries in [math]\displaystyle{ {0,1} }[/math]. Each column represents a subject and each row represents a feature. [math]\displaystyle{ a_{i,j}=1 }[/math] if subject [math]\displaystyle{ j }[/math] has feature [math]\displaystyle{ i }[/math], and [math]\displaystyle{ a_{i,j}=0 }[/math] if subject [math]\displaystyle{ j }[/math] does not have feature [math]\displaystyle{ i }[/math].

The partition to groups is described by [math]\displaystyle{ b }[/math], an [math]\displaystyle{ m\times 1 }[/math] vector with entries in [math]\displaystyle{ {-1,1} }[/math]. [math]\displaystyle{ b_j=1 }[/math] if subject [math]\displaystyle{ j }[/math] is in the treatment group T and [math]\displaystyle{ b_j=-1 }[/math] is subject [math]\displaystyle{ j }[/math] is in the control group C.

The balance of features is described by [math]\displaystyle{ c = A\cdot b }[/math]. This is an [math]\displaystyle{ n\times 1 }[/math] vector. The numeric value of [math]\displaystyle{ c_i }[/math] is the imbalance in feature [math]\displaystyle{ i }[/math]: if [math]\displaystyle{ c_i\gt 0 }[/math] then there are more subjects with [math]\displaystyle{ i }[/math] in T and if [math]\displaystyle{ c_i\lt 0 }[/math] then there are more subjects with [math]\displaystyle{ i }[/math] in C.

The imbalance of a given partition is defined as:

[math]\displaystyle{ I(b) = ||A\cdot b||_\infty = \max_{i\in 1\dots,n}|c_i| }[/math]

The set balancing problem is to find a vector [math]\displaystyle{ b }[/math] which minimizes the imbalance [math]\displaystyle{ I(b) }[/math].

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 [math]\displaystyle{ b }[/math] randomly with probability 1/2 to each value in {1,-1}.

Surprisingly, although this algorithm completely ignores the matrix [math]\displaystyle{ A }[/math], it achieves a small imbalance with high probability when there are many features. Formally, for a random vector [math]\displaystyle{ b }[/math]:

[math]\displaystyle{ Prob\left[ I(b) \geq \sqrt{4m\ln n}\right] \leq \frac{2}{n} }[/math]

PROOF:

Let [math]\displaystyle{ k_i }[/math] be the total number of subjects that have feature [math]\displaystyle{ i }[/math] (equivalently, the number of ones in the [math]\displaystyle{ i }[/math]-th of the matrix [math]\displaystyle{ A }[/math]). Consider the following two cases:

Easy case: [math]\displaystyle{ k_i \leq \sqrt{4m\ln n} }[/math]. Then, with probability 1, the imbalance in feature [math]\displaystyle{ i }[/math] (that we marked by [math]\displaystyle{ c_i }[/math]) is at most [math]\displaystyle{ \sqrt{4m\ln n} }[/math].

Hard case: [math]\displaystyle{ k_i \gt \sqrt{4m\ln n} }[/math]. For every [math]\displaystyle{ j }[/math], let [math]\displaystyle{ X_j = a_{i,j}b_j }[/math]. Each such [math]\displaystyle{ X_j }[/math] is a random variable that can be either 1 or -1 with probability 1/2. The imbalance in feature [math]\displaystyle{ i }[/math] is: [math]\displaystyle{ c_i = \sum_{j=1}^m{X_j} }[/math]. Since the [math]\displaystyle{ X_j }[/math] are independent random variables, by the Chernoff bound, for every [math]\displaystyle{ a\gt 0 }[/math]:

[math]\displaystyle{ Prob\left[|c_i|\geq a\right] \leq 2 \exp(-a^2/2m) }[/math]

Select: [math]\displaystyle{ a=\sqrt{4m\ln n} }[/math] and get:

[math]\displaystyle{ Prob\left[|c_i|\geq \sqrt{4m\ln n}\right] \leq \frac{2}{n^2} }[/math]

By the union bound,

[math]\displaystyle{ Prob\left[\exists i: |c_i|\geq \sqrt{4m\ln n}\right] \leq \frac{2}{n} }[/math].