Renyi's Parking Problem Revisited

• Published in 2014
• Added on 2018-05-21

R\'enyi's parking problem (or $1D$ sequential interval packing problem) dates back to 1958, when R\'enyi studied the following random process: Consider an interval $I$ of length $x$, and sequentially and randomly pack disjoint unit intervals in $I$ until the remaining space prevents placing any new segment. The expected value of the measure of the covered part of $I$ is $M(x)$, so that the ratio $M(x)/x$ is the expected filling density of the random process. Following recent work by Gargano {\it et al.} \cite{GWML(2005)}, we studied the discretized version of the above process by considering the packing of the $1D$ discrete lattice interval $\{1,2,...,n+2k-1\}$ with disjoint blocks of $(k+1)$ integers but, as opposed to the mentioned \cite{GWML(2005)} result, our exclusion process is symmetric, hence more natural. Furthermore, we were able to obtain useful recursion formulas for the expected number of $r$-gaps ($0\le r\le k$) between neighboring blocks. We also provided very fast converging series and extensive computer simulations for these expected numbers, so that the limiting filling density of the long line segment (as $n\to \infty$) is R\'enyi's famous parking constant, $0.7475979203...$.

Links

• http://arxiv.org/abs/1406.1781v2
• http://arxiv.org/pdf/1406.1781v2

Other information

BibTeX entry

@article{RenyisParkingProblemRevisited,
	key = {RenyisParkingProblemRevisited},
	type = {article},
	title = {Renyi's Parking Problem Revisited},
	author = {Matthew P. Clay and Nandor J. Simanyi},
	abstract = {R\'enyi's parking problem (or {\$}1D{\$} sequential interval packing problem) dates
back to 1958, when R\'enyi studied the following random process: Consider an
interval {\$}I{\$} of length {\$}x{\$}, and sequentially and randomly pack disjoint unit
intervals in {\$}I{\$} until the remaining space prevents placing any new segment.
The expected value of the measure of the covered part of {\$}I{\$} is {\$}M(x){\$}, so that
the ratio {\$}M(x)/x{\$} is the expected filling density of the random process.
Following recent work by Gargano {\{}\it et al.{\}} \cite{\{}GWML(2005){\}}, we studied the
discretized version of the above process by considering the packing of the {\$}1D{\$}
discrete lattice interval {\$}\{\{}1,2,...,n+2k-1\{\}}{\$} with disjoint blocks of {\$}(k+1){\$}
integers but, as opposed to the mentioned \cite{\{}GWML(2005){\}} result, our
exclusion process is symmetric, hence more natural. Furthermore, we were able
to obtain useful recursion formulas for the expected number of {\$}r{\$}-gaps ({\$}0\le
r\le k{\$}) between neighboring blocks. We also provided very fast converging
series and extensive computer simulations for these expected numbers, so that
the limiting filling density of the long line segment (as {\$}n\to \infty{\$}) is
R\'enyi's famous parking constant, {\$}0.7475979203...{\$}.},
	comment = {},
	date_added = {2018-05-21},
	date_published = {2014-12-07},
	urls = {http://arxiv.org/abs/1406.1781v2,http://arxiv.org/pdf/1406.1781v2},
	collections = {Easily explained},
	url = {http://arxiv.org/abs/1406.1781v2 http://arxiv.org/pdf/1406.1781v2},
	year = 2014,
	urldate = {2018-05-21},
	archivePrefix = {arXiv},
	eprint = {1406.1781},
	primaryClass = {math.PR}
}