In this paper, we propose a Markov movement model for mobile terminals in wireless personal communication service networks and study the location registration problem. We formulate the location registration as a Markov decision process and prove that the optimal strategies have threshold structures.To avoid solving the Bellman dynamical programming equations, we propose a single sample path-based algorithm to tune thresholds of the strategies. Since the proposed algorithm uses only one sample path of the system, it can be implemented online.