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

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

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

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

Вступ

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

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

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

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

Див. також

Випадковий граф
Імовірнісні доведення неімовірнісних теорем
Інтерактивна система доведення

Посилання

Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2ed). New York: Wiley-Interscience. ISBN 0-471-37046-0.
- Алон Н., Спенсер Дж. Вероятностный метод, Бином, 2007, с. 320, 1100 экз. ISBN 978-5-94774-556-6
Erdős, P. (1959). Graph theory and probability (PDF). Canad. J. Math. 11: 34—38. MR 0102081. Архів оригіналу (PDF) за 18 липня 2011. Процитовано 30 січня 2010.
Erdős, P. (1961). Graph theory and probability, II (PDF). Canad. J. Math. 13: 346—352. MR 0120168. Архів оригіналу (PDF) за 18 липня 2011. Процитовано 30 січня 2010.
J. Matoušek, J. Vondrak. The Probabilistic Method. Lecture notes.
Alon, N and Krivelevich, M (2006). Extremal and Probabilistic Combinatorics [Архівовано 9 червня 2011 у Wayback Machine.]
И.Е. Клейнер, видео лекции [Архівовано 27 вересня 2016 у Wayback Machine.]