“${n}$-$1$” paths on lattice graphs. Random walks

I. M. Erusalimskyi ; A. V. Ivantsov

Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Voronezh spring mathematical school “Modern methods of the theory of boundary-value problems. Pontryagin readings – XXX”. Voronezh, May 3-9, 2019. Part 5, Tome 194 (2021), pp. 107-114

Résumé

In this paper, we consider graph-lattices with "$n$-$1$" constraints on attainability whose vertices are located at points of the plane with nonnegative integer coordinates. Two arcs emerge from each vertex: a horizontal arc comes to the nearest right vertex and a vertical arc to the nearest upper vertex. In the case of the "$n$-$1$" attainability, reachable paths are paths that satisfy the additional condition, namely, the multiplicity $n$ of the number of arcs in the maximal segments of paths consisting only of horizontal arcs. This restriction does not apply to the final segment of a path consisting of horizontal arcs. We obtain a formula for the number of "$n$-$1$" paths leading from a vertex to another vertex and also a formula for the number of such paths passing through a given vertex of the graph-lattice. Random walks along "$n$-$1$" paths on graph-lattices are considered. It is shown that such processes can be locally reduced to Markov processs on subgraphs determined by the type of the initial vertex. Also, we obtain formulas for the probabilities of transition from a vertex to another vertex along "$n$-$1$" paths and some combinatorial identities on Pascal's triangle.

Détail

Keywords: directed graph, lattice graph, random walk, transition probability, attainability
Mots-clés : Pascal's triangle.

Bibliographie

[1] Erusalimskii Ya. M., “Sluchainye bluzhdaniya po grafu reshetke i kombinatornye tozhdestva”, Inzh. vestn. Dona., 2:2 (2015), 12

[2] Erusalimskii Ya. M., “2 i 3 puti na grafe i kombinatornye tozhdestva”, Izv. vuzov. Sev.-Kavkaz. region. Estestv. nauki., 1 (193) (2017), 25–30

[3] Erusalimskii Ya. M., Treugolnik Paskalya: kombinatorika i sluchainye bluzhdaniya, Izd-vo YuFU, Rostov-na-Donu–Taganrog, 2017

[4] Erusalimskii Ya. M., “2–3 puti na grafe-reshetke. Sluchainye bluzhdaniya”, Mat. zametki., 104:3 (2018), 396–406 | MR | Zbl

[5] Erusalimskii Ya. M., Vodolazov N. N., “Nestatsionarnyi i sluchainyi potok v seti”, Mat. Vseross. konf. «Voronezhskaya vesennyaya matematicheskaya shkola «Pontryaginskie chteniya-KhKh. Sovremennye metody teorii kraevykh zadach» (3–9 maya 2008 g., Voronezh), VGU, Voronezh, 2009, 56–57

[6] Erusalimskii Ya. M., Petrosyan A. G., “Sluchainye protsessy v setyakh s bipolyarnoi magnitnostyu”, Izv. vuzov. Sev.-Kavkaz. region. Estestv. nauki., 11 (2005), 10–16

[7] Erusalimskii Ya. M., Skorokhodov V. A., “Grafy s ventilnoi dostizhimostyu. Markovskie protsessy i potoki v setyakh”, Izv. vuzov. Sev.-Kavkaz. region. Estestv. nauki., 2 (2003), 3–5

[8] Erusalimskii Ya. M., Skorokhodov V. A., Kuzminova M. V., Petrosyan A. G., Grafy s nestandartnoi dostizhimostyu: zadachi, prilozheniya, YuFU, Rostov-na-Donu, 2009

[9] Zhilyakova L. Yu., “Ergodicheskie tsiklicheskie resursnye seti. I. Kolebaniya i ravnovesnye sostoyaniya pri malykh resursakh”, Upravl. bol. sist., 43 (2013), 34–54

[10] Zhilyakova L. Yu., “Ergodicheskie tsiklicheskie resursnye seti. II. Bolshie resursy”, Upravl/. bol. sist., 45 (2013), 6–29

[11] Zhilyakova L. Yu., Kuznetsov O. P., Teoriya resursnykh setei, INFRA-M, M., 2017

[12] Kristofides N., Teoriya grafov. Algoritmicheskii podkhod, Mir, M., 1978

[13] Malyshev V. A., Sluchainye bluzhdaniya. Uravneniya Vinera—Khopfa. Avtomorfizmy Galua, MGU, M., 1970

[14] Malyshev V. A., “O reshenii uravnenii Vinera—Khopfa v chetverti ploskosti”, Dokl. AN SSSR., 187:6 (1969), 1066–1069

[15] Pasenchuk A. E., “Ob odnoi zadache sluchainogo bluzhdaniya v chetverti ploskosti”, Usp. mat. nauk., 33:6 (1978), 229–230 | MR

[16] Rabinovich V. S., “Akusticheskaya difraktsiya na periodicheskikh grafakh”, Funkts. anal. prilozh., 48:4 (2014), 77–83 | Zbl

[17] Erusalimskiy I. M., “Graph–lattice: random walk and combinatorial identities”, Boletin de la Sociedad Matematica Mexicana, 22:2 (2016), 329–335 | DOI | MR | Zbl

[18] Ford L. R., Fulkerson D. R., Flows in Networks, Princeton Univ. Press, 1962 | MR | Zbl

[19] Kuznetsov Oleg P., Zhilyakova Ludmila Yu., “Nonsymmetric resource networks. The study of limit states”, Management and Production Engineering Review, 2:3, September (2011), 33–39

[20] Rabinovich V., “Diffraction by periodic graphs”, Complex Var. Ellipt. Equations., 59:4 (2013), 578–598 | MR

[21] Rabinovich V., “On Boundary Integral Operators for Diffraction Problems on Graphs with Finitely Many Exits at Infinity”, Russian Journal of Mathematical Physics, 20:4 (2013), 508–522 | DOI | MR | Zbl

[22] Rabinovich V. S., Roch S., “The essential spectrum of Schrödinger operators on lattice”, J. Phys. A: Math. Theor., 39 (2006), 8377–8394 | MR | Zbl

[23] Rabinovich V. S., Roch S., “Essential spectra of difference operators on $Z^n$-periodic graphs”, J. Phys. A: Math. Theor., 40 (2007), 10109–10128 | DOI | MR | Zbl

[24] Rabinovich V., Roch S., “Pseudodifferential operators on periodic graphs”, Integr. Equ. Oper. Theory., 72:2 (2012), 197–217 | DOI | MR | Zbl

[25] Zhilyakova L. Yu., “Dynamic graph models and their properties”, Automat. Remote Control., 76:8, 1417-–1435 | DOI | MR | Zbl