Fisher's inequality

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In combinatorial mathematics, Fisher's inequality, named after Ronald Fisher, is a necessary condition for the existence of a balanced incomplete block design satisfying certain prescribed conditions.

Fisher, a population geneticist and statistician, was concerned with the design of experiments studying the differences among several different varieties of plants, under each of a number of different growing conditions, called "blocks".

Let:

  • v be the number of varieties of plants;
  • b be the number of blocks.

It was required that:

  • k different varieties are in each block, k < v; no variety occurs twice in any one block;
  • any two varieties occur together in exactly λ blocks;
  • each variety occurs in exactly r blocks.

Fisher's inequality states simply that

 b \ge v.\,

Proof[edit]

Let the incidence matrix M be a v×b matrix defined so that Mi,j is 1 if element i is in block j and 0 otherwise. Then B=MMT is a v×v matrix such that Bi,i = r and Bi,j = λ for ij. Since r ≠ λ, det(B) ≠ 0, so rank(B) = v; on the other hand, rank(B) = rank(M) ≤ b, so vb.

Generalization[edit]

Fisher's inequality remains valid for more general classes of designs.

A pairwise balanced design (or PBD) is a set X together with a family of subsets of X (which need not have the same size and may contain repeats) such that every pair of distinct elements of X is contained in exactly λ (a positive integer) subsets. The set X is allowed to be one of the subsets, and if all the subsets are copies of X, th PBD is called trivial. The size of X is v and the number of subsets in the family (counted with multiplicity) is b.

Theorem: For any non-trivial PBD, vb.[1]

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

For a PBD with λ = 1 having no blocks of size 1 or size v, vb, with equality if and only if the PBD is a projective plane or a near-pencil.[2]

Notes[edit]

  1. ^ Stinson 2003, pg.193
  2. ^ Stinson 2003, pg.183

References[edit]

  • 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.
  • Stinson, Douglas R. (2003), Combinatorial Designs: Constructions and Analysis, New York: Springer, ISBN 0-387-95487-2 
  • Street, Anne Penfold and Street, Deborah J. (1987). Combinatorics of Experimental Design. Oxford U. P. [Clarendon]. pp. 400+xiv. ISBN 0-19-853256-3.