Числовая матрица называется дважды стохастической, если ее элементы неотрицательны, и в каждой строке и каждом столбце сумма элементов равна единице. Сумма всех элементов такой матрицы равна, с одной стороны, числу ее строк, а, с другой стороны, числу столбцов. Значит, дважды стохастическая матрица является квадратной. Подстановочная матрица состоит только из нулей и единиц, причем в каждой строке и каждом столбце содержится ровно одна единица. Ясно, что подстановочная матрица является дважды стохастической. Подстановочным множеством матрицы называется множество ее элементов, содержащее по одному элементу из каждой строки и каждого столбца. Дважды стохастические матрицы Теорема 7. Всякая дважды стохастическая матрица А = (а^) имеет подстановочное множество, состоящее из ненулевых элементов. Пусть матрица Л имеет размер п х п. Минимальное число линий, содержащих все ненулевые элементы матрицы Л, равно п, поскольку сумма элементов всей матрицы равна п, а каждой линии - 1. Рассмотрим матрицу В, которая получается из матрицы Л заменой ненулевых элементов на единицы. Минимальное число покрывающих линий матрицы В - такое же, как и для матрицы Л, то есть п. По венгерской теореме в матрице В есть п независимых единиц. Эти единицы задают подстановочное множество матрицы Очевидно, что подстановочное множество существует и для ненулевой матрицы из неотрицательных элементов с одинаковыми суммами по строкам и столбцам. Теорема 8 (Г. Биркгоф, 1946 г.). Всякая дважды стохастическая матрица представима в виде выпуклой комбинации подстановочных матриц. * Пусть Pi - подстановочная матрица, порожденная подстановочным множеством М\ из ненулевых элементов дважды стохастической матрицы Л, а число ci - наименьший элемент в М\. Тогда матрица А - С\Р\ состоит из неотрицательных элементов и имеет одинаковые суммы по строкам и столбцам, и в ней ненулевых элементов меньше, чем у исходной матрицы. Повторяя данное преобразование, через конечное число шагов приходим к равенству где - подстановочная матрица для каждого i. Пусть матрица А имеет размер п х п. Так как сумма всех элементов каждой из матриц равна п, из следует:. Таким образом, найденная линейная комбинация является выпуклой. Замечание 1. Доказательство теоремы носит конструктивный характер. Описанный процесс получения разложения называют алгоритмом Биркгофа. Поскольку каждый шаг этого алгоритма дает требуемое значение по меньшей мере одному элементу матрицы Л, а последний шаг - сразу п элементам матрицы, получаем неравенство, где к - число подстановочных матриц, через которые линейно выражается дважды стохастическая матрица Л. Известна и более точная оценка: Дважды стохастические матрицы Замечание 2. Представим каждую дважды стохастическую матрицу размера пх п точкой в п2-мерном пространстве. Геометрический смысл теоремы Биркгофа следующий: многогранник дважды стохастических матриц имеет своими вершинами подстановочные матрицы.

$A=(a\_\{ij\})$ с неотрицательными вещественными элементами, в которой все её строчные и столбцовые суммы равны 1, то есть

$\backslash sum\_i\; a\_\{ij\}=\backslash sum\_j\; a\_\{ij\}=1$.

Множество всех дважды стохастических матриц обозначается через $\backslash Omega\_n$.

Свойства

Напишите отзыв о статье "Дважды стохастическая матрица"

Примечания

Литература

• Минк Х. Перманенты. - М .: Мир, 1982. - 211 с.
• Прасолов В. В. Задачи и теоремы линейной алгебры. - М .: Наука, 1996. - 304 с. - ISBN 5-02-014727-3 .

Отрывок, характеризующий Дважды стохастическая матрица

Ей казалось, что то тяжелое, равномерно ударяя, стучит во все стены избы: это билось ее замиравшее от страха, от ужаса и любви разрывающееся сердце.
Она отворила дверь, перешагнула порог и ступила на сырую, холодную землю сеней. Обхвативший холод освежил ее. Она ощупала босой ногой спящего человека, перешагнула через него и отворила дверь в избу, где лежал князь Андрей. В избе этой было темно. В заднем углу у кровати, на которой лежало что то, на лавке стояла нагоревшая большим грибом сальная свечка.
Наташа с утра еще, когда ей сказали про рану и присутствие князя Андрея, решила, что она должна видеть его. Она не знала, для чего это должно было, но она знала, что свидание будет мучительно, и тем более она была убеждена, что оно было необходимо.
Весь день она жила только надеждой того, что ночью она уввдит его. Но теперь, когда наступила эта минута, на нее нашел ужас того, что она увидит. Как он был изуродован? Что оставалось от него? Такой ли он был, какой был этот неумолкавший стон адъютанта? Да, он был такой. Он был в ее воображении олицетворение этого ужасного стона. Когда она увидала неясную массу в углу и приняла его поднятые под одеялом колени за его плечи, она представила себе какое то ужасное тело и в ужасе остановилась. Но непреодолимая сила влекла ее вперед. Она осторожно ступила один шаг, другой и очутилась на середине небольшой загроможденной избы. В избе под образами лежал на лавках другой человек (это был Тимохин), и на полу лежали еще два какие то человека (это были доктор и камердинер).

С неотрицательными элементами такими, что

При любом i. Множество всех С. м. n-го порядка представляет собой выпуклую оболочку п n С. м., составленных из нулей и единиц. Любую С. м. Рможно рассматривать как переходных вероятностей матрицу цепи Маркова с дискретным временем.
Абсолютные величины собственных значений С. м. не превосходят единицы; является собственным значением любой С. м. Если С. м. Рнеразложима ( Маркова имеет один положительный состояний), то единица является простым собственным значением матрицы Р(т. е. имеет кратность 1); в общем случае кратность собственного значения 1 совпадает с числом положительных классов цепи Маркова Если С. м. неразложима и положительный класс состояний цепи Маркова имеет d, то всех собственных значений матрицы Р, как множество точек комплексной плоскости, переходит в себя при повороте на При d=l С. м. Ри цепь Маркова наз. непериодическими.
Левые собственные векторы С. м. Рконечного порядка, соответствующие единичному собственному значению:

и удовлетворяющие условиям определяют стационарные распределения цепи Маркова в случае неразложимой С. м. Рстационарное единственно.
Если Р - неразложимая непериодическая С. м. конечного порядка, то существует

где П - матрица, каждая строка к-рой совпадает с вектором (см. также Маркова цепь эргодическая ;для бесконечных С. м. . система уравнений (1) может не иметь ненулевых решений, удовлетворяющих условию в этом случае матрица П - нулевая). Скорость сходимости в (2) можно оценить геометрич. прогрессией с любым показателем к-рый по модулю больше всех собственных значений матрицы Р, отличных от 1.
Если - С. м. ге-го порядка, то любое ее удовлетворяет неравенству (см. ):

Описано множество М п, являющееся объединением множеств собственных значений всех С. м. n-го порядка (см. ).
С. м. удовлетворяющая дополнительному условию

наз. дважды стохастической матрицей. Множество дважды стохастич. матриц n-го порядка представляет собой выпуклую оболочку перестановочных матриц ге-го порядка (т. е. дважды стохастич. матриц, составленных из нулей и единиц). Стационарное распределение конечной цепи Маркова с дважды стохастич. матрицей Рявляется равномерным.

Лит. : Гантмахер Ф. Р., Теория матриц, 3 изд., М., 1967; Беллман Р., Введение в теорию матриц, пер. е англ., М., 1969; Маркус М., Минк X., Обзор по теории матриц и матричных неравенств, пер. с англ., М., 1972; Карпелевич Ф. И., лИзв. АН СССР. Сер. матем.

Математическая энциклопедия. - М.: Советская энциклопедия . И. М. Виноградов . 1977-1985 .

Смотреть что такое "СТОХАСТИЧЕСКАЯ МАТРИЦА" в других словарях:

В теории вероятности это матрица, чьи строки или колонки дают в сумме единицу. Содержание 1 Определения 2 Замечание 3 Cвойства … Википедия

У этого термина существуют и другие значения, см. Цепи Маркова#Переходная матрица и однородные цепи. Матрицей перехода от базиса к базису является матрица, столбцы которой координаты разложения векторов в базисе. Обозначается … Википедия

Матрица в математике, система элементов aij (чисел, функций или иных величин, над которыми можно производить алгебраические операции), расположенных в виде прямоугольной схемы. Если схема имеет m строк и n столбцов, то говорят о (m n) матрице.… …

Метод решения класса задач статистич. оценивания, в к ром новое значение оценки представляет собой поправку к уже имеющейся оценке, основанную на новом наблюдении. Первая процедура С. а. была предложена в 1951 X. Роббинсом(Н. Robbins) и С. Монро… … Математическая энциклопедия

I Матрица (нем. Matrize, от латинского matrix матка, источник, начало) в полиграфии, 1) сменный элемент литейной формы с углублённым (иногда фотографическим) изображением буквы или знака, используемый при отливке типографских… … Большая советская энциклопедия

Слово стохастический (от греч. στοχαστικός «умеющий угадывать») используется во многих терминах из разных областей науки, и в общем означает неопределённость, случайность чего либо. В теории вероятностей итог стохастического процесса не… … Википедия

- (др. греч. στόχος цель, предположение) означает случайность. Стохастический процесс это процесс, поведение которого не является детерминированным, и последующее состояние такой системы описывается как величинами, которые могут быть предсказаны,… … Википедия

У этого термина существуют и другие значения, см. Матрицы переходных вероятностей. Матрицей перехода от базиса < a1,a2..an > к базису < b1,b2..bn > является матрица, столбцы которой разложение векторов < b1,b2..bn > в базисе… … Википедия

Марковский процесс с конечным или счетным множеством состояний. Теория М. ц. возникла на основе исследований А. А. Маркова, к рый в 1907 положил начало изучению последовательностей зависимых испытаний и связанных с ними сумм случайных величин … Математическая энциклопедия

Канал связи, для к рого возможна передача информации одновременно в нескольких направлениях. Ниже описан К. м. без памяти с дискретным временем и конечными алфавитами на входах и выходах. Пусть заданы s конечных множеств Y1, ..., Ys, где… … Математическая энциклопедия