Fishers ojämlikhet
Fishers ojämlikhet är ett nödvändigt villkor för existensen av en balanserad ofullständig blockdesign , det vill säga ett system av delmängder som uppfyller vissa föreskrivna villkor i kombinatorisk matematik . Skisserat av Ronald Fisher , en populationsgenetiker och statistiker , som var oroad över utformningen av experiment som att studera skillnaderna mellan flera olika sorter av växter, under var och en av ett antal olika odlingsförhållanden, kallade block .
Låta:
- v vara antalet sorter av växter;
- b vara antalet block.
För att vara en balanserad ofullständig blockdesign krävs att:
- k olika sorter finns i varje block, 1 ≤ k < v ; ingen sort förekommer två gånger i ett block;
- två valfria sorter förekommer tillsammans i exakt λ -block;
- varje sort förekommer i exakt r block.
Fishers ojämlikhet säger helt enkelt det
- b ≥ v .
Bevis
Låt incidensmatrisen M vara en v × b -matris definierad så att Mi ,j är 1 om element i är i block j och 0 annars. Då B = MM T en v × v -matris så att Bi ,i = r och Bi ,j = λ för i ≠ j . Eftersom r ≠ λ , det( B ) ≠ 0 , så rank( B ) = v ; å andra sidan rank( B ) ≤ rank( M ) ≤ b , alltså v ≤ b .
Generalisering
Fishers ojämlikhet är giltig för mer allmänna klasser av design. En parvis balanserad design (eller PBD) är en mängd X tillsammans med en familj av icke-tomma delmängder av X (som inte behöver ha samma storlek och kan innehålla upprepningar) så att varje par av distinkta element i X ingår i exakt λ (ett positivt heltal) delmängder. Mängden X tillåts vara en av delmängderna, och om alla delmängder är kopior av X kallas PBD "trivial". Storleken på X är v och antalet delmängder i familjen (räknat med multiplicitet) är b .
Teorem: För alla icke-triviella PBD, v ≤ b .
Detta resultat generaliserar också Erdős–De Bruijn-satsen :
För en PBD med λ = 1 utan block av storlek 1 eller storlek v , v ≤ b , med likhet om och endast om PBD är ett projektivt plan eller en nära-penna (vilket betyder att exakt n − 1 av punkterna är kolinjära ).
I en annan riktning bevisade Ray-Chaudhuri och Wilson 1975 att i en 2 s -( v , k , λ) design är antalet block minst .
Anteckningar
- RC Bose , "A Note on Fisher's Inequality for Balanced Incomplete Block Designs", Annals of Mathematical Statistics , 1949, sidorna 619–620.
- RA Fisher, "En undersökning av de olika möjliga lösningarna av ett problem i ofullständiga block", Annals of Eugenics , volym 10, 1940, sidorna 52–75.
- Stinson, Douglas R. (2003), Combinatorial Designs: Constructions and Analysis , New York: Springer, ISBN 0-387-95487-2
- Street, Anne Penfold ; Street, Deborah J. (1987). Experimentell designs kombinatorik . Oxford UPP [Clarendon]. ISBN 0-19-853256-3 .
