Неравенство Фишера — это необходимое условие существования сбалансированной неполной блок-схемы, то есть системы подмножеств, которые удовлетворяют определённым предписанным условиям в комбинаторной математике. Неравенство описал Рональд Фишер, специалист по популяционной генетике и статистике, который изучал планирование эксперимента, изучая различия среди некоторых отличающихся разновидностей растений при различных условиях произрастания, называемых блоками.
Пусть:
будет числом разновидностей растений; будет числом блоков.
Чтобы быть сбалансированной неполной блок-схемой, необходимо, чтобы:
различных разновидностей в каждом блоке, , никакая разновидность не встречается дважды в блоке любые две разновидности встречаются вместе ровно в блоках каждая разновидность встречается ровно в блоках.
Неравенство Фишера утверждает, что .
Доказательство Пусть матрица смежности является матрицей, определённой так, что равен 1, если элемент содержится в блоке , и 0 в противном случае. Тогда является матрицей, такой, что и для . Поскольку , так что . С другой стороны, , так что .
Обобщение Неравенство Фишера верно для более общих классов блок-схем. Попарно сбалансированная схема (ПСС, , PBD) — это множество вместе с семейством непустых подмножеств (которые не обязательно должны быть одного размера и могут содержать повторения), такое, что любая пара различных элементов содержится точности в (положительное целое число) подмножествах. Множеству разрешено быть одним из подмножеств и, если все подмножества являются копиями , ПСС называется «тривиальной». Пусть размер множества равно , а число подмножества в семействе (учитывая кратность) равно .
Теорема: Для любой нетривиальной ПСС .
Этот результат обобщает теорему де Брёйна — Эрдёша:
Для ПСС с , не имеющей блоков размера 1 или размера , с равенством тогда и только тогда, когда ПСС является проективной плоскостью или почти пучком (что означает, что в точности точек коллинеарны).
В другом направлении, в 1975 году Рэй Чадхури и Вильсон доказали, что в схеме число блоков не меньше .
Примечания
Литература
Категория:Планирование эксперимента Категория:Семейства множеств Категория:Вероятностные неравенства