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

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

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

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

Вступ

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

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

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

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

Див. також

• Випадковий граф

Посилання

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