On the minimal travel time needed to collect n items on a circle

Nelly Litvak, Willem R. van Zwet

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)
10 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)881-902
Number of pages22
JournalAnnals of applied probability
Volume14
Issue number2
DOIs
Publication statusPublished - 2004

Fingerprint

Travel Time
Circle
Limiting
Limiting Distribution
Poisson process
Closed-form
Random variable
Infinity
Tend
Upper bound
Unit
Zero
Travel time
Limiting distribution
Random variables

Keywords

  • METIS-223770
  • EWI-17676
  • Uniform spacings
  • Asymptotics
  • Exponential functionals
  • Exact distributions
  • Carousel systems
  • IR-70339

Cite this

@article{2c78193827054711acfd3e16feb0a0ec,
title = "On the minimal travel time needed to collect n items on a circle",
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.",
keywords = "METIS-223770, EWI-17676, Uniform spacings, Asymptotics, Exponential functionals, Exact distributions, Carousel systems, IR-70339",
author = "Nelly Litvak and {van Zwet}, {Willem R.}",
note = "Open Access",
year = "2004",
doi = "10.1214/105051604000000152",
language = "English",
volume = "14",
pages = "881--902",
journal = "Annals of applied probability",
issn = "1050-5164",
publisher = "Institute of Mathematical Statistics",
number = "2",

}

On the minimal travel time needed to collect n items on a circle. / Litvak, Nelly; van Zwet, Willem R.

In: Annals of applied probability, Vol. 14, No. 2, 2004, p. 881-902.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - On the minimal travel time needed to collect n items on a circle

AU - Litvak, Nelly

AU - van Zwet, Willem R.

N1 - Open Access

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

KW - METIS-223770

KW - EWI-17676

KW - Uniform spacings

KW - Asymptotics

KW - Exponential functionals

KW - Exact distributions

KW - Carousel systems

KW - IR-70339

U2 - 10.1214/105051604000000152

DO - 10.1214/105051604000000152

M3 - Article

VL - 14

SP - 881

EP - 902

JO - Annals of applied probability

JF - Annals of applied probability

SN - 1050-5164

IS - 2

ER -