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

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

Позволять:

• v — количество разновидностей растений;
• b — количество блоков.

Чтобы получить сбалансированную неполную блочную конструкцию, требуется, чтобы:

• k разных сортов находятся в каждом блоке, 1 ≤ k < v ; ни одно разнообразие не встречается дважды в одном блоке;
• любые два многообразия встречаются вместе ровно в λ блоках;
• каждое разнообразие встречается ровно в r блоках.

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

b ≥ v .

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

Пусть матрица инцидентности M представляет собой матрицу размера v × b, определенную так, что M _i,j равно 1, если элемент i находится в блоке j , и 0 в противном случае. Тогда В = ММ ^Т — матрица размера 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 .

Этот результат также обобщает теорему Эрдеша – Де Брейна :

Для PBD с λ = 1 , не имеющего блоков размера 1 или размера v , v ≤ b с равенством тогда и только тогда, когда PBD является проективной плоскостью или почти карандашом (это означает, что ровно n - 1 точек лежат на одной прямой). ).

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

Ссылки

• Р. К. Бозе , «Заметки о неравенстве Фишера для сбалансированных неполных блочных конструкций», Анналы математической статистики , 1949, страницы 619–620.
• Р. А. Фишер, «Исследование различных возможных решений проблемы в неполных блоках», Анналы евгеники , том 10, 1940, страницы 52–75.
• Стинсон, Дуглас Р. (2003), Комбинаторные планы: конструкции и анализ , Нью-Йорк: Springer, ISBN  0-387-95487-2
• Стрит, Энн Пенфолд ; Стрит, Дебора Дж. (1987). Комбинаторика планирования эксперимента . Оксфорд, UP [Кларендон]. ISBN  0-19-853256-3 .