Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,087

СЛУЧАЙНЫЕ БЛУЖДАНИЯ ПО ГРАФУ-РЕШЁТКЕ. НЕМАРКОВСКИЙ СЛУЧАЙ

Ерусалимский Я.М. 1
1 ФГАОУ ВО «Южный федеральный университет»
Граф-решетка имеет вершины в точках с неотрицательными целыми координатами. Из каждой вершины выходят две дуги: горизонтальная и вертикальная ‒ в соседние вершины (правую и верхнюю). Вероятность перехода по вертикальной дуге равна p, 0 < p < 1, по горизонтальной дуге – q, 0 < q < 1, p + q = 1. Решены задачи о случайных блужданиях по вершинам графа-решётки, без ограничений на достижимость и с двумя видами ограничений на достижимость – смешанной и магнитной. При наличии ограничений на достижимость процесс случайного блуждания не является Марковским процессом. Получены некоторые комбинаторные тождества, содержащие биномиальные коэффициенты из разных слоёв треугольника Паскаля. Эти тождества можно считать обобщением формулы бинома Ньютона.
ориентированный граф
случайные блуждания
вероятность перехода
достижимость вершин
треугольник Паскаля
комбинаторное тождество
Марковский процесс
1. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. – 9-е изд., перераб. и доп. – М.: Вузовская книга, 2008. – 288 с.
2. Ерусалимский Я.М. Графы с нестандартной достижимостью. Задачи, приложения / Я.М. Ерусалимский, В.А. Скороходов, М.В. Кузьминова, А.Г. Петросян. – Ростов-на-Дону: Южный федеральный университет, 2009. – 195 с.
3. Ерусалимский Я.М. Графы с затуханием на дугах и усилением в вершинах и маршрутизация в информационных сетях // Инженерный вестник Дона. – 2015. – № 1. URL: http://www.ivdon.ru/ru/magazine/archive/n1y2015/2782.
4. Ерусалимcкий Я.М., Скороходов В.А. Общий подход к нестандартной достижимости на ориентированных графах // Известия вузов. Сев.-Кав. регион. Ест. науки, cпец. выпуск «Псевдодифференциальные уравнения и некоторые проблемы математической физики». – 2005. – C. 64–67.
5. Ерусалимский Я.М., Петросян А.Г.Случайные процессы в сетях с биполярной магнитностью // Известия вузов. Сев.-Кав. Регион. Ест. науки. Приложения. – 2005. – № 11. – С. 10–16.
6. Ерусалимский Я.М. Случайные блуждания по графу-решётке и комбинаторные тождества // Инженерный вестник Дона. – 2015. – № 2, ч. 2. – 12 с. – URL: http://www.ivdon.ru/ru/magazine/archive/n2p2y2015/2964.
7. Grady L., Polimeni J. Discrete Calculus: Аpplied analysis on Graphs for Computational Science // Springer Publishing Company, Inc., NY. – 2010. – 366 p.
8. Riordan J. An Introduction to combinatorial analysis. – New York: John Wiley&Sons, Inc., London-Chapman & Hall, Limited, 1958. – 244 p.

Задача о случайных блужданиях по вершинам графа давно считается классической, в теории случайных процессов это стандартный пример, с которого начинают изучение Марковских процессов. Перемещаясь по дугам из вершины в вершину, движущаяся частица совершает на графе путь (основные определения см. в [1]). Если мы налагаем дополнительные требования на множество допустимых путей (вводим ограничения на достижимость), этот процесс становится немарковским. Общая схема решения задачи о случайных блужданиях на конечных ориентированных графах с ограничениями на достижимость изложена в работе [2]. В настоящей работе мы рассматриваем бесконечный граф-решётку и решаем задачу о случайных блужданиях на графах с ограничениями на достижимость двух типов – смешанная достижимость и магнитная достижимость. Регулярность конструкции графа-решётки и регулярность поставленных ограничений на достижимость позволили нам получить результаты, не пользуясь методом разверток (см. [2]).

Пути на графе-решётке

Рассмотрим один бесконечный ориентированный граф, который будем называть граф-решетка. Множество вершин этого графа Z+×Z+ (здесь Z+ – множество неотрицательных целых чисел). Из каждой вершины (k; l) выходят две дуги, одна в вершину (k + 1; l), другая в вершину (k1; l + ) (рисунок). Будем считать, что все дуги имеют единичную длину.

Ясно, что

1. Граф-решетка не содержит контуров.

2. Все пути на этом графе простые.

3. Из вершины x = (k; l) существует путь в вершину y = (s; t) тогда и только тогда, когда (k ≤ s)&(l ≤ t), при этом длины всех путей равны (s – k) + (t – l). Все эти пути находятся на графе-решетке в прямоугольнике с нижней левой вершиной x и правой верхней вершиной y.

pic_6.wmf

Граф-решётка

Пусть 0 ≤ m ≤ n. Рассмотрим задачу о количестве путей из вершины erusalim01.wmf в вершину erusalim02.wmf. Все пути из erusalim03.wmf в erusalim04.wmf имеют длину, равную n и располагаются в соответствующем прямоугольнике. Каждый такой путь будем кодировать n-разрядным двоичным числом, содержащим m единиц и n – m нулей. Единица, стоящая на i-м месте, означает, что на i-м шаге путь проходит по вертикальной дуге, а ноль – означает прохождение по горизонтальной дуге. Таким образом, количество путей, ведущих из вершины erusalim05.wmf в вершину erusalim06.wmf, равно количеству n-разрядных двоичных чисел, содержащих m единиц, а оно равно erusalim07.wmf. Граф-решетка позволяет сделать наглядным доказательство тождества Паскаля, лежащего в основе построения знаменитого треугольника Паскаля (см. напр. [1]). Действительно, рассмотрим вершины erusalim08.wmf и erusalim09.wmf. Количество путей, ведущих из erusalim10.wmf в erusalim11.wmf, равно erusalim12.wmf, разобьем все множество путей на множество путей, заканчивающихся вертикальной дугой, и множество путей, заканчивающихся горизонтальной дугой. В первом из них содержится erusalim13.wmf путей, а во втором – erusalim14.wmf путей. По комбинаторному правилу суммы получаем

erusalim15.wmf

Будем считать, что на дугах заданы вероятности перехода. Вероятность перехода по любой вертикальной дуге будем считать равной p, 0 < p < 1, а по любой горизонтальной дуге равной q, 0 < q < 1, p + q = 1. Тогда вероятность попадания из вершины erusalim16.wmf в вершину erusalim17.wmf по одному из путей равна pm∙qn–m. Вероятность erusalim18.wmf попадания из вершины erusalim19.wmf в вершину erusalim20.wmf за s шагов равна

erusalim21.wmf

Просуммировав последнее по всем вершинам, находящимся на расстоянии n от вершины erusalim22.wmf, получим

erusalim23.wmf

Это соответствует тому, что мы имеем дело с полной группой событий.

Граф-решётка со смешанной достижимостью

Будем теперь рассматривать граф-решётку как граф со смешанной достижимостью (см. [2–4]). Множество дуг U графа со смешанной достижимостью представляет собой объединение непересекающихся непустых множеств UR и UZ, а допустимыми на графе со смешанной достижимостью являются пути, которые не проходят подряд по дугам множества UZ. Будем считать, что на графе-решетке горизонтальные дуги образуют множество UZ, а вертикальные – UR. Допустимыми путями на графе-решётке со смешанной достижимостью являются пути, не содержащие никаких следующих подряд горизонтальных дуг. Другими словами, между любыми двумя соседними горизонтальными дугами пути имеется не менее одной вертикальной дуги. Ясно, что условие существования пути из вершины x = (k; l) в вершину y = (s; t), состоящее в выполнении неравенств (k ≤ s)&(l ≤ t), является теперь только необходимым, но не достаточным.

Пусть 0 ≤ m ≤ n. Рассмотрим задачу о количестве смешанных путей, ведущих из вершины erusalim24.wmf в вершину erusalim25.wmf. Путь будем кодировать n-разрядным двоичным числом, содержащим m нулей и n – m единиц. Учитывая условие смешанной достижимости, в этих числах между любыми соседними нулями должна содержаться хотя бы одна единица. Обозначим через x1 количество единиц, стоящих перед первым нулями (x1 ∈ Z+), через x2 – количество единиц, стоящих между первым и вторым нулём (x2 ∈ N), через x3 – количество единиц, стоящих между вторым и третьим нулями, (x3 ∈ N), ..., через xm – количество единиц, стоящих между предпоследним и последним нулями (xm ∈ N), через xm+1 – количество единиц, стоящих за последним нулем (xm+1 ∈ Z+). Тогда задача о подсчёте количества таких n-разрядных двоичных чисел равносильна задаче нахождения числа решений уравнения

erusalim26.wmf (1)

Следуя [1], сделаем в (1) замену переменных

erusalim27.wmf

Тогда задача свелась к подсчету числа решений уравнения

erusalim28.wmf (2)

Известно ([1]), что количество решений уравнения (2) равно erusalim29.wmf. Ясно, что должно выполняться неравенство m < n – m + 1. Тогда erusalim30.wmf. Это неравенство является необходимым и достаточным условием смешанной достижимости на графе-решётке, а именно:

Утверждение 1. Вершина y = (s; t) смешанно достижима из вершины x = (k; l) на графе-решётке тогда и только тогда, когда выполнены следующие условия

erusalim31.wmf (3)

Множество вершин, смешанно достижимых из вершины erusalim32.wmf – это вершины, находящиеся на прямой y = x – 1 и выше этой прямой.

Что будет с процессом случайного блуждания в случае смешанной достижимости, когда запрещено проходить по двум горизонтальным дугам подряд? Как известно ([2, 5]), в этом случае процесс случайного блуждания не является Марковским процессом. Вершины, находящиеся ниже прямой y = x – 1, станут недостижимыми. Пути перестают быть равновероятными.

Рассмотрим случай, когда количество шагов процесса s = 4. В этом случае достижимыми являются только вершины I = (0; 4), II = (1; 3), III = (2; 2). В вершину I ведёт смешанный путь (1111), erusalim33.wmf. В вершину II ведут смешанные пути (1110), (0111), (1011) и (1101) . Вероятность прохождения по первому из них равна p3∙q, по второму и третьему и четвёртому – p2∙q, значит erusalim34.wmf. В вершину III ведут смешанные пути (1010), (0101) и (0110). Вероятность прохождения по первому из них равна p∙q2, по второму – q2, по третьему – p∙q2, значит, erusalim35.wmf.

Проверим, что сумма вероятностей попадания в эти вершины равна единице. Действительно,

erusalim36.wmf

Граф-решётка с магнитной достижимостью

Рассмотрим задачу о случайных блужданиях по графу-решетке с условием неубывающей магнитности [2]. Что это означает? Допустимыми на графе с магнитной достижимостью являются пути, удовлетворяющие следующему условию: если i-му шагу путь прошел через k дуг из множества магнитных дуг и среди дуг, выходящих из конечной вершины i-й дуги, есть магнитные дуги, то i + 1-я дуга должна быть магнитной. Величина k называется уровнем магнитности. Магнитными дугами на графе решётке будем считать вертикальные дуги, а уровень магнитности k = 3.

Рассмотрим задачу о вероятности попадания из вершины (0;0) в вершины решетки за пять шагов по магнитным путям.

Количество магнитных путей, ведущих в вершину (5;0), равно 1 erusalim37.wmf, а вероятность прохождения по этому пути равна q5, erusalim38.wmf.

Количество магнитных путей, ведущих в вершину (4;1), равно erusalim39.wmf, а вероятность прохождения по каждому из них равна p∙q4, т.е. erusalim40.wmf. Количество магнитных путей, ведущих в вершину (3; 2), равно erusalim41.wmf, а вероятность прохождения по каждому из них равна p3∙q3, erusalim42.wmf Количество магнитных путей, ведущих в вершину (2; 3), равно erusalim43.wmf, а вероятность прохождения по каждому из них равна p3∙q2, erusalim44.wmf. Количество магнитных путей, ведущих в вершину (1;4), равно erusalim45.wmf, а вероятность прохождения по каждому из них равна p3∙q, erusalim46.wmf. Количество магнитных путей, ведущих в вершину (0; 5), равно erusalim47.wmf, а вероятность прохождения по этому пути равна p3, erusalim48.wmf. Вероятности попадания из вершины (0;0) за n шагов при уровне магнитности k = 3 в точки, находящиеся на расстоянии равном n: (n; 0), (n – 1; 1), (n – 2; 2), (n – 3; 3), (n – 4; 4), ..., (2; n – 2), (1; n – 1), (0; n).

таковы:

erusalim49.wmf

Учитывая, что полная вероятность попасть из вершины (0;0) в какую-нибудь из этих вершин равна 1, мы получаем тождество

erusalim50.wmf (4)

если p + q = 1.

В случае отсутствия магнитности (k = 0) это тождество превращается в формулу бинома Ньютона.

Для уровня магнитности 0 < k < n получаем тождество:

erusalim51.wmf (5)

если p + q = 1.

Пусть erusalim52.wmf a, b ∈ Z+ (0 < a < b); erusalim53.wmf, тогда из (5) получаем

erusalim54.wmf

1 ≤ k ≤ n. (6)

Приведём пример «работы» тождества (6). Пусть a = 3; b = 5; b – a = 2; n = 5; k = 2..

erusalim55.wmf

Заключение

Мы рассматривали задачу о случайных блужданиях по графу-решётке из вершины erusalim56.wmf. Случай произвольной «стартовой» точки получается из рассмотренного с помощью соответствующего параллельного переноса начала координат в «стартовую» точку. Случай erusalim57.wmf рассмотрен нами в [6].

Комбинаторное тождество (6) (о комбинаторных тождествах [7, 8]) можно считать обобщением формулы бинома Ньютона.

Рецензенты:

Белявский Г.И., д.т.н., профессор, заведующий кафедрой высшей математики и исследования операций, Южный федеральный университет, г. Ростов-на-Дону;

Наседкин А.В., д.ф.-м.н., профессор, заведующий кафедрой математического моделирования, Южный федеральный университет, г. Ростов-на-Дону.


Библиографическая ссылка

Ерусалимский Я.М. СЛУЧАЙНЫЕ БЛУЖДАНИЯ ПО ГРАФУ-РЕШЁТКЕ. НЕМАРКОВСКИЙ СЛУЧАЙ // Фундаментальные исследования. – 2015. – № 2-27. – С. 6013-6017;
URL: http://www.fundamental-research.ru/ru/article/view?id=38610 (дата обращения: 07.08.2020).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074