Fishers ulighed

Fishers ulighed er en nødvendig betingelse for eksistensen af et afbalanceret ufuldstændigt blokdiagram , det vil sige et system af delmængder, der opfylder visse foreskrevne betingelser i kombinatorisk matematik . Uligheden blev beskrevet af Ronald Fisher , en befolkningsgenetiker og statistiker , som studerede eksperimentelt design ved at studere forskellene mellem nogle forskellige plantesorter under forskellige vækstbetingelser, kaldet blokke .

Lade:

$v$ vil være antallet af plantesorter;
$b$ vil være antallet af blokke.

For at være et afbalanceret ufuldstændigt blokdiagram er det nødvendigt, at:

$k$ forskellige sorter i hver blok, ingen sort forekommer to gange i en blok $1\leqslant k<v$
alle to varianter forekommer sammen nøjagtigt i blokke $\lambda$
hver sort forekommer nøjagtigt i blokke. $r$

Fishers ulighed siger det

b\geqslant v

Bevis

Lad tilstødende matrix være en matrix defineret således, at den er lig med 1, hvis elementet er indeholdt i blokken og 0 ellers. Så er en matrix som for . Fordi , så . På den anden side, , så . $\mathbf {M}$ $v\times b$ ${\displaystyle \mathbf {M} _{i,j))$ $jeg$ $j$ ${\displaystyle \mathbf {B} =\mathbf {MM} ^{T))$ $v\times v$ $\mathbf {B} _{i,i}=r$ $\mathbf {B} _{i,j}=\lambda$ $i \ne j$ $r\neq \lambda ,det(\mathbf {B} )\neq 0$ $rank(\mathbf {B} )=v$ $rank(\mathbf {B} )\leqslant rank(\mathbf {M} )\leqslant b$ $v\leqslant b$

Generalisering

Fishers ulighed gælder for mere generelle klasser af rutediagrammer. Et parvis balanceret design (PSS, eng. pairwise balanced design , PBD) er et sæt sammen med en familie af ikke-tomme delmængder (som ikke behøver at have samme størrelse og kan indeholde gentagelser), således at ethvert par af forskellige elementer er indeholdt i nøjagtigt (positive heltal ) delmængder. Et sæt tillades at være et af undersættene, og hvis alle undersæt er kopier , siges PSS'en at være "triviel". Lad størrelsen af mængden være , og antallet af delmængder i familien (under hensyntagen til multipliciteten) være . $x$ $x$ $x$ $\lambda$ $x$ $x$ $x$ $v$ $b$

Sætning: For enhver ikke-triviel PSS [1] . $v\leqslant b$

Dette resultat generaliserer de Bruijn-Erdős sætning :

For en PSS uden blokke af størrelse 1 eller størrelse , med lighed, hvis og kun hvis PSS er et projektivt plan eller næsten en bunke (hvilket betyder, at præcis punkterne er kollineære ) [2] . $\lambda=1$ $v,v\leqslant b$ $n-1$

I en anden retning beviste Ray Chadhuri og Wilson i 1975, at antallet af blokke i kredsløbet er mindst [3] . $2s-(v,k,\lambda )$ ${\binom {v}{s))$

Noter

↑ Stinson, 2003 , s. 193.
↑ Stinson, 2003 , s. 183.
↑ Ray-Chaudhuri, Wilson, 1975 , s. 737-744.

Litteratur

Dijen K. Ray-Chaudhuri, Richard M. Wilson. On t-designs // Osaka Journal of Mathematics. - 1975. - T. 12 .
Bose RC En note om Fishers ulighed for balancerede ufuldstændige blokdesigns // Annals of Mathematical Statistics . - 1949. - S. 619-620 .
Fisher RA En undersøgelse af de forskellige mulige løsninger på et problem i ufuldstændige blokke // Annals of Eugenics . - 1940. - T. 10 . — S. 52–75 .
Douglas R. Stinson. Kombinatoriske designs: konstruktioner og analyse. - New York: Springer, 2003. - ISBN 0-387-95487-2 .
Anne Penfold Street, Deborah J. Street,. Eksperimentelt designs kombinatorik. - = Oxford UP [Clarendon], 1987. - s. 400+xiv. — ISBN 0-19-853256-3 .