Вероятность существования седловой точки
Оценим, насколько часто в матричных играх существуют седловые точки (в чистых стратегиях).
Теорема. Пусть элементы 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.
Смотрите также: