PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ganesh P Kumar

arXiv:2608.22671v1cs.ROcs.DScs.SCmath.PRmath.RA

TL;DR

Exact finite-boundary results in uniform car parking have remained elusive because temporal dependence, piecewise configuration cells, and coupled Volterra equations complicate the theory. This paper resolves these structures using subset recursions, cell enumeration, hyperlogarithmic order statistics, and integral-equation analysis, while reporting a flat Berry–Esseen discrepancy measure across the tested range.

  • Problem

    Exact finite-boundary car-parking theory is limited by permutation-dependent densities, combinatorial configuration cells, and integral equations coupled across sub-interval lengths.

  • Method

    The paper organizes the joint density through jamming-cell support enumeration and subset recursion, derives order-statistic expressions, and analyzes aggregate quantities with Rényi-style integral equations.

  • Results

    The n! density sum is evaluated in O(2^n n) operations, while the gap-functional CLT’s Ds remains flat as √s grows from 3.5 to 13.3.

  • Takeaways & Limitations

    The paper supplies an exact finite-s framework spanning joint positions, order statistics, absorption counts, and aggregate functionals.

  • Takeaways & Limitations

    The exact finite-s results do not address whether they survive or degrade under probabilistic hard-core constraints caused by sensing and actuation uncertainty.

Abstract

from arXiv · show

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.

1. Introduction.

The paper develops an exact finite-(s,n) theory of uniform car parking, resolving the joint spatial law into rational jamming cells and extending analysis to marginals, absorption, aggregates, and asymptotics. Its central computational advance is a subset recursion that replaces the n! temporal-order sum with O(2^n n) evaluation, while remaining questions concern polynomial-time collapse and broader regimes.

  • Scope and central object: The finite-(s,n) joint density is the paper’s central exact result, expressed over the hard-core configuration space and organized by temporal orders and jamming cells.The density is a sum over arrival orders, with one rational function on each feasible region.
  • Cell structure: Jamming bitstrings index feasible cells, while free lengths are affine in the gaps with coefficients in {−1,0,1}.On each cell, the density is a single rational function with poles only on free-length hyperplanes.
  • Marginals and transcendental structure: Marginals and gap order statistics are hyperlogarithms of weight at most n−1 because the parking arrangement is linearly reducible.The weight equals the number of coordinates integrated out; no algebraic or elliptic letters arise under the stated reducibility condition.
  • Joint-density computation: O(2^n n) subset recursion evaluates the temporal-order density instead of enumerating n! permutations.Grouping temporal orders by their last-placed car works because free lengths depend on the placed subset, not only on an interval.
  • Open problems: Open frontiers include polynomial evaluation, sub-exponential symbolic compression, hyperuniformity and graph limits, and integral-equation coverage across regimes.The paper explicitly separates established finite results from unresolved extensions and asymptotic classifications.
  • Absorption and aggregates: The absorption count and aggregate functionals admit exact structural results, including stochastic monotonicity, bounded mode counts, finite integral equations, and closed-form point-process descriptors.The aggregate equations are linear Volterra for additive functionals and quadratic for the count; several asymptotic questions remain open.

4. Preliminaries.

The UCP is developed as an absorbing attachment chain whose gap-wise regeneration supports aggregate equations, while finite-length densities require separate combinatorial and analytic machinery. The section establishes ensemble relations, cellwise rational densities, hyperlogarithmic weight control, and a bridge between analytic and combinatorial structures.

  • The attachment chain: The UCP attachment chain places cars uniformly on the current free region, with irreversible placements continuing until an absorbing jammed configuration.A jam occurs when no admissible left endpoint remains; the process reaches one after finitely many steps almost surely.
  • Sub-interval factorisation: Conditioned on a configuration, each gap of length at least one evolves as an independent UCP on its own sub-interval.This strong Markov factorisation supports additive count calculations and first-step integral equations.
  • Limits of factorisation: A first-placement split yields the Rényi integral equation for absorption counts and moments, but not the fixed-n joint order-statistic density.The density instead requires peeling the last car because reciprocal free-length weights do not factor across a split.
  • The partial and jammed ensembles: For s < n + 1, the partial and jammed ensembles coincide, and the jammed n-configuration mass equals Pr[N(s) = n].Every proper subconfiguration of a jammed n-configuration has a gap admitting another car, establishing the event equivalence.
  • Integral and algebraic machinery: Parking integrals are analysed with Hopf-algebraic tools: integrations raise hyperlogarithmic weight, while a bridge identifies the analytic and combinatorial recursions.The bridge connects the parking Volterra recursion and Chen iterated-integral series to the FQSym coproduct.

1. What a car does, algebraically.

The paper separates the joint density from cheaper aggregate recursions: its density is piecewise rational and requires subset dynamic programming, while marginal integration yields a weight-graded hyperlogarithmic structure. The finite theory resolves cells, formulas, and computation, while several complexity and higher-weight questions remain open.

  • Algebraic structure: The joint density does not factor through the sub-segment coproduct because reciprocal free lengths couple both sides of a split.The obstruction is 1/(ℓleft +ℓright), which does not factor into independent side contributions.
  • Algebraic structure: Marginalization raises transcendental weight through the coproduct, linking joint density at weight 0 to the fully marginalized mean at weight k−2.Integration acts as a coalgebra map, producing the rational → log → dilog hierarchy.
  • Dynamic programming: O(2^n n) operations evaluate the n! temporal-order sum by grouping orders according to the last-placed car.The recursion evaluates the density at a point and can be applied per cell.
  • Cell geometry: Jamming bitstrings partition the gap simplex along hyperplanes {G_i = 1}, making the density a single rational function on each cell.The fully unjammed cell is uniform, whereas cells with jammed gaps generally carry non-constant rational densities.
  • Marginals: Single-gap marginals have O(s) pieces with half-integer breakpoints, while n-coordinate integrations produce hyperlogarithms of weight at most n−1.For n = 3 the weight is at most 2; for n = 4 it is at most 3.
  • Scope and open problems: The paper’s exact contribution is the finite-(s,n) joint resolution, cell count, and partition, while polynomial-time evaluation, #P-hardness, and general higher-weight reductions remain open.The order-sum form itself is attributed to earlier adsorption literature.

1. Non-exchangeability (the gap law).

The gap vector is reflection-symmetric but not exchangeable: distinct interior gaps remain distributionally different. This non-exchangeability is a defining feature of the ordered UCP configuration.

  • Symmetry: The gap vector has exactly Z2 symmetry under segment reflection, mapping g_i to g_{n−i}.No broader permutation symmetry is asserted.
  • Non-exchangeability: Distinct-depth interior gaps can have different distributions, so the order statistics form a dependent, non-identically-distributed family.Spatial ordering does not make the gaps exchangeable.

2. Joint order-statistic density (the David–Nagaraja derivation).

The finite-s joint law is a rational density on jamming cells, whose gap representation exposes dependence, reflection symmetry, and order-statistic structure. David–Nagaraja symmetrization then yields exact gap-order marginals and moments, with logarithmic or polylogarithmic complexity after integration.

  • Joint density: The joint density is rational on each jamming region, with regions indexed by jamming bitstrings and free lengths affine in the gaps.The gaps and ordered positions share the same density under a unit-Jacobian affine transformation.
  • Gap structure: The gap vector is dependent and non-exchangeable: boundary gaps differ from interior gaps, while reflection is the exact Z2 symmetry.At n=2, each boundary gap has mean 3/16 and the interior gap has mean 1/8.
  • Gap order statistics: The sorted-gap density requires full symmetrization over (n+1)! permutations, reduced only pairwise by reflection to ⌈(n+1)!/2⌉ generically distinct terms.Non-exchangeability prevents the collapse or factorization available for exchangeable or i.i.d. spacings.
  • Marginals and moments: Marginalizing coordinates produces piecewise multiple polylogarithms of weight at most n−1, while sorting adds no transcendental weight.For n=2, the marginal is rational plus rational multiples of logarithms, with breakpoints where sort-cell geometry changes.
  • Dependence: All order-statistic pairs are positively correlated, strictly so for distinct indices in the verified finite cases, despite failure of negative association for the gaps.The dependence is long-range but decaying, with correlations approximately 0.74, 0.46, and 0.33 at separations 1, 2, and 3.

1. The moments are integrals of the density, so they are strictly harder to compute.

The density is the primitive weight-0 rational object, whereas moments are obtained by integrating it and therefore belong to a higher-weight polylogarithmic class. Reconstructing the density from moments reverses this computational advantage.

  • Computational hierarchy: The density is a weight-0 rational function assembled by O(2^n n) subset dynamic programming, while each moment is a weight-≤n multiple polylogarithm.The moments are higher-weight integrals of the density rather than a simpler representation of it.
  • Computational hierarchy: Recovering the density from moments requires many higher-weight integrals followed by inversion to obtain the lower-weight primitive.Direct density evaluation avoids constructing the primitive from its harder integrals.

2. The density is not globally analytic, so no single Taylor/moment series represents it.

The finite-s density is piecewise rather than globally analytic: cell boundaries and poles make direct rational assembly the exact object, while moments and CDFs become polylogarithmic integrals. Quantiles and modes therefore require inversion or regime-specific optimization rather than one universal series.

  • The exact finite-(s,n) density is piecewise-rational with poles and hard boundaries, so moment expansions describe limits rather than the density itself.Direct assembly is exact and easier for the finite problem.
  • Every mixed moment is a multiple polylogarithm of weight at most n, with letters s−j, because moments integrate the cellwise density.
  • On cell∩box pieces, the joint CDF is a hyperlogarithm of weight ≤n; for n = 3, exact evaluation uses dilogarithms and at most trilogarithms.The n = 3 computation gives an exact symbolic slice and a numerical value F = 0.1559 matching Monte Carlo.
  • The joint CDF contours bend at x2 = x1+1, exposing dependence that a product-of-marginals CDF would not reproduce.
  • For n = 2, the marginal quantile is expressed through Lambert W; for n ≥3, it is the root of a polylogarithmic equation without a named inverse.
  • The mode changes across s > 2n + 1, 2n −1 < s ≤2n + 1, and s ≤2n −1: explicit spacious-region maximization, bounded vertex scanning, and no finite mode, respectively.In the crowded regime the density is unbounded and approaches a pole at a boundary vertex.

6. The absorption time Nabs(s).

The absorption count is characterized through Rényi’s splitting law as a mixture of independent child-process counts. This yields exact support information, stochastic monotonicity in segment length, and a finite-mode bound, while real-rootedness, log-concavity, and unimodality remain open.

  • The absorption pmf is pn(s) := Pr[Nabs(s) = n], and its support is determined explicitly by the segment length.For noninteger s > 1 the support is {nmin,...,nmax}; at integer s, nmax has zero mass.
  • Rényi’s splitting law represents Nabs(s) as a mixture over the split point of independent child-process counts.
  • The resulting moment equations form a triangular system of second-kind linear Volterra equations sharing one kernel.F1 = 1 recovers Rényi’s equation.
  • Nabs(s) is stochastically non-decreasing in s.The proof combines monotonicity of child lengths, induction, and closure of stochastic order under independent sums and mixtures.
  • The pmf can have a plateau: for 2 < s < 3, the two masses agree at s = 7/3, so counts 1 and 2 are jointly modal.
  • Real-rootedness, log-concavity, and unimodality are conjectured, but the continuous mixture in the splitting law does not preserve real-rootedness through a common interlacer.The family of products has no common interlacer for noninteger s > 2.

7. Asymptotic Properties of the Order Statistics.

The paper establishes limit theorems for spatial functionals of the jammed configuration, extending asymptotic analysis beyond the jamming count. These results cover bulk gaps, medians, extremes, concentration, and empirical gap measures.

  • The paper proves a central limit theorem for bulk-gap sums and a density-general extension.
  • It gives sub-Gaussian concentration for spatial functionals and a Gaussian fluctuation law for the median position.The median result includes the symmetric-median law.
  • The largest gap obeys a Weibull law with an explicit constant.
  • A functional limit theorem is established for the empirical gap measure.

1. Central order statistics — limit laws.

The paper fills several asymptotic gaps for spatial order-statistic and gap functionals of one-dimensional car parking. It combines rank-functional, concentration, and Stein/Malliavin approaches to obtain central-limit laws and an explicit convergence rate.

  • Prior work provided count limit theorems but not central-limit or concentration results for spatial order-statistic and gap functionals.
  • The median is treated as a rank functional through a Bahadur representation, while the bulk-gap sum is reached through stabilization.
  • The split-tree martingale instantiates bounded-difference and Stein–Chatterjee concentration for RSA order-statistic and gap functionals.
  • A bulk-gap functional receives a Kolmogorov bound of order s−1/2+ε for every ε > 0, with the leading constant identified for continuous scores.

4. Extreme value theory — extremal order statistics.

The paper distinguishes extremal behavior across jammed and partial ensembles: bounded jammed gaps produce Weibull maxima, while unbounded partial gaps produce Gumbel maxima. Central order statistics admit Gaussian limits, but extreme ranks do not, and several rates or extensions remain conditional or open.

  • Extreme-value class: At φ = 1, every gap is capped below 1 and the largest gap has a Weibull extreme-value law; for φ < 1, uncapped voids produce Gumbel behavior.The phase boundary also changes the boundedness conditions relevant to gap-score limit theorems.
  • Bulk-gap functionals: The bulk-gap CLT applies to bounded scores at every density through stabilization, while unbounded scores are restricted to the jammed ensemble because partial gaps have heavy tails.The theorem gives an ensemble-specific linear variance rate for the summed score.
  • Order statistics: Central ranks Gaussianize through Bahadur linearisation and count fluctuations, whereas the extreme rank X(1) converges to a boundary-gap law rather than a normal limit.The argument requires positive local car density, which extreme order statistics lack.
  • Scope and limitations: The central-quantile CLT extends to every p ∈ (0,1) and every density, but rank and extremal functionals remain outside the local-score stabilization argument.The density-general extension avoids the Rényi split and uses the count CLT, Bahadur–Kiefer linearisation, and stabilization.

8. The jamming graph.

The jamming graph is exactly a linear forest determined by the internal jamming-bit string β, reducing its nontrivial descriptors to β-functionals and UCP marginal calculations. This reduction separates graph connectivity from full process saturation and yields exact structural identities alongside finite-s,n descriptor laws.

  • Graph invariants: Clique, chromatic, girth, cycle, connectivity, and Hamiltonicity descriptors are fixed or nearly trivial under the linear-forest form; only edge and run-structure statistics remain nontrivial.Proposition 8.2 gives the corresponding deterministic values and thresholds.
  • Connectivity versus saturation: Pr[J connected] ≥ Pr[N = n], with strict inequality for s > n + 1, so graph-connectedness can precede process-jamming.Connectivity requires jammed internal gaps, whereas saturation additionally requires both end gaps to be shorter than one.
  • Linear-forest reduction: Theorem 8.1 identifies the jamming graph as a subgraph of the path P_n, so it is a disjoint union of paths indexed by maximal runs of jammed internal gaps.Every graph invariant is thereby a functional of β, while point-process descriptors are marginals of f_UCP.
  • Linear-forest reduction: χtop = K = n − M_e, and the maximum degree satisfies Δ(J) ≤ 2 with vertex degrees determined by adjacent jamming bits.Components correspond to maximal runs of 1s in β and flanked singleton vertices.
  • Exact descriptor laws: Every count and length descriptor reduces to explicit integrals of UCP bit-block marginals over jamming-cell polytopes, where f_UCP is piecewise weight-0 rational.The resulting general-(n,s) closed forms are obtained from the finite-cell representation.
  • Finite-size behavior: At s = 6.5, E[Lmax] rises from 1.404 at n = 2 to 6.000 at n = 6, where saturation makes J = P6 exactly.The longest jammed run reaches the full path at the saturation endpoint.

9. Markov chain and aggregates.

The paper organizes finite-length aggregates around regeneration after the first car, yielding linear, quadratic, or augmented triangular integral equations. It also derives exact spatial laws, hyperlogarithmic marginals, and finite-length hierarchy limits.

  • Rigidity of the attachment kernel: Length-only process laws characterize exponential attachment densities, while a constant kernel occurs exactly for the uniform process.The mean alone cannot distinguish affine and uniform densities, but the attachment kernel can.
  • Regeneration and representability: Finite integral equations arise from split-compatibility: additive aggregates are linear Volterra, multiplicative aggregates are quadratic, and marked aggregates restore regeneration through coefficient extraction.The mark carries the split allocation as a convolution, producing triangular fixed-index hierarchies.
  • Aggregate equations: The additive mean recovers Rényi’s mean equation, while the count generating function and max-gap distribution instantiate quadratic equations.The order-statistic forcing is obtained by extracting a coefficient from the count-marked equation.
  • Order-statistic hierarchy: For s ∈[ℓ,ℓ+1), order-statistic marginals form a rank-triangular hierarchy and are piecewise hyperlogarithms of weight at most ℓ−1.The hierarchy is solved rank by rank from the count probability mass function and lower-rank marginals.
  • Boundary of the finite-length theory: The finite-segment split closes these hierarchies, unlike the thermodynamic-limit spatial gap sequence, whose nonzero three-gap cumulant prevents truncation.The exact finite-s theory therefore relies on a distinguished first car and bounded-segment regeneration.
  • Joint spatial laws: The full fixed-count order-statistic density is piecewise rational on jamming cells, while selected multivariable marginals remain hyperlogarithmic without square roots or elliptic curves.The rational cell representation is the input for aggregate density calculations.

10. Implementation details.

The implementation combines symbolic exact computation with machine-checked structural verification. Its exact symbolic reach is concentrated on the all-jammed facet, while several analytic and probabilistic components remain explicit hypotheses or conditional results.

  • Symbolic computation: Symbolic computation enumerates jamming cells, evaluates rational densities and polytope volumes, and integrates cell contributions with a dedicated hyperlogarithm integrator.Independent recursion evaluation and archived plain-text forms support re-evaluation of the resulting expressions.
  • Machine-checked verification: The machine-checked dependency graph is rooted in the process measure M0 and free-length affineness F1, with dashed clusters conditional on stated hypotheses.The formal development distinguishes discharged results from assumed or conditional components.
  • Symbolic computation: 719 of 720 gap-sign cells for Pr[N = 6] on (6,7) reduce to closed polylogarithmic form, with one cell evaluated numerically.Exact forms agree with direct Monte Carlo within Monte-Carlo error.
  • Scope and assumptions: The development carries the sequential-uniform process measure and polylogarithmic weight theory as explicit hypotheses rather than constructing the analytic results from scratch.The Aomoto–Goncharov period theorem and marginal-identification step are also separate assumptions.
  • Machine-checked verification: The formalized layer covers process-measure foundations, order-statistic symmetrisation, free-length structure, jamming-count bounds, subset recursion, and related graph identities.The implementation records both exact combinatorial results and the complexity claim associated with the subset recursion.
  • Scope and assumptions: The real-variable Dyson–Schwinger equation is the sole genuine axiom, and its hypothesis is machine-shown non-vacuous at a base coordinate.The signed-argument derivation does not extend from the nonnegative-valued conditional result.

11. Retrospect and future work.

The retrospective identifies the exact finite-(s,n) joint order-statistic density as a long-neglected question and frames future work around the obstacles preventing its broader development.

  • Retrospect and future work: The exact finite-(s,n) joint order-statistic density was essentially absent from roughly seventy years of car-parking and RSA work.The paper interprets this silence as evidence that the question was not historically posed, rather than as a problem known to resist solution.

1. The founding questions were asymptotic by construction.

Rényi’s founding treatment targeted an asymptotic thermodynamic quantity, making finite-segment behavior a boundary transient rather than the primary object of study.

  • Founding questions: Rényi introduced parking to extract the jamming constant M1 ≈0.7476, treating finite-s behavior as a boundary transient to integrate away.This framing prioritized a single thermodynamic number over exact finite-length structure.

2. The stat-mech lineage measured other things.

Classical irreversible-deposition studies measured coverage, kinetics, correlations, and asymptotic count statistics, but did not obtain the exact finite-length joint order-statistic law or finite-L moment functions.

  • Coverage fraction, kinetics, and bulk pair-correlation were studied, but not the finite joint order-statistic law.
  • Asymptotic work carried absorption-count moments to their limiting constants but stopped short of exact finite-L moment functions.The missing functions are described as piecewise-polylogarithmic solutions of the same Volterra equations.
  • The unresolved finite-length theory reflects a mismatch between the problem's piecewise multiple-polylogarithmic structure and previously used machinery.

3. The moment program parked at the constant.

The paper identifies a deeper unresolved issue in transferring exact uniform-placement theory to locally constrained settings: finite laws under sensing uncertainty and global-information limits remain unsettled.

  • The model is deliberately abstract, so three idealisations constrain whether its results transfer to deployed systems.
  • With sensing and actuation uncertainty, hard-core exclusion becomes probabilistic, and whether the exact finite-s laws survive is unaddressed.
  • Uniform placement requires global knowledge of the segment and occupied intervals, exceeding the traversal or memory resources of the earlier platforms.
  • A bounded local sampling window avoids traversal and global memory, but its saturation density and exact finite-s order statistics remain open.
  • The proposed program parameterises the attachment window to test how the splitting law and exact theory degrade as placement becomes local.
Loading 2608.22671v1…