Неравенство Фишера является необходимым условием существования сбалансированной неполной блочной схемы , то есть системы подмножеств, удовлетворяющих определенным предписанным условиям комбинаторной математики . Обрисовано в общих чертах Рональдом Фишером , популяционным генетиком и статистиком , который занимался разработкой экспериментов, таких как изучение различий между несколькими различными разновидностями растений в каждом из ряда различных условий выращивания, называемых блоками .
Позволять:
- v быть количеством разновидностей растений;
- b - количество блоков.
Для сбалансированной неполной блочной конструкции необходимо, чтобы:
- k различных разновидностей в каждом блоке, 1 ≤ k < v ; ни одно разнообразие не встречается дважды в одном блоке;
- любые две разновидности входят ровно в λ блоков;
- каждая разновидность встречается ровно в r блоках.
Неравенство Фишера просто утверждает, что
- б ≥ v .
Доказательство
Пусть матрица инцидентности M представляет собой матрицу размера v × b, определенную так, что M i, j равно 1, если элемент i находится в блоке j, и 0 в противном случае. Тогда B = MM T - матрица размера v × v такая, что B i, i = r и B i, j = λ для i ≠ j . Поскольку r ≠ λ , det ( B ) ≠ 0 , то rank ( B ) = v ; с другой стороны, rank ( B ) ≤ rank ( M ) ≤ b , поэтому v ≤ b .
Обобщение
Неравенство Фишера справедливо для более общих классов планов. Попарно сбалансированная конструкция ( , или PBD) представляет собой набор X вместе с семейством непустых подмножеств X (которые не должны иметь одинаковый размер и может содержать повторы) таким образом, что каждая пара различных элементов X содержится ровно λ (положительное целое) подмножества. Множеству X разрешено быть одним из подмножеств, и если все подмножества являются копиями X , PBD называется «тривиальным». Размер X равен v, а количество подмножеств в семье (с учетом кратности) равно b .
Теорема: для любого нетривиального PBD v ≤ b . [1]
Этот результат также обобщает теорему Эрдеша – де Брейна :
Для PBD с λ = 1 , не имеющего блоков размера 1 или размера v , v ≤ b , с равенством тогда и только тогда, когда PBD является проективной плоскостью или почти пучком (что означает, что ровно n - 1 из точек коллинеарны ). [2]
В другом направлении Рэй-Чаудхури и Уилсон доказали в 1975 году, что в схеме 2 с - ( v , k , λ) количество блоков не менее. [3]
Заметки
- ^ Стинсон 2003 , pg.193
- ^ Стинсон 2003 , pg.183
- ^ Рэй-Чоудхури, Dijen К .; Уилсон, Ричард М. (1975), «О t- образных схемах » , Osaka Journal of Mathematics , 12 : 737–744, MR 0592624 , Zbl 0342.05018
Рекомендации
- RC Bose , "Примечание о неравенстве Фишера для сбалансированных неполных блочных схем", Annals of Mathematical Statistics , 1949, страницы 619–620.
- Р. А. Фишер, «Исследование различных возможных решений проблемы в неполных блоках», Annals of Eugenics , volume 10, 1940, страницы 52–75.
- Стинсон, Дуглас Р. (2003), Комбинаторные конструкции: конструкции и анализ , Нью-Йорк: Springer, ISBN 0-387-95487-2
- Улица, Энн Пенфолд ; Улица, Дебора Дж. (1987). Комбинаторика экспериментального дизайна . Оксфорд UP [Кларендон]. ISBN 0-19-853256-3.