Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Fisher's inequality
Summary
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:
v be the number of varieties of plants;
b be the number of blocks.
To be a balanced incomplete block design it is required that:
k different varieties are in each block, 1 ≤ 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 ≥ v.
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 i ≠ j. Since r ≠ λ, det(B) ≠ 0, so rank(B) = v; on the other hand, rank(B) ≤ rank(M) ≤ b, so v ≤ b.
Fisher's inequality is valid for more general classes of designs. A pairwise balanced design (or PBD) is a set X together with a family of non-empty 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, the 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, v ≤ b.
This result also generalizes the Erdős–De Bruijn theorem:
For a PBD with λ = 1 having no blocks of size 1 or size v, v ≤ b, with equality if and only if the PBD is a projective plane or a near-pencil (meaning that exactly n − 1 of the points are collinear).
In another direction, Ray-Chaudhuri and Wilson proved in 1975 that in a 2s-(v, k, λ) design, the number of blocks is at least .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.