Search Results

Documents authored by Kijima, Shuji

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}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact