Exact Finite-Length Theory of Uniform Car Parking: Spatial Laws, Absorption, and Aggregation

Ganesh P Kumar

cs.ROAug 24, 2026

Exact Finite-Length Theory of Uniform Car Parking: Spatial Laws, Absorption, and Aggregation

Authors: Ganesh P Kumar

Abstract

The uniform car-parking process is the one-dimensional random sequential adsorption of unit cars on a segment of finite length $s$ : cars arrive at uniformly random positions and park wherever they fit, until no gap admits another. This paper develops the exact finite- $s$ theory. The joint density of the parked positions is resolved into jamming cells, on each of which it is a rational function, and evaluated by a subset recursion in $O(2^n n)$ operations; the marginal and gap order statistics are obtained as hyperlogarithms whose weight is fixed by the number of coordinates integrated out; and the absorption count and the aggregate quantities are treated through the integral equation descending from Rényi.

Figures & tables

#	Result	Section	Evidence
1	The joint density of the positions is the temporal-order sum $f_{\mathrm{UCP}}=\sum_{\sigma}\prod_{k}1/\ell_{k}^{\sigma}$ , one rational function on each region	5.1	machine-checked
2	Every free length is affine in the gaps, with coefficients in $\{-1,0,1\}$	5.1	machine-checked
3	The regions are indexed by jamming bitstrings, with a closed-form feasibility criterion and count	5.2	machine-checked
4	On a region the density is a single rational function, with poles only on free-length hyperplanes	5.2	machine-checked
5	The parking arrangement is linearly reducible, so every marginal is a hyperlogarithm of weight at most $n-1$	5.1	machine-checked
6	The gap map carries $f_{\mathrm{UCP}}$ : it is affine with unit Jacobian	5.4	machine-checked

Table 1

Question	Section	Obstacle, and the step that would remove it
Real-rootedness of the count generating polynomial $P_{s}$ , hence log-concavity and unimodality of $p_{n}$	6	Real-rootedness is not preserved by the continuous mixture over the split position, and the splitting family has non-constant degree, so the common-interlacer route is unavailable. The remaining candidate is to establish real-rootedness of the symmetric self-convolution $\int_{0}^{s-1}P_{x}P_{s-1-x}\,\mathrm{d}x$ by a tree-structured aggregation.
The likelihood-ratio order in the segment length	6	The same mixture: the order is preserved by independent sums and not by mixtures. Real-rootedness would give it, so this problem is subsumed by the row above.
Whether the density can be evaluated in polynomial time, and whether the associated counting problems are $\#\mathrm{P}$ -hard	5.2	Open in both directions. A collapse of the subset recursion to intervals would need the free lengths to be interval-determined, and they are not. Settling either direction needs new work: a polynomial algorithm exploiting the geometry of the free lengths, or a gadget reproducing the temporal-order sum from a known hard problem.
The asymptotic two-point gap density inside the present framework	7	Its kernel is an exponential period, outside the algebra of multiple polylogarithms in which the finite-length theory sits. The step is to work in that transcendence class directly, targeting the double-Laplace form of the kernel rather than a polylogarithmic one.

Table 2

Section	Aspect of the attachment chain
order statistics	the density on the hard-core polytope $\mathsf{S}_{n}$ ; jammed $=N{=}n$ conditioning, partial $=$ step- $n$ marginal
absorption time	the absorption level / time $N(s)$ and its law
aggregate / count	the law and moments of $N(s)$ , via the strong-Markov split-convolution (R'enyi IE)
point process / RGG	the absorbed configuration as a point process and random geometric graph
asymptotics	the large- $s$ limit — stabilisation, scoped to saturation (§5)

Table 3

probabilistic object	algebraic object
one arriving car	grafting $B_{+}$ in $H_{\mathrm{CK}}$ , depth $+1$
temporal order $\sigma$ (position against arrival time)	a word in $H_{\sqcup\!\sqcup}$ (ladder tree in $H_{\mathrm{CK}}$ )
temporal-order density $\prod_{k}1/\ell_{k}^{(\sigma)}$	the character $\chi$ on that word (comultiplicative for deconcatenation)
sorting $=$ sum over temporal orders	the shuffle $\sqcup\!\sqcup$ (symmetrize over $S_{n}$ )
order-stat joint density $f_{\mathrm{UCP}}$	$\chi(e_{1}\sqcup\!\sqcup\cdots\sqcup\!\sqcup e_{n})=\sum_{\sigma}\chi(\mathrm{word}_{\sigma})$
marginalize one coordinate	one coaction $\Delta$ , weight $+1$

Table 4

aggregate subsection	continues	tool laid here
representations	the split-convolution dictionary	the Volterra / Dyson–Schwinger dichotomy (§1–2) + Hopf ( 4.3 )
additivity	Rényi’s mean equation	the second-kind Volterra resolvent (§1)
special-cases	the moment cascade	the Dyson–Schwinger / Faà di Bruno structure (§2)
order statistics (integral-equation route)	the rank marginals and the joint density	the Volterra hierarchy + linear reducibility (§1, §4)
boundary	the correlation cascade	correlation densities (§3) + transcendence classes (§4)

Table 5

Fig 1: The joint density across two jamming walls: continuous, not differentiable

Fig 2: cell partition and Schlegel diagram

Fig 3: The UCP joint density at $n=2$ , $s=13/2$ ; dotted lines are the cell walls $\{G_{i}=1\}$

	general $(s,n)$	$s=13/2$ : $\,n=3,4,5,6$	in the literature?
1. # cells	$\lvert\mathcal{B}(n,s)\rvert=\displaystyle\sum_{k=w_{\min}}^{n+1}\binom{n+1}{k}-\mathbf{1}\{s>2n+1\},\ \ w_{\min}=\max\{0,\lceil 2n{+}1{-}s\rceil\}$	$15,\,16,\,7,\,1$	no prior source found (the jamming-cell partition)
2. qualitatively distinct	$\lceil\lvert\mathcal{B}(n,s)\rvert/2\rceil$ (reflection of the segment; the density is rational on every cell, of weight $0$ )	$8,\,8,\,4,\,1$	reflection is classical; the partition is not
3. min terms / cell	$n!$ : every temporal order is feasible at an interior point	$6,\,24,\,120,\,720$	no prior source found
4. max terms / cell	exactly $n!$ reciprocal-products: $f\big\|_{\mathcal{R}_{\mathbf{b}}}=\sum_{\sigma\in\mathfrak{S}_{n}}\prod_{k=1}^{n}1/\ell_{k}^{(\sigma)}$	$6,\,24,\,120,\,720$	prior art (the order-sum form )

Table 9

	attachment words	cells (bitstrings)	collapse	gaps computed	$g$ -pieces / gap	integrals / gap	max / cell·piece
n=3	90	15	$90=3!\cdot 15$	$G_{0},G_{1}$ (→ $G_{2},G_{3}$ refl.)	11	588	24
n=4	384	16	$4!\cdot 16$	$G_{0},G_{1},G_{2}$ (refl.)	5	≈3600	288

Table 10

gap	piece	cells meeting the slice	largest term count
$G_{0}$	$[1,\tfrac{3}{2}]$	5	39,840
$G_{0}$	$[\tfrac{3}{2},2]$	1	149
$G_{1}$	$[0,\tfrac{1}{2}]$	11	50,210
$G_{1}$	$[1,\tfrac{3}{2}]$	5	60,253
$G_{2}$	$[1,\tfrac{3}{2}]$	5	55,324
$G_{2}$	$[\tfrac{3}{2},2]$	1	471

Table 11

Fig 4: Marginals of the joint density at

n=3

s=13/2

: the first position

f_{X_{(1)}}

and the interior gap

f_{G_{1}}

, with the half-integer breakpoints marked

operation	cost	note
analytic class of $f_{g_{()}}$	weight-0 rational	sorting adds no transcendentality; polylogs appear only on marginalization
representation	$(n{+}1)!$ permuted copies of $f_{\mathrm{UCP}}$ (each $n!$ arrival terms)	halved by the $\mathbb{Z}_{2}$ reflection
point evaluation	$O\!\big((n{+}1)!\,2^{n}n\big)$	each $f_{\mathrm{UCP}}$ via Held–Karp subset DP $O(2^{n}n)$ [R8]; the $(n{+}1)!$ is intrinsic to sorting a non-exchangeable vector
support / pieces	ordered jammed simplex, $O(s)$ pieces	Theorem C of 5.2
marginal to $g_{(r)}$	integrate $n$ coords	5.3

Table 13

gap feature	UCP	Tonks (equilibrium)	Poisson (no hard core)	Mat'ern I/II
gap law	size-biased $\prod 1/\ell$ ; non-exchangeable	uniform on simplex; exchangeable	i.i.d. exponential spacings	thinned-Poisson spacings
Theorem D ( $f_{g_{()}}$ )	$(n{+}1)!$ distinct terms	$(n{+}1)!\times$ one term (collapses)	i.i.d. product form	thinned, stationary
boundary vs interior	boundary gaps larger ( $\tfrac{3}{16}$ vs $\tfrac{1}{8}$ at $n{=}2$ )	identical (exchangeable)	identical (stationary)	stationary
max gap	$<1$ w.p. 1 (jamming certificate)	can exceed 1 (equilibrium admits sub-jammed)	unbounded	governed by exclusion $r$
min gap	$\geq 0$ , can be $\approx 0$ (near contact)	$\geq 0$	$\geq 0$	$\geq r$ enforced
gap density shape	log-convex per cell	log-affine (uniform)	log-linear (exponential)	,

Table 14

symbol	meaning
$f_{X}=f_{\mathrm{UCP}}/\Pr[N{=}n]$	the conditional order-statistic density, a probability density
$\mathcal{U}_{n}(s)$	the all-unjammed region , every gap at least $2$ ; the modal set for $s>2n{+}1$

Table 15

Fig 5: UCP joint CDF on the Tonks simplex

Fig 6: Quantile function of X_(1): the inverse is Lambert W

Property	Global operation	Per-cell assembly?	Cost	Verdict
Normalization $\Pr[N{=}n]$	sum of integrals	yes (additive)	per-cell integral	easy
Moments $\mathbb{E}[\prod X_{(i)}^{m_{i}}]$	sum of integrals	yes (additive)	per-cell integral, weight $\leq n$	easy
Marginal density / CDF $F_{X_{(i)}}$	integrate out, then over $g$ -pieces	yes per $g$ -piece	weight- $\leq n$ polylog	moderate
Joint CDF $F(\mathbf{x})$	integrate over cell $\cap$ box	no (box cuts across cells)	cell $\cap$ box pieces, weight $\leq n$	harder
Covariances / association	pair-marginal integrals	yes (additive)	weight- $\leq n{-}1$	moderate
Quantile $q_{\alpha}$	invert the marginal CDF	no (inverse has no per-cell form)	transcendental root-find	hard

Table 18

parent structure	joint order-statistic density	cost
i.i.d.	elementary product form (David–Nagaraja Ch. 2)	$O(n)$
independent non-identical (i.n.i.d.)	a permanent	#P-hard exactly; $O(2^{n}n)$ by Ryser
UCP spatial order statistics	structured $\sum_{\sigma}\prod 1/\ell_{k}^{\sigma}$ (a set-function permanent , above)	$O(2^{n}n)$ subset DP ; closed form on the all-unjammed cell; complexity of the general case open
general dependent parents (David–Nagaraja Ch. 6)	the dependency theorem , no permanent shortcut	intractable; the temporal (arrival) law

Table 19

route	computes	cost
Widom arrival sum (naive)	exact finite- $n$ density	$O(n!)$
Held–Karp / Ryser subset DP	exact finite- $n$ density	$O(2^{n}n)$
all-unjammed cell (closed form)	point evaluation	$O(n)$
Widom kinetic time-integral	$s\to\infty$ density ( $\varphi$ -kernel)	$O(1)$

Table 20

statement	content	Lean
free length is a subset sum	$\ell=(s-n-\lvert T^{c}\rvert)-\sum_{i\in T}G_{i}$ over the jammed set $T$ , additive, with no interaction between gaps	UCP.freeLength_subset_sum
cost of the subset recursion	the memoised recursion performs exactly $\sum_{T\subseteq S}\lvert T\rvert=\lvert S\rvert\,2^{\lvert S\rvert-1}$ operations	UCP.Cost.tableCost_eq
it costs less than the order sum	$C_{\mathrm{dp}}(S)<C_{\mathrm{ord}}(S)=\lvert S\rvert!\,\lvert S\rvert$ whenever $\lvert S\rvert\geq 4$	UCP.Cost.tableCost_lt_naive
knowing all proper subsets suffices	two weights agreeing on every $T\subsetneq S$ give the same value	UCP.heldKarp_congr_of_forall_ssubset
missing one proper subset does not	if some $T\subsetneq S$ is never queried, two weights agree on all queries yet differ in value	UCP.heldKarp_not_determined_of_missing
a partial-history oracle does not help	an oracle giving the density of the first $k$ arrivals supplies the weight only on sets of size $\leq k$ , leaving the rest to be queried	UCP.high_levels_remaining

Table 21

feature	UCP (this work)	Tonks (equilibrium)	Mat'ern I	Mat'ern II
construction	sequential uniform attachment	concurrent Gibbs draw	Poisson $+$ delete any close pair	Poisson $+$ keep earliest of close pair
conditioning	fixed segment $s$ and count $N{=}n$	fixed $s,n$	fixed intensity $\lambda$	fixed intensity $\lambda$
joint density on $\mathsf{T}_{n}$	$\sum_{\sigma}\prod_{k}1/\ell_{k}^{\sigma}$ (size-biased $\prod 1/\ell$ )	uniform $n!/(s{-}n)^{n}$	thinned Poisson (not a fixed- $n$ density)	thinned Poisson
gaps	non-exchangeable , size-biased	exchangeable (i.i.d. given sum)	stationary, dependent	stationary, dependent
order-stat correlation	positive , decays in $\lvert i{-}j\rvert$	positive, exchangeable	short-range	short-range
log-shape of density	log-convex per cell , global fail	log-affine (constant)	, (no fixed- $n$ density)	,

Table 22

$n$	$3$	$4$	$5$	$6$
$p_{n}(s)$	$0.004$	$0.404$	$0.577$	$0.018$

Table 23

Fig 7: The two masses on the band

2<s<3

. They cross at

s=7/3

, where both equal

1/2

, so the maximising block is

\{1,2\}

and the mode is not unique.

route	obstacle
Laplace or Sturm–Liouville reformulation	the transform relocates the mixture rather than removing it
common interlacer	the family has non-constant degree ( 6.0.4 )
Hodge index on the convolution Gram matrix	the Gram matrix is not Lorentzian
Lorentzian polynomials and the Hodge-theoretic route of Adiprasito, Huh and Katz	that machinery delivers log-concavity for the invariants of a matroid or, more generally, for a Lorentzian polynomial. The coefficients $p_{n}(s)$ are not known to be either: no matroid is known whose invariants they are, and deciding whether $P_{s}$ is Lorentzian needs the Hessian signature of its homogenisation, which we cannot check without a closed form for $p_{n}$
determinantal representation $P_{s}\propto\det(A_{s}-zB_{s})$	the integral of a determinant is not a determinant, and the pencils have $x$ -dependent size
Alexandrov–Fenchel or Brunn–Minkowski	the region carrying exactly $n$ cars is a non-convex union of cells whose dimension grows with $n$

Table 25

property	UCP, $P_{s}$	Tonks, $P^{\mathrm{Tonks}}_{s}$
real-rootedness	open ( 6.0.4 )	holds: a unit-interval graph is claw-free, so its independence polynomial is real-rooted (Chudnovsky and Seymour 2007), and the continuum statement follows by a limit
log-concavity	open ( 6.0.4 )	holds, by Newton’s inequalities
unimodality	open ( 6.0.4 )	holds, from log-concavity
mode bound $\nu(s)\leq\lceil m(s)/2\rceil$	proved ( 6.0.3 )	holds, the proof using only the support
plateaux	occur ( 6.0.3 )	occur: $p_{1}=p_{2}$ when $s-1=(s-2)^{2}/2$ , that is at $s=3+\sqrt{3}$

Table 26

symbol	meaning
$m$	Rényi parking constant $=\int_{0}^{\infty}e^{-2\int_{0}^{x}(1-e^{-u})/u\,du}\,dx=0.7475979\dots$
$v$	variance rate, $\operatorname{Var}N(s)\sim v\,s$ , $v\approx 0.03815$ (Dvoretzky–Robbins / Blaisdell–Solomon)
$\xi(x,\mathcal{X})$	a stabilizing score at $x$ for point set $\mathcal{X}$ (Penrose–Yukich); $\xi$ is reserved for scores, and the population $p$ -quantile of §A2′ is written $q_{p}$
$R$	radius of stabilization (here $O(1)$ -tailed: super-exponential decorrelation)
RSA field / configuration	the random set of parked-car positions on $[0,s]$ — a point process (“field” in the geometric-probability sense, not an algebraic field)
MDA	max-domain of attraction; the three classes are named in words (Gumbel, Weibull, Fréchet), the Gumbel law alone carrying the symbol $\Lambda$

Table 27

aspect	partial (subcritical, $\eta<\rho_{c}$ )	jammed (saturated)	established in
gap support	unbounded (large voids)	$[0,1)$ , hard-capped	—
gap / void tail	exponential , rate $\lambda=t$	finite endpoint, contact-divergent	§A5, Lemma V
max-gap EVT	Gumbel	Weibull	§A5, Corollary G′
jamming graph	linear forest, geometric components	single path $P_{n}$ (connected)	8.1
unbounded scores ( $g^{2}$ )	heavy-tailed, CLT can fail	bounded, CLT holds	§A1, Theorem G
bounded-score CLT	rate $\sigma^{2}_{\phi,\text{part}}$	rate $\sigma^{2}_{\phi,\text{jam}}$	§A1, Theorem G

Table 28

result	sparse $\theta\to 0$	partial $\theta\in(0,m),\varphi<1$	saturated $\theta=m,\varphi=1$
A1 bulk CLT	Gaussian (weak dep)	Gaussian, bounded $\phi$ (Thm G); $\alpha$ -stable super-tail	Gaussian, all $\phi$
A2/A2′ quantile CLT	—	$\tau^{2}(p,\eta)=v_{\eta}\,p(1{-}p)/\eta^{2}$ (§A2′)	median $\tau^{2}=v/4m^{2}$
A3 concentration	tighter (more blocks)	sub-Gaussian, bounded ( open — §A3)	sub-Gaussian
A4 Berry–Esseen	—	$O(s^{-1/2+\varepsilon})$ (stabilisation BE, open)	$O(s^{-1/2+\varepsilon})$ proven
A5 max-gap EVT	Gumbel	Gumbel	Weibull ( $\varphi{=}1$ flip)
A7 emp. law	$\approx$ Pyke bridge	$\varphi F_{\rm cap}{+}(1{-}\varphi)F_{\rm void}$	func. CLT (§A7)

Table 29

case	statement	status
$\varphi{=}1$ (saturated)	$(S_{s}-\mathbb{E}S_{s})/\sqrt{\operatorname{Var}}\Rightarrow\mathcal{N}(0,1)$ , $\operatorname{Var}\sim\sigma_{\phi}^{2}s$	proven — Penrose–Yukich stabilisation of the bounded gap score
$\varphi<1$ (partial, $\eta$ )	same CLT, ensemble-specific rate	proven for bounded $\phi$ (Theorem G); unbounded $\phi$ jammed-only (heavy tail from large voids)

Table 30

Fig 8: A1 CLT: example vs non-example

case	statement	status
$\varphi{=}1$ (saturated)	$(\tilde{X}_{\rm med}-\tfrac{s-1}{2})/\sqrt{s}\Rightarrow\mathcal{N}(0,\tau^{2})$ , $\tau^{2}=v/(4m^{2})$	conditional theorem — given (i) the count CLT, (ii) shielding-independence of the half-counts, (iii) a Bahadur–Kiefer remainder; core (linearisation + exact reflection-centring) proven
$\varphi<1$ (partial, $\eta$ ) $+$ all central quantiles	$\hat{X}_{p}$ CLT, $\tau^{2}(p,\eta)=v_{\eta}\,p(1{-}p)/\eta^{2}$	proven (§A2′) — Bahadur 1966/Kiefer 1967 (density-general linearisation) $+$ Penrose 2001 count CLT (any density) $+$ §G5′ half-count independence. No Rényi split needed; median is $p=\tfrac{1}{2}$ . Closes the general case

Table 32

Fig 9: A2 median: central vs extreme rank

case	statement	status
$\varphi{=}1$ (saturated)	$\Pr(\|S_{s}-\mathbb{E}S_{s}\|\geq t)\leq 2\exp(-t^{2}/2c_{\phi}^{2}\lfloor s\rfloor)$ , bounded $\phi$	conditional theorem — Freedman on the split-tree martingale, modulo the bounded-remainder lemma of §A3 (Dvoretzky–Robbins 1964); martingale + Freedman step proven
$\varphi<1$ (partial, $\eta$ )	bounded-score normality carries; explicit constant does not	CLT carries (Theorem G, bounded $\phi$ ); the Azuma constant is jammed (split-tree $=$ Rényi split). A fixed-density tail needs a stabilisation concentration inequality, not yet instantiated

Table 34

Fig 10: concentration vs non-concentration

Fig 11: higher cumulants extensive; standardized cumulants vanish

case	statement	status
$\varphi{=}1$ (saturated)	$\sup_{x}\|\Pr(Z_{s}\leq x)-\Phi_{\mathcal{N}}(x)\|=O(s^{-1/2+\varepsilon})\ \forall\varepsilon>0$	proven, given Bolthausen’s martingale Berry–Esseen (1982), which gives $O(s^{-1/2}\log s)$ ; then $\log s=O(s^{\varepsilon})$ . The rate theorem is cited, not proved here, and no rate theory of this kind is formalised. Sharp $O(s^{-1/2})$ conditional (Grama–Haeusler $L^{\infty}$ -QV)
$\varphi<1$ (partial, $\eta$ )	analogous rate	jammed-as-proved — the split-tree martingale BE is jammed; a fixed-density rate needs the stabilisation Berry–Esseen (Lachièze-Rey–Schulte–Yukich 2019), open for RSA

Table 37

Fig 12: A4 Berry–Esseen: bounded vs unbounded

case	statement	status
$\varphi{=}1$ (saturated)	$N(1-\max_{i}G_{i})\Rightarrow\mathrm{Exp}(c)$ ; $\max_{i}G_{i}$ in the Weibull MDA (endpoint $1$ , shape $1$ ), $c=f_{G}(1^{-})$	conditional theorem — given $c\in(0,\infty)$ , Chen–Stein $\Rightarrow$ Exp $(c)$ ; $c$ derived from the kinetic gap equation ( $c=0.42167$ , §A5(iii)); Picard-branch uniqueness is the residual conjecture
$\varphi<1$ (partial, $\eta$ )	$\max_{i}G_{i}$ in the Gumbel MDA — the EVT class flips	conditional theorem — Corollary G′ (Lemma V exponential void tail, rate $\lambda=t$ ; $+$ Chen–Stein), given the asymptotic independence of near-maximal gaps that the Chen–Stein $b_{2}$ term needs

Table 39

Fig 13: A5 Weibull vs Gumbel

Fig 14: Q–Q plots: jammed max-gap is Weibull (via Exp), partial max-gap is Gumbel

case	statement	status
$\varphi{=}1$ (saturated)	Glivenko–Cantelli to closed-form $F_{G}$ ; functional CLT $\mathbb{G}_{s}=\sqrt{N}(\widehat{F}_{s}-F_{G})\Rightarrow\mathbb{G}$ in $D[0,1)$	proven — fdd (delta-method $+$ stabilisation CLT) $+$ tightness (§A7 proof: two-interval fourth-moment bound via Billingsley Thm 13.5, Rényi split, Penrose 2001 stabilisation, Saulis–Statulevičius cumulants); the residual is a split-tree-internal $\Xi_{4}$ lemma, and the closed form of $\sigma^{2}(x)$ remains open
$\varphi<1$ (partial, $\eta$ )	spacing process $\approx$ classical Pyke bridge at low $\eta$ , departing toward the jammed finite-range kernel as $\eta\uparrow$	kernel computed (not a functional theorem) — density-driven interpolation; the process stays Gaussian, no class flip

Table 42

	i.i.d. uniform spacings (Pyke)	jammed RSA gaps (here)
scale	$\Theta(1/n)$ — rescale by $n$	$\Theta(1)$ — hard-core floor, no rescaling
limit law	$1-e^{-x}$ (exponential, unbounded )	$F_{G}$ on $[0,1)$ , bounded : $F_{G}(1)=1$ exactly ( $G_{i}<1$ at jamming)
density	$e^{-x}$	$f_{G}(g)=\tfrac{2}{m}\!\int_{0}^{\infty}te^{-gt}\Phi\,dt$ (§A5(iii)): $-\ln g$ contact spike, finite $f_{G}(1^{-}){=}c$
dependence	independent-spacing Brownian bridge	finite-range (super-exp decorrelation) — stabilization covariance
max	Gumbel, $\log n$ centering	Weibull , endpoint $1$ (§A5)

Table 43

Theorem	Example (holds)	Non-example (fails)	Hypothesis violated
A1 CLT	$\phi(g)=g^{2}$ (bounded)	$\phi(g)=1/g$ (unbounded)	boundedness ⇒ Lindeberg fails; heavy tail, skew $\not\to 0$
A2 median CLT	central rank $X_{(\lceil N/2\rceil)}$	extreme rank $X_{(1)}$	central/bulk rank ⇒ Bahadur linearization needs positive local density
A3 concentration	bounded $\phi=\mathbf{1}\{g<\tfrac{1}{2}\}$	$\phi=1/g$ (unbounded)	boundedness ⇒ sub-Gaussian tail replaced by heavy tail
A4 Berry–Esseen	bounded $\phi=K$ ( $D_{s}\sqrt{s}{=}O(1)$ )	$\phi=1/g$ (unbounded)	boundedness ⇒ no CLT, so no $O(s^{-1/2})$ rate
A5 Weibull max-gap	jammed-RSA $\max_{i}G_{i}$ (bounded support)	Poisson-process max spacing (unbounded)	bounded support (hard-core) ⇒ Gumbel, not Weibull

Table 44

symbol	meaning
$s$ ; $n$	segment length; number of parked cars ( $=\|V\|$ )
$g_{0},\dots,g_{n}$	the $n{+}1$ gaps, $\sum g_{i}=s-n$ ; internal gaps are $g_{1},\dots,g_{n-1}$
$b_{i}=\mathbf{1}[g_{i}<1]$	jamming bit (gap $i$ is jammed); the 5.1 cell index
$\beta=(b_{1},\dots,b_{n-1})$	internal sub-word $=$ edge-indicator of $\mathcal{J}$
$\mathcal{J}=(V,E)$	jamming graph; $V=\{1,\dots,n\}$ , $(i,i{+}1)\in E\iff b_{i}{=}1$
$M_{e}=\sum_{i=1}^{n-1}b_{i}$	edge count $=$ # jammed internal intervals

Table 45

$n$	reach-depth	$\mathbb{E}M_{e}$	$\mathbb{E}K$	$\Pr[\text{conn}]$	$\Pr[N{=}n]$
1	1.000	0	1.000	— (single vertex)	—
2	1.000	0.40308 ∗	1.596	0.40308 ∗	0.000
3	1.000	1.300	1.700	0.370	0.004
4	0.996	2.676	1.324	0.681	0.409
5	0.589	3.981	1.019	0.981	0.964
6	0.021	5.000	1.000	1.000	1.000

Table 47

$n$	$\Pr[\text{conn}]$	$\Pr[N{=}n]$	conn $/$ sat
2	0.4031	0.000	$\infty$
3	0.370	0.004	$\sim 100\times$
4	0.681	0.409	1.66 $\times$
5	0.981	0.964	1.02 $\times$
6	1.000	1.000	$1\times$ (equality)

Table 48

$n$	$\Pr[\deg{=}0]$	$\Pr[\deg{=}1]$	$\Pr[\deg{=}2]$	$\bar{d}=2\mathbb{E}M_{e}/n$
2	0.596	0.404	0	0.404
3	0.257	0.620	0.123	0.867
4	0.054	0.555	0.392	1.338
5	0.002	0.405	0.594	1.592
6	0	0.333	0.667	1.667

Table 49

Fig 17: jamming-graph spectrum delta-comb

Fig 18: saturated adjacent-gap correlation

aggregate quantity	Hopf object	integral equation	§, status
additive $\sum_{i}h(G_{i})$	primitive element	linear Volterra (2nd kind, unit delay)	§2, proved
count PGF $\mathbb{E}[z^{N}]$	group-like element	quadratic Volterra (Dyson–Schwinger)	§3, proved
max-gap CDF $\Pr[\max_{i}G_{i}\leq x]$	group-like element	quadratic Volterra	§3, proved
factorial moments $M_{k}=\partial_{z}^{k}\mathbb{E}[z^{N}]\|_{1}$	Faà-di-Bruno coordinates	finite linear cascade	§3, proved
single order statistic $X_{(k)}$	marginalised character	triangular linear Volterra hierarchy	§4, proved
finite $k$ -variable joint density	graded component of the character	hyperlogarithm (linear reducibility)	§4, proved

Table 54

Fig 20: per-count modes

Fig 21: order-statistic marginals

Fig 22: order-statistic monotonicity in the count

Fig 23: max-gap distribution

$T$	$c$	$h(g)$	$\mathbb{E}[T]$ (tangent)	$\mathbb{E}[T]$ (simulated)	$\operatorname{Var}T$ (tangent)	$\operatorname{Var}T$ (simulated)
count $N$	$1$	$0$	$3.4889$	$3.4952\pm 0.0079$	$0.2497$	$0.2501\pm 0.0056$
$\sum_{i}G_{i}^{2}$	$0$	$g^{2}$	$0.8644$	$0.8588\pm 0.0078$	$0.2407$	$0.2422\pm 0.0054$
$\sum_{i}\sqrt{G_{i}}$	$0$	$\sqrt{g}$	$2.3214$	$2.3190\pm 0.0061$	$0.1485$	$0.1450\pm 0.0032$
$N+\sum_{i}G_{i}^{2}$	$1$	$g^{2}$	$4.3533$	$4.3540\pm 0.0025$	$0.0233$	$0.0227\pm 0.0005$

Table 59

Fig 26: connected k-gap correlation ladder

interval	$\mathbb{E}[N]$	$\mathbb{E}[N^{2}]$	$\mathbb{E}[N^{3}]$	weight
$[1,2)$	$1$	$1$	$1$	0
$[2,3)$	$\dfrac{3s-5}{s-1}$	$\dfrac{7s-13}{s-1}$	$\dfrac{15s-29}{s-1}$	0
$[3,4)$	weight-1 (log)	weight-1 (log)	weight-1 (log)	1
$[4,5)$	weight-2 (dilog)	weight-2 (dilog)	weight-2 (dilog)	2

Table 63

Fig 27: M1 and variance-rate convergence to their asymptotic constants

$s$	$M_{1}$ (DSE march)	$\mathbb{E}[N]$ (order-statistic MC, $\pm 1$ s.e.)
$2.5$	$1.6680$	$1.6668\pm 0.0014$
$3.5$	$2.3527$	$2.3513\pm 0.0014$
$4.5$	$3.1136$	$3.1107\pm 0.0012$
$5.5$	$3.8616$	$3.8585\pm 0.0014$

Table 65

$n$	$p_{n}(s)$ (DSE)	histogram (process MC, $\pm 1$ s.e.)
$2$	$0.6473$	$0.6489\pm 0.0011$
$3$	$0.3527$	$0.3511\pm 0.0011$

Table 66

$s$	$M(s,2)$	$M(s,4)$	$M(s,8)$	Rényi $M(s)$	residual at $t=8$
$2$	$0.8647$	$0.9817$	$0.9997$	$1.0020$	$0.0023$
$3$	$1.4513$	$1.7176$	$1.8661$	$2.0010$	$0.1349$
$4$	$2.0386$	$2.3632$	$2.5473$	$2.7441$	$0.1967$
$5$	$2.6340$	$3.0345$	$3.2553$	$3.4870$	$0.2317$

Table 67

Fig 28: mean and variance against their asymptotics

Fig 29: the standardised third cumulant

Fig 30: Dependency graph of the machine-checked results. Roots (shaded) are the process measure and the free-length affineness; dashed clusters are conditional on the hypotheses listed below.

result cluster	discharged (proved from $M0$ / $F1$ )	assumed (explicit hypothesis)	why assumed
process measure	$M0$ , PM-norm , total mass one, arrival kernel, first-arrival disintegration	—	—
order-statistic density	positional density, $n!$ -symmetrisation, $F1$ , reducibility	—	—
log-convexity	per-cell and $n=2$ on the density itself; exact global-failure counterexample	—	—
complexity	unjammed closed form, jammed subset-sum reduction, counting identity, the Held–Karp subset-recursion identity, refutation of the $O(n^{3})$ /FP claim	—	—
jamming graph	linear-forest structure, $\Delta\leq 2$ , $\omega\leq 2$ , $\chi\leq 2$ , independence / matching / domination, deletion law	—	—
weight ladder	the parking arrangement is reducible; the weight algebra	Aomoto–Goncharov period theorem, and a marginal-equals-integral identification	the period theorem is deep analysis absent from Mathlib; the marginal identification is separate work

Table 71

Learning Optimal Search Strategies
Mar 2, 2026Stefan Ankirchner, Maximilian Philipp ThielOptimal Stopping Minimax Regret
Institute for Mathematics, University of Jena, Inselplatz 5, 07743 Jena, Germany.
High-Density Automated Valet Parking with Relocation-Free Sequential Operations
Mar 25, 2026Bon Choe, Minhee Kang, Heejin AhnAutonomous Parking Sequential Decision Making
School of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Republic of Korea
Limit Theorems and Optimal Policies for Flock Flight through Poisson Forests
Oct 29, 2026Lav R. VarshneyTraffic Flow Theory Combinatorial Optimization
AI Innovation Institute and the Department of Electrical and Computer Engineering, Stony Brook University, Stony Brook, NY, USA.

Mar 2, 2026J/K move · Enter open · S save

Learning Optimal Search Strategies

Stefan Ankirchner, Maximilian Philipp Thiel

Institute for Mathematics, University of Jena, Inselplatz 5, 07743 Jena, Germany.

Optimal Stopping Minimax Regret

Open paper AskPDF arXiv

We explore the question of how to learn an optimal search strategy within the example of a parking problem where parking opportunities arrive according to an unknown inhomogeneous Poisson process. The optimal policy is a threshold-type stopping rule characterized by an indifference position. We propose an algorithm that learns this threshold by estimating the integrated jump intensity rather than the intensity function itself. We show that our algorithm achieves a logarithmic regret growth, uniformly over a broad class of environments. Moreover, we prove a logarithmic minimax regret lower bound, establishing the growth optimality of the proposed approach.

Abstract

Explore similar work

Learning Optimal Search Strategies

High-Density Automated Valet Parking with Relocation-Free Sequential Operations

Limit Theorems and Optimal Policies for Flock Flight through Poisson Forests