Главная страница 1

Вероятность существования седловой точки


Оценим, насколько часто в матричных играх существуют седловые точки (в чистых стратегиях).

Теорема. Пусть элементы mn матрицы (aij) являются независимыми случайными величинами с одинаковыми непрерывными функциями распределения. Тогда вероятность того, что матрица (aij) имеет седловую точку равна .

Доказательство. Для краткости будем называть матрицы, в которых все элементы попарно различны, типичными. В силу непрерывности функций распределения, мера множества нетипичных матриц равна нулю, поэтому P есть вероятность того, что типичная матрица имеет седловую точку. Последнюю вероятность и будем оценивать.

Рассмотрим случайное событие E(i,j), состоящее в том, что типичная матрица (aij) имеет пару (i,j) своей седловой точкой. В лекции 2 было показано, что выигрыши игроков в любых двух седловых точках равны, поэтому типичная матрица имеет не более одной седловой точки. Поэтому события E(i,j) являются взаимно исключающими и, следовательно, вероятность P равна сумме вероятностей событий E(i,j).

Так как элементы матрицы (aij) имеют одинаковые функции распределения, вероятности событий E(i,j) одинаковы. Поэтому, если p обозначает вероятность события E(1,1), то P=mnp. Остается найти величину p.

Отождествим матрицы (aij) с точками mn-мерного евклидова пространства. Гиперплоскости вида



a1i=a1j, i=1,…,n, j=1,…,n,

ai1=aj1, i=1,…,m, j=1,…,m,

a1i=aj1, i=1,…,n, j=1,…,m,

разбивают пространство на конечное число областей. Определим их количество.

Выберем в любой области произвольную точку и поставим ей в соответствие перестановку чисел a11,a12,…,a1n,a21,a31,…,am1, ставящую их в возрастающем порядке. Очевидно, что эта перестановка не зависит от выбранной точки, а зависит только от заданной области. Более того, построенное соответствие между областями и перестановками взаимно однозначно, поэтому число областей равно (m+n–1)!.

В силу симметрии задачи меры всех этих областей одинаковы.

Типичные матрицы, имеющие седловую точку, попадают в те области, для которых соответствующие перестановки ставят число a11 на m-е место, числа aj1 располагают раньше числа a11, а числа a1i – позже. Число таких перестановок равно (m–1)!(n–1)!.

Таким образом, и . Теорема доказана.



Нетрудно видеть, что вероятность P стремится к нулю при увеличении m и/или n.



Смотрите также:
Вероятность существования седловой точки
18.5kb.
9. Скорость материальной точки, движущейся в положительном направлении оси
28.31kb.
Вопросы по курсу «Теория вероятностей и математическая статистика»
32.64kb.
Билет Кинематика. Механическое движение. Материальная точка и абсолютно твердое тело. Кинематика материальной точки и поступательного движения твердого тела. Траектория, путь, перемещение, скорость, ускорение
575.02kb.
3. Культура Древнего Египта Приблизительные временные рамки существования египетской цивилизации с 3100 года до н э. до нашей эры
28.24kb.
Вероятность как загадка бытия и познания Ю. В. Сачков
437.67kb.
Инновационный конфликт на промышленном предприятии
69.54kb.
4 Области, в которых существенную роль играет вероятность Моделирование. Прогнозирование. Планирование Принцип неопределенного будущего и абстрактные науки
310.06kb.
Вопросы по специальности 01. 01
26.23kb.
Умц "диомен"
65.28kb.
Газеты «Пионерская правда» в разные годы ее существования
161.68kb.
С началом весенне-летнего сезона актуальной становится проблема укусов клещей. Нынешняя активность клещей наблюдается по всей России
57.28kb.