A property of random walks on a cycle graph

Springer Science and Business Media LLC - Tập 7 - Trang 1-14 - 2015
Yuki Ikeda1, Yasunari Fukai2, Yoshihiro Mizoguchi3
1Graduate School of Mathematics, Kyushu University, Fukuoka, Japan
2Faculty of Mathematics, Kyushu University, Fukuoka, Japan
3Institute of Mathematics for Industry, Kyushu University, Fukuoka, Japan

Tóm tắt

We analyze the Hunter vs. Rabbit game on a graph, which is a model of communication in adhoc mobile networks. Let G be a cycle graph with N nodes. The hunter can move from a vertex to a vertex along an edge. The rabbit can jump from any vertex to any vertex on the graph. We formalize the game using the random walk framework. The strategy of the rabbit is formalized using a one dimensional random walk over . We classify strategies using the order O(k −β−1) of their Fourier transformation. We investigate lower bounds and upper bounds of the probability that the hunter catches the rabbit. We found a constant lower bound if β∈(0,1) which does not depend on the size N of the graph. We show the order is equivalent to O(1/logN) if β=1 and a lower bound is 1/N (β−1)/β if β∈(1,2]. These results help us to choose the parameter β of a rabbit strategy according to the size N of the given graph. We introduce a formalization of strategies using a random walk, theoretical estimation of bounds of a probability that the hunter catches the rabbit, and also show computing simulation results.

Từ khóa


Tài liệu tham khảo

Adler, M., Räcke, H., Sivadasan, N., Sohler, C., Vöcking, B.: Randomized Pursuit-Evasion in Graphs. Combinatorics Probability Comput. 12, 225–244 (2003).

Aleliunas, R., Karp, R.M., Lipton, R.J., Lovász, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: In Proceedings of the 20th IEEE Symposium on Foundations of ComputerScience (FOCS), pp. 218–223 (1979).

Alpern, S.: The search game with mobile hider on the circle. In: Emilio O. Roxin, Pan-Tai Liu, Robert L. Sternberg (eds.)Differential Games and Control Theory, pp. 181–200. Marcel Dekker, New York (1974).

Babichenko, Y., Peres, Y., Peretz, R., Sousi, P., Winkler, P.: Hunter, Cauchy Rabbit, and Optimal Kakeya Sets. preprint, arXiv:1207.6389v1 (2012).

Chatzigannakis, I., Nikoletseas, S., Spirakis, P.: An efficient communication strategy for ad-hoc mobile networks. In: Proc. the 20th ACM Symposium on Principles of Distributed Computing (PODC), pp. 320–322 (2001).

Chatzigiannakis, I., Nikoletseas, S., Paspallis, N., Spirakis, P., Zaroliagis, C.: An experimental study of basic communication protocols in ad-hoc mobile networks. Lecture Notes in Computer Science 2141, pp. 159–171 (2001).

Efrat, A., Guibas, L.J., Har-Peled, S., Lin, D.C., Mitchell, J.S.B., Murali, T.M.: Sweeping Simple Polygons with a Chain of Guards (2000).

Gal, S.: Search games with mobile and immobile hider, SIAM. J. Control Optimization. 17(1), 99–122 (1979).

Guibas, L.J., Latombe, J.-C., LaValle, S.M., Lin, D., Motwani, R.: A visibility-based pursuit-evasion problem. Int. J. Comput. Geometry Appl. (IJCGA). 9(4), 471–493 (1999).

Isaacs, R.: Differential games, A mathematical theory with applications to warfare and pursuit, control and optimization. John Wiley & Sons, Inc, New York-London-Sydney (1965).

Kirousis, L.M., Papadimitriou, C.H.: Searching and pebbling. Theor Comput. Sci. 47, 205–218 (1986).

LaPaugh, A.S.: Recontamination does not help to search a graph. J. ACM. 40(2), 224–245 (1993).

Lawler, G.F: Intersections of Random Walks, Birkhäuser, Boston (1991).

Megiddo, N., Hakimi, S.L., Garey, M.R., Johnson, D.S., Papadimitriou, C.H.: The complexity of searching a graph. J. ACM. 35(1), 18–44 (1988).

Park, S.-M., Lee, J.-H., Chwa, K.-Y.: Visibility-based pursuit-evasion in a polygonal region by a searcher. Lecture Notes in Computer Science 2076, pp. 456–468 (2001).

Parsons, T.D: Pursuit-evasion in a graph. In: Alavi, Y., Lick, D. (eds.)Theory and Applications of Graphs, Lecture Notes in Mathematics 642, pp. 426–441 (1976).

Parsons, T.D.: The search number of a connected graph. In: Proc. the 9th South-eastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 549–554 (1978).

Spitzer, F.: Principles of Random Walk. 2nd ed. Springer-Verlag, New York (1976).

Suzuki, I., Yamasita, M.: Searching for a mobile intruder in a polygonal region, SIAM. J. Comput. 21(5), 863–888 (1992).

Zelikin, M.I.: A certain differential game with incomplete information. Doklady Akademii Nauk SSSR. 202, 998–1000 (1972).

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Tập 7

1-14

Thông tin tác giả