Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,087

A RANDOM WALK ON A GRAPH-LATTICE. NOT MARKOV CASE

Erusalimskiy Y.M. 1
1 Federal Autonomous Educational Institution of Higher Education Southern Federal University
Граф-решетка имеет вершины в точках с неотрицательными целыми координатами. Из каждой вершины выходят две дуги: горизонтальная и вертикальная ‒ в соседние вершины (правую и верхнюю). Вероятность перехода по вертикальной дуге равна p, 0 < p < 1, по горизонтальной дуге – q, 0 < q < 1, p + q = 1. Решены задачи о случайных блужданиях по вершинам графа-решётки, без ограничений на достижимость и с двумя видами ограничений на достижимость – смешанной и магнитной. При наличии ограничений на достижимость процесс случайного блуждания не является Марковским процессом. Получены некоторые комбинаторные тождества, содержащие биномиальные коэффициенты из разных слоёв треугольника Паскаля. Эти тождества можно считать обобщением формулы бинома Ньютона.
Graph-lattice has vertices at points with non-negative integer coordinates. From each vertex have two arcs: horizontal and vertical neighboring vertices (right and top). The transition probability for each vertical arc is equal to p, 0 < p < 1, for each vertical arc is equal to q, 0 < q < 1, p + q = 1. Consider the problem of random walks on the vertices of the graph, without limitation on the achievable and with two types of limitations on achievable – mixed and magnetic. We solved the problem of random walks on the vertices on the graph-lattice, without limitation on the achievable and with two types of limitations on achievable – mixed and magnetic. If you have restrictions on the attainability the process of the random walk is not a Markov process. There are some combinatorial identities containing binomial coefficients from different layers of Pascal’s triangle. These identities can be considered a generalization of the binomial.
directed graph
random walks
the probability of transition
achievability of the vertices
Pascal’s triangle
combinatorial identity
Markov process
1. Erusalimskiy I.M. Diskretnaja matematika: teorija, zadachi, prilozhenija [Discrete Mathematics: Theory, Tasks and Applications]. Moskow, Vuzovskaja kniga, 2008. 288 p.
2. Erusalimskiy I.M., Skorohodov V.A., Kuzminova M.V., Petrosjan A.G. Grafy s nestandartnoj dostizhimostju. Zadachi, prilozhenija [Graphs with non-standart reachability. Theory, Applications]. Rostov-na-Donu, Juzhnyj federalnyj universitet, 2009.195 p.
3. Erusalimskij Ja.M. Inženernyj vestnik Dona (Rus), 2015, no. 1. URL: http://www.ivdon.ru/ru/magazine/archive/n1y2015/2782.
4. Erusalimskij Ja.M., Skorohodov V.A. Izvestija vuzov. Sev.-Kav. region. Est. nauki, spec. vypusk «Psevdodifferencialnye uravnenija i nekotorye problemy matematicheskoj fiziki», 2005. pp. 64–67.
5. Erusalimskij Ja.M., Petrosjan A.G. Izvestija vuzov. Sev.-Kav. Region. Est. nauki, prilozhenija, 2005, no. 11. pp. 10–16.
6. Erusalimskij Ja.M. Inženernyj vestnik Dona (Rus), 2015, no. 2, 12 p. 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]) можно считать обобщением формулы бинома Ньютона.

Рецензенты:

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

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