Неравенство Фишера

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

Пусть:

• ${\displaystyle v}$ будет числом разновидностей растений;
• ${\displaystyle b}$ будет числом блоков.

Чтобы быть сбалансированной неполной блок-схемой, необходимо, чтобы:

• ${\displaystyle k}$ различных разновидностей в каждом блоке, ${\displaystyle 1\leqslant k<v}$, никакая разновидность не встречается дважды в блоке
• любые две разновидности встречаются вместе ровно в ${\displaystyle \lambda }$ блоках
• каждая разновидность встречается ровно в ${\displaystyle r}$ блоках.

Неравенство Фишера утверждает, что

${\displaystyle b\geqslant v}$.

Доказательство

Пусть матрица смежности ${\displaystyle \mathbf {M} }$ является ${\displaystyle v\times b}$ матрицей, определённой так, что ${\displaystyle \mathbf {M} _{i,j}}$ равен 1, если элемент ${\displaystyle i}$ содержится в блоке ${\displaystyle j}$, и 0 в противном случае. Тогда ${\displaystyle \mathbf {B} =\mathbf {MM} ^{T}}$ является ${\displaystyle v\times v}$ матрицей, такой, что ${\displaystyle \mathbf {B} _{i,i}=r}$ и ${\displaystyle \mathbf {B} _{i,j}=\lambda }$ для ${\displaystyle i\neq j}$. Поскольку ${\displaystyle r\neq \lambda ,det(\mathbf {B} )\neq 0}$, так что ${\displaystyle rank(\mathbf {B} )=v}$. С другой стороны, ${\displaystyle rank(\mathbf {B} )\leqslant rank(\mathbf {M} )\leqslant b}$, так что ${\displaystyle v\leqslant b}$.

Обобщение

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

Теорема: Для любой нетривиальной ПСС ${\displaystyle v\leqslant b}$^[1].

Этот результат обобщает теорему де Брёйна — Эрдёша:

Для ПСС с ${\displaystyle \lambda =1}$, не имеющей блоков размера 1 или размера ${\displaystyle v,v\leqslant b}$, с равенством тогда и только тогда, когда ПСС является проективной плоскостью или почти пучком (что означает, что в точности ${\displaystyle n-1}$ точек коллинеарны)^[2].

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

Примечания

1. Stinson, 2003, с. 193.
2. Stinson, 2003, с. 183.
3. Ray-Chaudhuri, Wilson, 1975, с. 737–744.

Литература

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