Нерівність Фішера

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

Нехай:

• $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$.

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

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

Література

• Dijen K. Ray-Chaudhuri, Richard M. Wilson. On t-designs // Osaka Journal of Mathematics. — 1975. — Т. 12 (21 квітня).
• Bose R. C. A Note on Fisher's Inequality for Balanced Incomplete Block Designs // Annals of Mathematical Statistics. — 1949. — 21 квітня. — С. 619–620.
• Fisher R. A. An examination of the different possible solutions of a problem in incomplete blocks // Annals of Eugenics. — 1940. — Т. 10 (21 квітня). — С. 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.