Abstract
Consider n items located randomly on a circle of length 1. The locations of the items are assumed to be independent and uniformly distributed on [0, 1). A picker starts at point 0 and has to collect all n items by moving along the circle at unit speed in either direction. In this paper we study the minimal travel time of the picker. We obtain upper bounds and analyze the exact travel time distribution. Further, we derive closed-form limiting results when n tends to infinity. We determine the behavior of the limiting distribution in a positive neighborhood of zero. The limiting random variable is closely related to exponential functionals associated with a Poisson process. These functionals occur in many areas and have been intensively studied in recent literature.
Received December 2002; revised May 2003.
AMS 2000 subject classifications. Primary 90B05; secondary 62E15, 60F05, 60G51.
Chapter PDF
Similar content being viewed by others
Key words and phrases
REFERENCES
ALI, M. M. and 0BAIDULLAH, M. (1982). Distribution of linear combination of exponential variates. Comm. Statist. Theory Methods 11 1453-1463.
ASKEY, R. (1980). Ramanujan's extensions of the gamma and beta functions. Amer. Math. Monthly 87 346-359.
BARTHOLD!, J. J. III and PLATZMAN, L. K. (1986). Retrieval strategies for a carousel conveyor. liE Transactions 18 166-173.
BERTOIN, J. and YoR, M. (2001). On subordinators, self-similar Markov processes and some factorizations of the exponential variable. Electron. Comm. Probab. 6 95-106.
BERTOIN, J. and YOR, M. (2002a). On the entire moments of self-similar Markov processes and exponential functionals of Levy processes. Ann. Fac. Sci. Toulouse Math. (6) 11 33-45.
BERTOIN, J. and YOR, M. (2002b). The entrance laws of self-similar Markov processes and exponential functionals of Levy processes. Potential Anal. 17 389-400.
BERTOIN, J., BlANE, P. and YOR, M. (2002). Poissonian exponential functionals, q-series, q-integrals, and the moment problem for log-normal distributions. Technical Report PMA-705, Univ. Paris 6, Laboratoire de Probabilites.
CARMONA, P., PETIT, F. and YOR, M. (1997). On the distribution and asymptotic results for exponential functionals of Levy processes. In Exponential Functionals and Principal Values Related to Brownian Motion (M. Yor, ed.) 73-130. Iberoamericana, Madrid.
DAVIS, R. A. and RESNICK, S. I. (1991). Extremes of moving averages of random variables with finite endpoint. Ann. Probab. 19 312-328.
DUMAS, V., GUlLLEMJN, F. and ROBERT, PH. (2002). A Markovian analysis of additive-increase multiplicative-decrease algorithms. Adv. in Appl. Probab. 34 85-111.
FELLER, W. (1970). An Introduction to Probability Theory and Its Applications II. Wiley, London.
GASPER, G. and RAHMAN, M. (1990). Basic Hypergeometric Series. Cambridge Univ. Press.
GUILLEMIN, F., ROBERT, PH. and ZWART, B. (2002). AIMD algorithms and exponential functionals. Technical Report 4447, INRIA.
LITVAK, N. and ADAN, I. (2001). The travel time in carousel systems under the nearest item heuristic. J. Appl. Probab. 38 45-54.
LITVAK, N. and ADAN, I. (2002). On a class of order pick strategies in paternosters. Oper. Res. Lett. 30 377-386.
LITVAK, N. (2001). Some peculiarities of exponential random variables. J. Appl. Probab. 38 787-792.
PYKE, R. (1965). Spacings. J. R. Stat. Soc. Ser. B Stat. Methodol. 27 395-449.
YOR, M. (2001). Exponential Functionals of Brownian Motion and Related Processes. Springer, Berlin.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Litvak, N., van Zwet, W.R. (2012). On The Minimal Travel Time Needed to Collect n Items on a Circle. In: van de Geer, S., Wegkamp, M. (eds) Selected Works of Willem van Zwet. Selected Works in Probability and Statistics. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-1314-1_22
Download citation
DOI: https://doi.org/10.1007/978-1-4614-1314-1_22
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-1313-4
Online ISBN: 978-1-4614-1314-1
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)