Fisher's inequality

Fisher's inequality is a necessary condition for the existence of a balanced incomplete block design, that is, a system of subsets that satisfy certain prescribed conditions in combinatorial mathematics. Outlined by Ronald Fisher, a population geneticist and statistician, who was concerned with the design of experiments such as studying the differences among several different varieties of plants, under each of a number of different growing conditions, called blocks.

Let:

• Template:Math be the number of varieties of plants;
• Template:Math be the number of blocks.

To be a balanced incomplete block design it is required that:

• Template:Math different varieties are in each block, Template:Math; no variety occurs twice in any one block;
• any two varieties occur together in exactly Template:Math blocks;
• each variety occurs in exactly Template:Math blocks.

Fisher's inequality states simply that

Template:Math.

Proof

Let the incidence matrix Template:Math be a Template:Math matrix defined so that Template:Math is 1 if element Template:Math is in block Template:Math and 0 otherwise. Then Template:Math is a Template:Math matrix such that Template:Math and Template:Math for Template:Math. Since Template:Math, Template:Math, so Template:Math; on the other hand, Template:Math, so Template:Math.

Generalization

Fisher's inequality is valid for more general classes of designs. A pairwise balanced design (or PBD) is a set Template:Math together with a family of non-empty subsets of Template:Math (which need not have the same size and may contain repeats) such that every pair of distinct elements of Template:Math is contained in exactly Template:Math (a positive integer) subsets. The set Template:Math is allowed to be one of the subsets, and if all the subsets are copies of Template:Math, the PBD is called "trivial". The size of Template:Math is Template:Math and the number of subsets in the family (counted with multiplicity) is Template:Math.

Theorem: For any non-trivial PBD, Template:Math.

This result also generalizes the Erdős–De Bruijn theorem:

For a PBD with Template:Math having no blocks of size 1 or size Template:Mvar, Template:Math, with equality if and only if the PBD is a projective plane or a near-pencil (meaning that exactly Template:Math of the points are collinear).

In another direction, Ray-Chaudhuri and Wilson proved in 1975 that in a Template:Math design, the number of blocks is at least $(\genfrac{}{}{0ex}{}{v}{s})$.

References

• R. C. Bose, "A Note on Fisher's Inequality for Balanced Incomplete Block Designs", Annals of Mathematical Statistics, 1949, pages 619–620.
• R. A. Fisher, "An examination of the different possible solutions of a problem in incomplete blocks", Annals of Eugenics, volume 10, 1940, pages 52–75.
• Template:Citation
• Template:Cite book