Імовірнісний метод

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Ця стаття не про інтерактивні системи доведення, що використовують ймовірність для переконання верифікатора в тому, що доведення коректне, не про імовірнісні алгоритми, що дають правильну відповідь з високою імовірністю проте без гарантії, не про методи Монте Карло, що є методами моделювання на основі псевдо-випадковості.

Імовірнісний метод являє собою метод неконструктивного доведення, що, в першу чергу, використовується у комбінаториці та винайдений Паулем Ердьошем, для доведення існування наперед визначеного виду математичних об'єктів. Він працює через демонстрацію того, що, якщо випадково обрати об'єкти з деякого класу, ймовірність того, що результат є визначеного вигляду, більше нуля. Хоча доведення використовує ймовірність, кінцевий висновок визначається напевно, без будь-якої похибки.

Цей метод досі застосовується у різних галузях математики таких, як теорія чисел, лінійна алгебра, та аналіз.

Вступ[ред.ред. код]

Якщо кожен об'єкт у наборі об'єктів не має певної властивості, тоді імовірність, що випадковий об'єкт, обраний з цього набору має цю властивість, становить нуль. І у зворотному напрямку, якщо імовірність, що випадковий об'єкт має цю властивість, більше нуля, тоді це доводить існування принаймні одного об'єкта у даному наборі, що має цю властивість. Навіть якщо ймовірність дуже мала; будь-яка позитивна ймовірність доводить це твердження.

Аналогічно, демонстрація того, що ймовірність (строго) менше 1, може бути використане для доведення існування об'єкта, що не задовольняє наперед визначеним вимогам.

Ще один спосіб використання імовірнісного методу — це обчислення очікуваної значення деякої випадкової змінної. Якщо може бути показано, що деяка випадкова змінна може приймати значення менше ніж очікуване, це доводить, що випадкова змінна може також приймати деяке значення більше, ніж очікуване.

Загальноприйняті інструменти у імовірнісному методі включають нерівність Маркова, границю Чернова, та локальну лему Ловаша.

Дивіться також[ред.ред. код]

Посилання[ред.ред. код]