Introduction

The parking problem was proposed by Alfred Rényi in 1958 - cars, modelled as unit intervals, are placed at random upon a street of length $x$ until no spaces that can accommodate cars remain. Rényi showed that the jamming limit, or expected coverage of cars on the street, is approximately $75%$.

As well as being an interesting problem in it's own right, applications of the parking problem are numerous in physics and chemistry. One of the most interesting applications is in the theory of Random Sequential Adsorption, or RSA, which models the surface deposition of particles upon a substrate.

There are a number of approaches to this problem in one dimensions. In this series we will look at three of the approaches - an elementary treatment, an analytic approach, and the kinetic approach that looks at the time evolution of the line filling process.

We will also look at a number of different generalizations of the problem, including parking with overlap, also know as cooperative RSA, and the reversible parking problem, where cars arrive and leave at different rates.

Problem Statement

Consider an interval $(0, x)$ upon which we place a segment of unit length at random. We continue by placing a second segment of unit length randomly upon the original interval, discarding the segment if it overlaps with the original one.

We continue in this fashion until we can no longer add unit segments without overlap. At each step the next position within the interval is chosen from a uniform distribution of the remaining locations within the interval.

We are interested in both the expected value of the number of unit segments contained within the interval $(0, x)$, denoted $M(x)$, and the expected filling density of unit segments within the interval, denoted $M(x) / x$.

Derivation of the Master Equation

We first look at the derivation of the master equation for $M(x)$ which forms the heart of the problem, and will be crop up in the rest of the paper.

We initially consider an interval $(0, x + 1)$ and upon this place a unit segment $(t, t + 1)$. This unit segment partitions the original interval into two smaller intervals - $(0, t)$ and $(t + 1, x + 1)$. The expected number of unit segments contained within the original interval is:

$$ M(x + 1) = M(t) + 1 + M(x - t) $$

where $1$ represents the expectation of the added segment within the unit interval $(t, t + 1)$ - in other words, we have one unit segment within the unit interval $(t, t + 1)$. Integrating with respect to $t$ we get:

$$ \begin{align*} \int_{0}^{x} M(x + 1) dt & = \int_{0}^{x} [M(t) + 1 + M(x - t)] dt \\ M(x + 1) \int_{0}^{x} dt & = \int_{0}^{x} dt + \int_{0}^{x} [M(t) + M(x - t)] dt \\ M(x + 1) \cdot x & = x + \int_{0}^{x} [M(t) + M(x - t)] dt \\ M(x + 1) & = 1 + \frac{1}{x} \int_{0}^{x} [M(t) + M(x - t)] dt \end{align*} $$

as the distributions within each of the smaller intervals are uniform, and hence the same, we get:

$$ M(x + 1) = 1 + \frac{2}{x} \int_{0}^{x} M(t) dt $$

changing variables we get:

$$ M(x) = 1 + \frac{2}{x - 1} \int_{0}^{x - 1} M(t) dt $$

more completely, and because adding a unit segment to an interval of length less than $1$ has no meaning, the equation for $M(x)$ can be written as follows:

$$ M(x) = \begin{dcases} 0, & \text{for } 0 \leq x < 1 \\ 1, & \text{for } x = 1 \\ 1 + \frac{2}{x - 1} \int_{0}^{x - 1} M(t) dt, & \text{for } x > 1 \end{dcases} $$

which has the form of a recurrence.

Applications

One of the most important applications of the parking problem is to the theory of random sequential adsorption (RSA), which models the adsorption of particles onto a solid substrate. It is important to make the distinction between adsorption and absorption - adsorption involves the surface of the material involved, whereas absorption involves the full volume of the material.

Some examples of RSA are adsorption of gas molecules, polymer chains, latex particles, bacteria, proteins, and colloidal particles (insoluble particles contained within a suspension) onto a surface.

Another important application is when applied to genome sequencing where a newly-arriving sequenced clone is allowed to partially overlap an existing sequenced clone - in which case the parking problem with overlap is the most relevant model. In some cases adsorbed particles can also be released from a surface, a process know as desorption, and in this case the reversible parking problem is the most relevant model.

In order to maximize the adsorption of particles, a clear understanding of the problem is required, and to that end we need to be able to faithfully model the process. This series of posts will offer a survey of the approaches to modelling the one-dimensional parking problem, and provide a different approach to both validate the approaches used to model the process, and to calculate the associated constants.