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:
- vScript error: No such module "Check for unknown parameters". be the number of varieties of plants;
- bScript error: No such module "Check for unknown parameters". be the number of blocks.
To be a balanced incomplete block design it is required that:
- kScript error: No such module "Check for unknown parameters". different varieties are in each block, 1 ≤ k < vScript error: No such module "Check for unknown parameters".; no variety occurs twice in any one block;
- any two varieties occur together in exactly λScript error: No such module "Check for unknown parameters". blocks;
- each variety occurs in exactly rScript error: No such module "Check for unknown parameters". blocks.
Fisher's inequality states simply that
- b ≥ vScript error: No such module "Check for unknown parameters"..
Proof
Let the incidence matrix MScript error: No such module "Check for unknown parameters". be a v × bScript error: No such module "Check for unknown parameters". matrix defined so that Mi,jScript error: No such module "Check for unknown parameters". is 1 if element iScript error: No such module "Check for unknown parameters". is in block jScript error: No such module "Check for unknown parameters". and 0 otherwise. Then B = MMTScript error: No such module "Check for unknown parameters". is a v × vScript error: No such module "Check for unknown parameters". matrix such that Bi,i = rScript error: No such module "Check for unknown parameters". and Bi,j = λScript error: No such module "Check for unknown parameters". for i ≠ jScript error: No such module "Check for unknown parameters".. Since r ≠ λScript error: No such module "Check for unknown parameters"., det(B) ≠ 0Script error: No such module "Check for unknown parameters"., so rank(B) = vScript error: No such module "Check for unknown parameters".; on the other hand, rank(B) ≤ rank(M) ≤ bScript error: No such module "Check for unknown parameters"., so v ≤ bScript error: No such module "Check for unknown parameters"..
Generalization
Fisher's inequality is valid for more general classes of designs. A pairwise balanced design (or PBD) is a set XScript error: No such module "Check for unknown parameters". together with a family of non-empty subsets of XScript error: No such module "Check for unknown parameters". (which need not have the same size and may contain repeats) such that every pair of distinct elements of XScript error: No such module "Check for unknown parameters". is contained in exactly λScript error: No such module "Check for unknown parameters". (a positive integer) subsets. The set XScript error: No such module "Check for unknown parameters". is allowed to be one of the subsets, and if all the subsets are copies of XScript error: No such module "Check for unknown parameters"., the PBD is called "trivial". The size of XScript error: No such module "Check for unknown parameters". is vScript error: No such module "Check for unknown parameters". and the number of subsets in the family (counted with multiplicity) is bScript error: No such module "Check for unknown parameters"..
Theorem: For any non-trivial PBD, v ≤ bScript error: No such module "Check for unknown parameters"..[1]
This result also generalizes the Erdős–De Bruijn theorem:
For a PBD with λ = 1Script error: No such module "Check for unknown parameters". having no blocks of size 1 or size Template:Mvar, v ≤ bScript error: No such module "Check for unknown parameters"., with equality if and only if the PBD is a projective plane or a near-pencil (meaning that exactly n − 1Script error: No such module "Check for unknown parameters". of the points are collinear).[2]
In another direction, Ray-Chaudhuri and Wilson proved in 1975 that in a 2s-(v, k, λ)Script error: No such module "Check for unknown parameters". design, the number of blocks is at least .[3]
Notes
<templatestyles src="Reflist/styles.css" />
Script error: No such module "Check for unknown parameters".
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.
- Script error: No such module "citation/CS1".
- Script error: No such module "citation/CS1".