Balanced Incomplete Block Designs (BIBD)
Introduction:
Suppose you have 7 possible treatments for a disease, that you hope may work well singly or
in combination. You would like to try out every possible combination of them, but the
number of (non-empty) subsets of the set of 7 treatments is 27−1=127, and you have
only 7 mice in the lab who have this disease. You believe that using a pair of the treatments
together will have a more significant impact than adding more of the treatments, but even
trying every pair of treatments on a different mouse would require 7C2=21 mice.
Here is a strategy you could try: give each of the mice 3 of the treatments, according to the
following scheme. For 1≤i≤7, the treatments given to mouse i will be the elements of
the ith set in the following list
{1,2,3},{1,4,5},{1,6,7},{2,4,6},{2,5,7},{3,4,7},{3,5,6}
Careful perusal of this scheme will show that every pair of treatments is used together
on precisely one of the mice.
Definition: Design and Block
A design is a pair (V,B), where V is a finite set of points (varieties) and B is a collection of
subsets of V, called blocks of the design.
We use v to denote |V| and b to denote |B|.
Definition: Regular, Uniform, and Balanced Design
A regular design is a design in which every point appears in the same number of blocks, r.
A uniform design is a design in which every block contains the same number of points, k.
A balanced design is a design in which every pair of points appear together in the same
number of blocks, λ.
In our disease treatments for the mice, we have V= {1,2,3,4,5,6,7}
B={{1,2,3},{1,4,5},{1,6,7},{2,4,6},{2,5,7},{3,4,7},{3,5,6}}.
This is a regular, uniform, balanced design. In this design, v=7, b=7, r=3, k=3, and λ=1.
A regular, uniform, balanced design may be referred to as a (b,v,r,k,λ)-design. So our disease
treatments for the mice formed a (7,7,3,3,1)-design.
A (b,v,r,k,λ)-design is called complete if v=k. In this case, every block will contain every
point. A (b,v,r,k,λ)-design is called trivial if k=1. In this case, every block consists of a single
point, and no points appear together in a block. The case k=2 is also fairly trivial since in this
case, the blocks of the design must consist of the (v2) pairs of elements of v, each
occurring λ times.
Definition: Balanced Incomplete Block Design (BIBD)
A balanced incomplete block design (BIBD) is a regular, uniform, balanced design that is
not complete. So it is a (b,v,r,k,λ)-design with k<v.
Although this definition includes the possibility k=1 or k=2, these are not interesting cases,
and can usually be ignored.
Here is another BIBD. This one has parameters (20,16,5,4,1).
{a,b,c,d},{a,h,l,p},{c,g,i,n},{e,f,g,h},{b,e,j,o},{c,h,j,m},{i,j,k,l},{b,f,i,p},{d,e,k,n},
{m,n,o,p},{b,g,l,m},{d,f,l,m},{a,e,i,m},{b,h,k,n},{d,g,j,p},{a,f,j,n},{c,e,l,o},{d,h,i,o}
{a,g,k,o}, {c,f,k,p},
Here are the blocks of a BIBD with λ=1
What are the values of v, b, k, and r for this BIBD?