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

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

Пусть:

  • будет числом разновидностей растений;
  • будет числом блоков.

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

  • различных разновидностей в каждом блоке, , никакая разновидность не встречается дважды в блоке
  • любые две разновидности встречаются вместе ровно в блоках
  • каждая разновидность встречается ровно в блоках.

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

.

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

Пусть матрица смежности является матрицей, определённой так, что равен 1, если элемент содержится в блоке , и 0 в противном случае. Тогда является матрицей, такой, что и для . Поскольку , так что . С другой стороны, , так что .

Обобщение

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

Теорема: Для любой нетривиальной ПСС [1].

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

Для ПСС с , не имеющей блоков размера 1 или размера , с равенством тогда и только тогда, когда ПСС является проективной плоскостью или почти пучком (что означает, что в точности точек коллинеарны)[2].

В другом направлении, в 1975 году Рэй Чадхури и Вильсон доказали, что в схеме число блоков не меньше [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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.