Title: On the expected distance of a random walk

Authors: Trevor S. Hale; Faizul Huq; Heather Lutz; Carles Moslares

Addresses: Department of Management, Marketing, and Business Administration, University of Houston – Downtown, Houston, Texas 77002, USA ' Department of Management, Ohio University, Athens, Ohio 45701, USA ' Supply Chain and Information Systems Department, Penn State University, University Park, Pennsylvania 16803, USA ' IQS School of Management, Universitat Ramon Llull, 08017 Barcelona, Spain

Abstract: This paper investigates the Euclidean length of a random walk though n coplanar points. The length of which has multiple applications including spanning trees, Steiner trees, and certain forms of the travelling salesman problem. To estimate this distance, we partition an area A into m equivalent squares and then add the expected Euclidean distances travelled between each of the m squares with the expected Euclidean distances travelled within each of the m squares. The end result is a closed form model for the expected length of a random walk through n coplanar points. Some avenues of future research are also included.

Keywords: expected distance; random walk; Euclidean TSP; travelling salesman problem; Euclidean distances; Euclidean length.

DOI: 10.1504/IJMOR.2015.069135

International Journal of Mathematics in Operational Research, 2015 Vol.7 No.3, pp.241 - 250

Received: 14 Feb 2013
Accepted: 30 Aug 2013
Published online: 30 Apr 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article