Search Results

Documents authored by Kijima, Shuji

Document
DOI: 10.4230/LIPIcs.AofA.2024.22
The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension

Authors: Shuma Kumamoto, Shuji Kijima, and Tomoyuki Shirai

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
It is celebrated that a simple random walk on ℤ and ℤ² returns to the initial vertex v infinitely many times during infinitely many transitions, which is said recurrent, while it returns to v only finite times on ℤ^d for d ≥ 3, which is said transient. It is also known that a simple random walk on a growing region on ℤ^d can be recurrent depending on growing speed for any fixed d. This paper shows that a simple random walk on {0,1,…,N}ⁿ with an increasing n and a fixed N can be recurrent depending on the increasing speed of n. Precisely, we are concerned with a specific model of a random walk on a growing graph (RWoGG) and show a phase transition between the recurrence and transience of the random walk regarding the growth speed of the graph. For the proof, we develop a pausing coupling argument introducing the notion of weakly less homesick as graph growing (weakly LHaGG).
Cite as

Shuma Kumamoto, Shuji Kijima, and Tomoyuki Shirai. The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kumamoto_et_al:LIPIcs.AofA.2024.22,
  author =	{Kumamoto, Shuma and Kijima, Shuji and Shirai, Tomoyuki},
  title =	{{The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.22},
  URN =		{urn:nbn:de:0030-drops-204577},
  doi =		{10.4230/LIPIcs.AofA.2024.22},
  annote =	{Keywords: Random walk, dynamic graph, recurrence, transience, coupling}
}
Document
DOI: 10.4230/LIPIcs.SAND.2024.17
An Analysis of the Recurrence/Transience of Random Walks on Growing Trees and Hypercubes

Authors: Shuma Kumamoto, Shuji Kijima, and Tomoyuki Shirai

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
It is a celebrated fact that a simple random walk on an infinite k-ary tree for k ≥ 2 returns to the initial vertex at most finitely many times during infinitely many transitions; it is called transient. This work points out the fact that a simple random walk on an infinitely growing k-ary tree can return to the initial vertex infinitely many times, it is called recurrent, depending on the growing speed of the tree. Precisely, this paper is concerned with a simple specific model of a random walk on a growing graph (RWoGG), and shows a phase transition between the recurrence and transience of the random walk regarding the growing speed of the graph. To prove the phase transition, we develop a coupling argument, introducing the notion of less homesick as graph growing (LHaGG). We also show some other examples, including a random walk on {0,1}ⁿ with infinitely growing n, of the phase transition between the recurrence and transience. We remark that some graphs concerned in this paper have infinitely growing degrees.
Cite as

Shuma Kumamoto, Shuji Kijima, and Tomoyuki Shirai. An Analysis of the Recurrence/Transience of Random Walks on Growing Trees and Hypercubes. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kumamoto_et_al:LIPIcs.SAND.2024.17,
  author =	{Kumamoto, Shuma and Kijima, Shuji and Shirai, Tomoyuki},
  title =	{{An Analysis of the Recurrence/Transience of Random Walks on Growing Trees and Hypercubes}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.17},
  URN =		{urn:nbn:de:0030-drops-198955},
  doi =		{10.4230/LIPIcs.SAND.2024.17},
  annote =	{Keywords: Random walk, dynamic graph, recurrent, transient}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.13
Plane Formation by Synchronous Mobile Robots without Chirality

Authors: Yusaku Tomita, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
We consider a distributed system consisting of autonomous mobile computing entities called robots moving in the three-dimensional space (3D-space). The robots are anonymous, oblivious, fully-synchronous and have neither any access to the global coordinate system nor any explicit communication medium. Each robot cooperates with other robots by observing the positions of other robots in its local coordinate system. One of the most fundamental agreement problems in 3D-space is the plane formation problem that requires the robots to land on a common plane, that is not predefined. This problem is not always solvable because of the impossibility of symmetry breaking. While existing results assume that the robots agree on the handedness of their local coordinate systems, we remove the assumption and consider the robots without chirality. The robots without chirality can never break the symmetry consisting of rotation symmetry and reflection symmetry. Such symmetry in 3D-space is fully described by 17 symmetry types each of which forms a group. We extend the notion of symmetricity [Suzuki and Yamashita, SIAM J. Compt. 1999] [Yamauchi et al., PODC 2016] to cover these 17 symmetry groups. Then we give a characterization of initial configurations from which the fully-synchronous robots without chirality can form a plane in terms of symmetricity.
Cite as

Yusaku Tomita, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita. Plane Formation by Synchronous Mobile Robots without Chirality. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{tomita_et_al:LIPIcs.OPODIS.2017.13,
  author =	{Tomita, Yusaku and Yamauchi, Yukiko and Kijima, Shuji and Yamashita, Masafumi},
  title =	{{Plane Formation by Synchronous Mobile Robots without Chirality}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.13},
  URN =		{urn:nbn:de:0030-drops-86337},
  doi =		{10.4230/LIPIcs.OPODIS.2017.13},
  annote =	{Keywords: Autonomous mobile robots, plane formation problem, symmetry breaking, group theory}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact