PROFILPELAJAR.COM

Нері́вність Фі́шера — це необхідна умова існування зрівноваженої неповної блок-схеми, тобто системи підмножин, які задовольняють певним умовам, вказаним у комбінаторній математиці. Нерівність описав Рональд Фішер, фахівець з популяційної генетики та статистики, який вивчав планування експерименту, досліджуючи відмінності серед деяких різновидів рослин за різних умов проростання, званих блоками.

Нехай:

$v$ — числом різновидів рослин;
$b$ — числом блоків.

Щоб бути зрівноваженою неповною блок-схемою, необхідно, щоб:

$k$ різних різновидів у кожному блоці, $1\leqslant k<v$ , ніякий різновид не зустрічається в блоці двічі
будь-які два різновиди зустрічаються разом рівно в $\lambda$ блоках
кожен різновид зустрічається рівно в $r$ блоках.

Нерівність Фішера стверджує, що

b\geqslant v

.

Доведення

Нехай матриця суміжності $\mathbf {M}$ є $v\times b$ матрицею, визначеною так, що $\mathbf {M} _{i,j}$ дорівнює 1, якщо елемент $i$ міститься в блоці $j$ , і 0 в іншому разі. Тоді $\mathbf {B} =\mathbf {MM} ^{T}$ є $v\times v$ матрицею, такою, що $\mathbf {B} _{i,i}=r$ і $\mathbf {B} _{i,j}=\lambda$ для $i\neq 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$ .

Узагальнення

Нерівність Фішера істинна для загальніших класів блок-схем. Попарно зрівноважена схема (ПЗС, англ. pairwise balanced design, PBD) — це множина $X$ разом із сімейством непорожніх підмножин $X$ (які не обов'язково мають бути одного розміру і можуть містити повторення), така, що будь-яка пара різних елементів $X$ міститься рівно в $\lambda$ (додатне ціле число) підмножин. Множині $X$ дозволено бути однією з підмножин і, якщо всі підмножини є копіями $X$ , ПЗС називають «тривіальною». Нехай розмір множини $X$ дорівнює $v$ , а число підмножин у сімействі (з урахуванням кратності) дорівнює $b$ .

Теорема: Для будь-якої нетривіальної ПЗС $v\leqslant b$ ^[1].

Цей результат узагальнює теорему де Брейна — Ердеша: Для ПЗС з $\lambda =1$ , яка не має блоків розміру 1 або розміру $v,v\leqslant b$ , з рівністю тоді й лише тоді, коли ПЗС є проєктивною площиною або майже пучком (що означає, що рівно $n-1$ точок колінеарні)^[2].

З іншого боку, 1975 року Рей Чадхурі та Вільсон довели, що в схемі $2s-(v,k,\lambda )$ число блоків не менше ніж ${\binom {v}{s}}$ ^[3].

Примітки

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

Література

Dijen K. Ray-Chaudhuri, Richard M. Wilson. On t-designs // Osaka Journal of Mathematics. — 1975. — Т. 12 (17 січня).
Bose R. C. A Note on Fisher's Inequality for Balanced Incomplete Block Designs // Annals of Mathematical Statistics. — 1949. — 17 січня. — С. 619–620.
Fisher R. A. An examination of the different possible solutions of a problem in incomplete blocks // Annals of Eugenics. — 1940. — Т. 10 (17 січня). — С. 52–75.
Douglas R. Stinson. Combinatorial Designs: Constructions and Analysis. — New York : Springer, 2003. — ISBN 0-387-95487-2.
Anne Penfold Street, Deborah J. Street,. Combinatorics of Experimental Design. — =Oxford U. P. [Clarendon], 1987. — С. 400+xiv. — ISBN 0-19-853256-3.