|
Архив публикацийТезисыXXIII-ая конференцияВероятностный выбор неупорядоченных пар элементов из конечного множестваФГУ ФНЦ Научно-исследовательский институт системных исследований РАН, Россия, 117218, Москва, Нахимовский пр-т, 36, к. 1, akrugly@mail.ru 1 стр. (принято к публикации)Рассмотрим задачу о вероятностном выборе неупорядоченной пары элементов из конечного множества. Выбор пары элементов из конечного множества встречается в теории графов. Типичным примером может служить пошаговая динамика конечного графа, когда на каждом шаге с некоторой вероятностью добавляется или удаляется одно ребро. Выбор ребра и есть выбор пары инцидентных ему вершин. Рассмотрим процедуру последовательного выбора пары элементов, при которой вероятности выбора каждой пары элементов заменяются на вероятности выбора первого элемента и условные вероятности выбора второго элемента при уже выбранном первом. В силу неупорядоченности пары результат не зависит от порядка выбора элементов. В этом случае исходная задача эквивалентна задаче об инвариантной мере цепи Маркова, для которой исходное множество элементов является множеством состояний, вероятности выбора первого элемента являются инвариантной мерой, а условные вероятности выбора второго элемента являются условными вероятностями перехода. При этом на условные вероятности перехода оказываются наложены дополнительные условия. Следствием этих условий является следующее свойство. Произведение условных вероятностей перехода для любой циклической последовательности состояний равно произведению условных вероятностей перехода для тех же состояний, но циклически проходимых в обратном порядке. Исследование инвариантной меры являются традиционным вопросом теории цепей Маркова, и результаты, полученные в рамках этих исследований, могут быть переформулированы и применены к рассматриваемой задаче. |
