# A renewal approach to configurational entropy in one dimension

P L Krapivsky1,2 and J M Luck3 1 Department of Physics, Boston University,
Boston, MA 02215, USA  2 Santa Fe Institute, Santa Fe, NM 87501, USA  3
Université Paris-Saclay, CNRS, CEA, Institut de Physique Théorique, 91191 Gif-
sur-Yvette, France<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We introduce a novel approach, inspired from the theory of renewal processes,
to determine the configurational entropy of ensembles of constrained
configurations of particles on the one-dimensional lattice. The proposed
method can deal with all local rules involving only the lengths of clusters of
occupied and empty sites. Within this scope, this method is both more
systematic and easier to implement than the transfer-matrix approach. It is
illustrated in detail on the $k$-mer deposition model and on ensembles of
trapped Rydberg atoms with blockade range $b$.

,

##  1 Introduction

A variety of complex systems, including spin glasses, structural glasses and
granular matter, are known to possess many metastable states at low enough
temperature and/or high enough density [1, 2, 3, 4, 5, 6, 7]. These metastable
states are usually defined by dynamical considerations. They have been given
various names in different contexts, including valleys, pure states, quasi-
states and inherent structures. The number ${\cal N}(N,E)$ of metastable
states with energy density $E$ usually grows exponentially with the system
size $N$, as

${\cal N}(N,E)\sim\exp(N\,S(E)),$ (1.1)

where $S(E)$ is the configurational entropy, or complexity, of the system [8,
9].

The one-dimensional geometry is a convenient playground to investigate the
statistics of these metastable states. There, metastability only takes place
at zero temperature, and valleys typically consist of single blocked
configurations. A broad range of one-dimensional kinetic spin models possess
an exponentially large number of blocked configurations, which identify with
the attractors of zero-temperature dynamics. This class includes pristine
models, such as the ferromagnetic Ising chain with Kawasaki dynamics [10, 11],
disordered models, such as the Ising spin glass with single-spin-flip dynamics
[12, 13], and a class of kinetically constrained spin models [14, 15, 16, 17,
18, 19, 20, 21, 22] and of related lattice gas models [23, 24, 25, 26, 27].
The zero-temperature dynamics of these kinetically constrained models is fully
irreversible. In most cases, it can be mapped onto RSA (random sequential
adsorption) or CSA (cooperative sequential adsorption) models, where objects
are deposited sequentially on an initially empty substrate [28, 29, 30]. This
mapping brings several simplifications. Blocked configurations often have a
local characterization in terms of forbidden patterns. The configurational
entropy counting the latter configurations can be determined either by a
direct combinatorial reasoning [17, 31, 32, 33, 34, 35] or by using the
transfer-matrix approach [20, 22]. The dynamics of this class of models can
also be solved exactly by an analytical approach based on considering empty
intervals (see [36, 37] for overviews). These models are strongly non-ergodic.
The energy density $E_{\infty}$ at the end of the zero-temperature dynamical
process, where the system is blocked in one of its many attractors, depends
continuously on the energy density $E_{0}$ of the initial state. For the most
probable infinite-temperature initial state ($E_{0}=0$), the final energy
density $E_{\infty}$ is slightly different from the most probable one
$E_{\star}$, which maximizes the configurational entropy $S(E)$. This
testifies a weak violation of the flatness hypothesis originally formulated by
Edwards for slowly compacting granular matter (see [38] for a recent review).

The physics of ultracold atoms provides another motivation for investigating
the configurational entropy $S(\rho)$ of statistical ensembles of particles
defined by local constraints, where $\rho$ now denotes the particle density.
Trapped Rydberg atoms provide a promising experimental playground for quantum
information processing, quantum computation and quantum simulation [39]. The
strong interactions between Rydberg atoms generate a blockade, preventing the
excitation of further Rydberg atoms in some vicinity of an already existing
one [40, 41, 42, 43, 44, 45]. Under certain conditions, the Rydberg blockade
yields patterns of atoms, either on periodic optical lattices or on more
complex graphs and networks, which are somehow similar to the blocked
configurations of RSA models [46]. A simple setting is that of a one-
dimensional optical lattice, where each lattice site occupied by a Rydberg
atom must have at least $b$ empty sites on either side [35]. The integer
$b\geq 1$ is referred to as the blockade range of the model. The problem with
blockade range $b=1$ on more complex graphs amounts to counting the ‘maximal
independent sets’ on the underlying graph. This combinatorial task is known to
be a hard NP-complete one in general [47]. Quite recently, experimental
systems of Rydberg atoms have been demonstrated to be able to find maximal
independent sets in some geometries [48, 49].

The present paper has been elaborated concomitantly with the work by Došlić et
al. [50]. Here, our main goal is to introduce a novel exact method to
determine the configurational entropy $S(\rho)$ of statistical ensembles of
constrained configurations of particles on the one-dimensional lattice defined
by local rules. This approach, inspired from the theory of renewal processes,
provides an alternative to the usual methods recalled above, based either on
direct combinatorial reasoning or on the transfer-matrix approach. The usage
of the renewal approach is however limited to constraints involving the
lengths of clusters of occupied and empty sites. Within this scope, it is more
systematic and easier to implement than both other methods. The renewal
approach itself is described in section 2. Section 3 is devoted to the
analysis of quantities pertaining to the thermodynamic limit, including the
cumulants of the number of particles and the configurational entropy. Fully
explicit expressions are presented in section 4 for three simple statistical
ensembles. The main focus is then on the $k$-mer deposition model and on
assemblies of trapped Rydberg atoms with blockade range $b$. Both models are
essentially equivalent to each other, with $k=b+1$. They are respectively
investigated in sections 5 and 6. A brief discussion is given in section 7.
Two appendices are respectively devoted to an extension of the renewal
approach to several species of particles, and to a reminder on the transfer-
matrix formalism.

##  2 Renewal approach

Within the present approach, a configuration ${\cal C}$ is a sequence of
particles (i.e., occupied sites, noted ${\bullet}$) and holes (i.e., empty
sites, noted ${\circ}$) on the half-infinite one-dimensional chain. The basic
variables are the lengths $i_{1}$, $j_{1}$, $i_{2}$, $j_{2},$ $\dots$ of the
clusters of contiguous occupied and empty sites. The configuration thus reads

${\cal
C}=\underbrace{{\bullet}\cdots{\bullet}}_{i_{1}}\underbrace{{\circ}\cdots{\circ}}_{j_{1}}\underbrace{{\bullet}\cdots{\bullet}}_{i_{2}}\underbrace{{\circ}\cdots{\circ}}_{j_{2}}\cdots$
(2.1)

if the first site is occupied, and

${\cal
C}=\underbrace{{\circ}\cdots{\circ}}_{j_{1}}\underbrace{{\bullet}\cdots{\bullet}}_{i_{1}}\underbrace{{\circ}\cdots{\circ}}_{j_{2}}\underbrace{{\bullet}\cdots{\bullet}}_{i_{2}}\cdots$
(2.2)

if the first site is empty.

We define a statistical ensemble of configurations by putting the following
constraints on the (mutually independent) cluster lengths:

  * •

the lengths $i_{1}$, $i_{2}$, $\dots$ of clusters of occupied sites belong to
some set ${\cal I}$ of integers.

  * •

the lengths $j_{1}$, $j_{2}$, $\dots$ of clusters of empty sites belong to
some set ${\cal J}$ of integers.

The first quantity of interest is the total number ${\cal N}_{N}$ of
configurations ${\cal C}_{N}$ on a finite system of length $N$. It is
understood that the rightmost cluster ends exactly at site $N$. In other
words, at variance with the usual approach to renewal processes in continuous
time, no overhang is permitted.

We have

$\displaystyle{\cal N}_{N}$ $\displaystyle=$ $\displaystyle\sum_{i_{1}\in{\cal
I}}\delta_{i_{1},N}+\sum_{i_{1}\in{\cal I}}\sum_{j_{1}\in{\cal
J}}\delta_{i_{1}+j_{1},N}$ (2.3) $\displaystyle+\sum_{i_{1}\in{\cal
I}}\sum_{j_{1}\in{\cal J}}\sum_{i_{2}\in{\cal
I}}\delta_{i_{1}+j_{1}+i_{2},N}+\cdots$ $\displaystyle+$
$\displaystyle\sum_{j_{1}\in{\cal J}}\delta_{j_{1},N}+\sum_{j_{1}\in{\cal
J}}\sum_{i_{1}\in{\cal I}}\delta_{j_{1}+i_{1},N}$
$\displaystyle+\sum_{j_{1}\in{\cal J}}\sum_{i_{1}\in{\cal
I}}\sum_{j_{2}\in{\cal J}}\delta_{j_{1}+i_{1}+j_{2},N}+\cdots,$

where the first two and last two lines respectively correspond to (2.1) and
(2.2).

An efficient way of resumming the above series is suggested by a formal
analogy with the theory of renewal processes [51, 52, 53] (see [54, 55] for
presentations by physicists). Introduce the generating series

$I(z)=\sum_{i\in{\cal I}}z^{i},\qquad J(z)=\sum_{j\in{\cal J}}z^{j},$ (2.4)

associated with the sets ${\cal I}$ and ${\cal J}$ encoding the definition of
the statistical ensemble. The generating series of the numbers of
configurations,

${\cal N}(z)=\sum_{N\geq 0}{\cal N}_{N}z^{N},$ (2.5)

then reads

$\displaystyle{\cal N}(z)=1+{\cal N}_{I}(z)+{\cal N}_{J}(z),$
$\displaystyle{\cal N}_{I}(z)=I(z)+I(z)J(z)+I(z)J(z)I(z)+\cdots,$
$\displaystyle{\cal N}_{J}(z)=J(z)+J(z)I(z)+J(z)I(z)J(z)+\cdots$ (2.6)

The initial term ${\cal N}_{0}=1$ is somehow conventional, whereas ${\cal
N}_{I}(z)$ and ${\cal N}_{J}(z)$ are in correspondence with (2.1) and (2.2).
These series obey the ‘renewal equations’

${\cal N}_{I}(z)=I(z)(1+{\cal N}_{J}(z)),\qquad{\cal N}_{J}(z)=J(z)(1+{\cal
N}_{I}(z)).$ (2.7)

Solving the above linear equations, we obtain our first key result:

${\cal N}(z)=\frac{(1+I(z))(1+J(z))}{1-I(z)J(z)}.$ (2.8)

The second quantity of interest is the number ${\cal N}_{N,M}$ of
configurations on a system of length $N$, comprising exactly $M$ particles,
i.e., $M$ occupied sites and $N-M$ empty ones. This quantity is advantageously
encoded in the partition function

$Z_{N}(x)=\sum_{M=0}^{N}{\cal N}_{N,M}x^{M},$ (2.9)

obtained by attributing a positive weight $x$ to each particle. We have
therefore

$\langle x^{M}\rangle=\frac{Z_{N}(x)}{Z_{N}(1)},$ (2.10)

where brackets denote an average over all configurations ${\cal C}_{N}$ of
length $N$.

The partition function reads alternatively

$Z_{N}(x)=\sum_{{\cal C}_{N}}x^{M({\cal C}_{N})},$ (2.11)

where the sum runs over all configurations ${\cal C}_{N}$, with

$M({\cal C}_{N})=i_{1}+i_{2}+\cdots$ (2.12)

being the number of particles in the configuration ${\cal C}_{N}$. In analogy
with (2.6), the generating series of the partition functions, namely

$Z(z,x)=\sum_{N\geq 0}Z_{N}(x)z^{N}=\sum_{N\geq 0}\sum_{M=0}^{N}{\cal
N}_{N,M}z^{N}x^{M},$ (2.13)

reads

$\displaystyle Z(z,x)=1$ $\displaystyle+$ $\displaystyle
I(xz)+I(xz)J(z)+I(xz)J(z)I(xz)+\cdots$ (2.14) $\displaystyle+$ $\displaystyle
J(z)+J(z)I(xz)+J(z)I(xz)J(z)+\cdots$

We thus obtain our second key result:

$Z(z,x)=\frac{(1+I(xz))(1+J(z))}{1-I(xz)J(z)}.$ (2.15)

For $x=1$, where all configurations have the same weight, we have

$Z(z,1)={\cal N}(z),$ (2.16)

and therefore

$Z_{N}(1)={\cal N}_{N}=\sum_{M=0}^{N}{\cal N}_{N,M},$ (2.17)

as should be.

The expressions (2.8) and (2.15) hold in full generality. They are the most
useful in the rational case where both generating series

$I(z)=\frac{A_{I}(z)}{B_{I}(z)},\qquad J(z)=\frac{A_{J}(z)}{B_{J}(z)}$ (2.18)

are rational functions of $z$. The expressions (2.8) and (2.15) then read

${\cal N}(z)=\frac{C(z)}{D(z)},$ (2.19)

where

$\displaystyle C(z)=(A_{I}(z)+B_{I}(z))(A_{J}(z)+B_{J}(z)),$ $\displaystyle
D(z)=B_{I}(z)B_{J}(z)-A_{I}(z)A_{J}(z)$ (2.20)

are polynomials in $z$, and

$Z(z,x)=\frac{C(z,x)}{D(z,x)},$ (2.21)

where

$\displaystyle C(z,x)=(A_{I}(xz)+B_{I}(xz))(A_{J}(z)+B_{J}(z)),$
$\displaystyle D(z,x)=B_{I}(xz)B_{J}(z)-A_{I}(xz)A_{J}(z)$ (2.22)

are polynomials in $z$ and $x$. We have consistently $C(z)=C(z,1)$ and
$D(z)=D(z,1)$.

The complexity of an ensemble can be measured by the degree $\Delta$ of the
polynomial $D(z)$, which coincides with the degree in $z$ of $D(z,x)$. In
particular, as a consequence of (2.19), the total numbers ${\cal N}_{N}$ of
configurations obey a linear recursion with constant integer coefficients,
whose number of terms is at most $\Delta+1$. Explicit examples will be given
in (4.17) and (5.13).

The rational class encompasses a panoply of ensembles. If ${\cal I}$ is a
finite set, $I(z)$ is a polynomial in $z$. If ${\cal I}=\\{b,2b,3b,\dots\\}$
is the sublattice of index $b$, we have

$I(z)=\frac{z^{b}}{1-z^{b}}.$ (2.23)

The rational class therefore comprises all cases where the sets ${\cal I}$ and
${\cal J}$ are either finite sets, sublattices, or any finite unions of such
sets. From now on, we restrict ourselves to this rational class of ensembles.

##  3 Thermodynamic limit

The above approach provides an efficient framework to investigate the
distribution of the number $M$ of particles in the thermodynamic limit of very
large systems.

In the simplest cases, the renewal approach also gives access to the full
finite-size combinatorics encoded in the numbers ${\cal N}_{N,M}$ (see section
4).

###  3.1 Cumulants of number of particles

A first side of the problem concerns the cumulants of the number $M$ of
particles in a very large system of size $N$.

The rational expression (2.21) of the generating series $Z(z,x)$ implies an
asymptotic exponential behavior of the partition function $Z_{N}(x)$ at large
$N$, namely

$Z_{N}(x)\sim z_{0}(x)^{-N},$ (3.1)

where $z_{0}(x)$ is the nearest zero of the polynomial $D(z,x)$, i.e., that
with smallest modulus among the $\Delta$ zeros. Since the weight $x$ is real,
the partition functions $Z_{N}(x)$ are positive, and so $z_{0}(x)$ is real and
positive. Depending on $x$, $z_{0}(x)$ may be either smaller or larger than
unity.

Setting

$x=\rme^{\beta},$ (3.2)

where $\beta$ is a fictitious inverse temperature, being either positive or
negative, the identity (2.10) yields

$\langle\rme^{\beta M}\rangle\sim\rme^{NF(\beta)},$ (3.3)

where the configurational free energy $F(\beta)$ reads

$F(\beta)=\ln z_{\star}-\ln z_{0}(\rme^{\beta}),\qquad z_{\star}=z_{0}(1).$
(3.4)

We assume that the problem is non-trivial, in the sense that at least one of
the sets ${\cal I}$ and ${\cal J}$ contains more than one point. The free
energy then has a full ‘high-temperature’ power-series expansion of the form

$F(\beta)=\sum_{n\geq 1}\frac{c_{n}}{n!}\,\beta^{n}.$ (3.5)

As a consequence of (3.3), all cumulants of $M$ grow linearly with the system
size $N$, as

$\langle M^{n}\rangle_{c}\approx c_{n}N.$ (3.6)

In particular, the mean and the variance of the particle number grow as

$\displaystyle\langle M\rangle\approx c_{1}N,$ $\displaystyle\langle
M^{2}\rangle_{c}=\langle M^{2}\rangle-\langle M\rangle^{2}\approx c_{2}N.$
(3.7)

The first cumulant amplitude $c_{1}$ is nothing but the most probable density
$\rho_{\star}$ (see (3.17)), as should be.

###  3.2 Configurational entropy

Let us turn to the asymptotic growth of the number ${\cal N}_{N,M}$ of
configurations ${\cal C}_{N}$ of a system of size $N$ comprising $M$
particles, i.e., $M$ occupied sites. This number is expected on general
grounds to scale as (see (1.1))

${\cal N}_{N,M}\sim\exp(N\,S(\rho)),$ (3.8)

where the microcanonical configurational entropy $S(\rho)$ is a function of
the particle density

$\rho=\frac{M}{N}.$ (3.9)

The total number ${\cal N}_{N}$ of configurations ${\cal C}_{N}$ on a system
of size $N$ therefore also grows exponentially, as

${\cal N}_{N}\sim\rme^{NS_{\star}},\qquad S_{\star}=\,\mathrel{\mathop{{\rm
max}}\limits_{\rho}}S(\rho).$ (3.10)

The value $\rho_{\star}$ of the density where the microcanonical entropy
$S(\rho)$ reaches its maximum $S_{\star}$ represents the most probable density
in the thermodynamic limit.

The configurational entropy $S(\rho)$ can be derived as follows. The partition
function $Z_{N}(x)$ can be estimated by using (2.9), (3.1) and (3.8). We thus
obtain

$Z_{N}(x)\sim\int\rme^{N[S(\rho)+\rho\ln x]}\,{\rm d}\rho\sim\rme^{-N\ln
z_{0}(x)}.$ (3.11)

The saddle-point method yields

$\ln z_{0}(x)=-\mathrel{\mathop{{\rm max}}\limits_{\rho}}[S(\rho)+\rho\ln x].$
(3.12)

This equality expresses that the functions $S(\rho)$ and $\ln z_{0}(x)$ are
Legendre transforms of each other. We have therefore

$S(\rho)=-\ln z_{0}(x)-\rho\ln x,$ (3.13)

with

$\rho=-\frac{{\rm d}\ln z_{0}}{{\rm d}\ln x}=-\frac{x}{z_{0}}\,\frac{{\rm
d}z_{0}}{{\rm d}x}=\left(\frac{x\,\partial D/\partial x}{z\,\partial
D/\partial z}\right)_{z=z_{0}(x)}.$ (3.14)

We have alternatively, using (3.2) and (3.4),

$S(\rho)=-\ln z_{\star}+F(\beta)-\beta\rho,\qquad\rho=\frac{{\rm d}F}{{\rm
d}\beta}.$ (3.15)

The maximal entropy $S_{\star}$ is reached for $x=1$, i.e., $\beta=0$, as
should be, since this is the case where all configurations ${\cal C}_{N}$ have
equal weights. We have

$S_{\star}=-\ln z_{\star}.$ (3.16)

The series expansion (3.5) ensures that the corresponding density reads

$\rho_{\star}=c_{1},$ (3.17)

and that $S(\rho)$ departs quadratically from its maximum $S_{\star}$, as

$S(\rho)\approx S_{\star}-\frac{(\rho-\rho_{\star})^{2}}{2c_{2}}.$ (3.18)

Another interpretation of the configurational entropy $S(\rho)$ is as follows.
The probability $P_{N}(\rho)$ of observing a configuration ${\cal C}_{N}$ with
an atypical density $\rho\neq\rho_{\star}$ is given by a large-deviation
formula of the form

$P_{N}(\rho)\sim\exp(-N\Sigma(\rho)),$ (3.19)

where the large-deviation function reads

$\Sigma(\rho)=S_{\star}-S(\rho).$ (3.20)

Using (3.15) and (3.16), we have alternatively

$\Sigma(\rho)=\beta\rho-F(\beta).$ (3.21)

The large-deviation function is positive, and vanishes quadratically in the
vicinity of $\rho_{\star}$, according to (see (3.18))

$\Sigma(\rho)\approx\frac{(\rho-\rho_{\star})^{2}}{2c_{2}}.$ (3.22)

##  4 Three simple cases

The complexity of a statistical ensemble has been argued to be dictated by the
degree $\Delta$ of the polynomial $D(z)$. In this section we illustrate the
above general results on the only three examples (up to symmetries) where
either $\Delta=1$ (Section 4.1) or $\Delta=2$ (Sections 4.2 and 4.3). These
examples essentially exhaust all cases where fully explicit expressions can be
obtained, either for finite systems or in the thermodynamic limit.

###  4.1 Flat ensemble

The first and simplest ensemble is the flat one, where all cluster lengths are
equally permitted. Equivalently, each site of the lattice is independently
either occupied or empty. We have ${\cal I}={\cal J}=\\{1,2,3,\dots\\}$, so
that

$I(z)=J(z)=\frac{z}{1-z}.$ (4.1)

The formula (2.8) reads

${\cal N}(z)=\frac{1}{1-2z},$ (4.2)

so that

${\cal N}_{N}=2^{N}.$ (4.3)

The formula (2.15) reads

$Z(z,x)=\frac{1}{1-(1+x)z}.$ (4.4)

This is the only instance where the polynomials

$D(z)=1-2z,\qquad D(z,x)=1-(1+x)z$ (4.5)

have degree $\Delta=1$ in $z$. The expression (4.4) yields

${\cal N}_{N,M}={N\choose M},$ (4.6)

where $M$ ranges from $0$ to $N$.

Asymptotic expressions in the thermodynamic limit are also simple. We have

$z_{0}(x)=\frac{1}{1+x},$ (4.7)

so that (3.4) yields

$F(\beta)=\ln\frac{1+\rme^{\beta}}{2}=\frac{\beta}{2}+\ln\cosh\frac{\beta}{2}.$
(4.8)

We have therefore

$\rho_{\star}=c_{1}=\frac{1}{2},$ (4.9)

in agreement with particle-hole symmetry, whereas all higher-order odd
cumulants vanish. The even cumulant amplitudes are given by

$c_{n}=\frac{2^{n}-1}{n}\,B_{n},$ (4.10)

where $B_{n}$ are the Bernoulli numbers, i.e.,

$c_{2}=\frac{1}{4},\quad c_{4}=-\frac{1}{8},\quad c_{6}=\frac{1}{4},\quad
c_{8}=-\frac{17}{16},\quad\hbox{etc.}$ (4.11)

The formula (3.14) implies that $x$ and $z_{0}(x)$ can be expressed as
rational functions of the density $\rho$:

$x=\frac{\rho}{1-\rho},\qquad z_{0}(x)=1-\rho,$ (4.12)

so that (3.13) yields the explicit expression

$S(\rho)=-\rho\ln\rho-(1-\rho)\ln(1-\rho)$ (4.13)

for $0<\rho<1$. The above formula coincides with the well-known expression for
the entropy of mixing. It is the largest possible value for the
configurational entropy $S(\rho)$ of an ensemble consisting of occupied and
empty sites. In particular,

$S_{\star}=\ln 2\approx 0.693147,$ (4.14)

in agreement with (4.3). This is the largest possible value for the entropy
$S_{\star}$.

###  4.2 Isolated empty sites

This second ensemble is defined by the condition that empty sites are
isolated. The dual ensemble where occupied sites are isolated is simply
obtained from the present one by changing $M$ to $N-M$, and $\rho$ to
$1-\rho$. These two ensembles have already been considered in several
contexts, including the attractors of repulsion processes [56] and packings of
disks in narrow channels [57, 58].

In the present case we have ${\cal I}=\\{1,2,3,\dots\\}$ and ${\cal
J}=\\{1\\}$, so that

$I(z)=\frac{z}{1-z},\qquad J(z)=z.$ (4.15)

The formula (2.8) reads

${\cal N}(z)=\frac{1+z}{1-z-z^{2}},$ (4.16)

implying that the numbers ${\cal N}_{N}$ obey the recursion

${\cal N}_{N}={\cal N}_{N-1}+{\cal N}_{N-2},$ (4.17)

defining the Fibonacci numbers

$F_{n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right].$
(4.18)

These integers are listed in entry A000045 of the OEIS [59], together with
many formulas and references. The initial values ${\cal N}_{0}=1$, ${\cal
N}_{1}=2$ lead to

${\cal N}_{N}=F_{N+2}.$ (4.19)

The formula (2.15) reads

$Z(z,x)=\frac{1+z}{1-xz-xz^{2}}.$ (4.20)

The polynomials

$D(z)=1-z-z^{2},\qquad D(z,x)=1-xz-xz^{2}$ (4.21)

have degree $\Delta=2$ in $z$. The expression (4.20) yields after some algebra

${\cal N}_{N,M}={M+1\choose N-M}.$ (4.22)

The minimal value of $M$ is either $N/2$ (if $N$ is even) or $(N-1)/2$ (if $N$
is odd), whereas its maximal value is $N$.

Asymptotic expressions in the thermodynamic limit are also simple. We have

$z_{0}(x)=\frac{\sqrt{x(x+4)}-x}{2x},$ (4.23)

so that (3.4) yields

$F(\beta)=\beta+\ln\frac{1+\sqrt{1+4\rme^{-\beta}}}{1+\sqrt{5}},$ (4.24)

and so

$\rho_{\star}=c_{1}=\frac{5+\sqrt{5}}{10}\approx 0.723606,$ (4.25)

and

$c_{2}=\frac{\sqrt{5}}{25},\quad c_{3}=\frac{\sqrt{5}}{125},\quad
c_{4}=-\frac{\sqrt{5}}{125},\quad\hbox{etc.}$ (4.26)

Even though the polynomial $D(z,x)$ is quadratic in $z$, both $x$ and
$z_{0}(x)$ can be expressed as rational functions of the density $\rho$:

$x=\frac{(2\rho-1)^{2}}{\rho(1-\rho)},\qquad z_{0}(x)=\frac{1-\rho}{2\rho-1},$
(4.27)

so that (3.13) yields the explicit expression

$S(\rho)=-(2\rho-1)\ln(2\rho-1)-(1-\rho)\ln(1-\rho)+\rho\ln\rho$ (4.28)

for $1/2<\rho<1$. In particular,

$S_{\star}=\ln\frac{1+\sqrt{5}}{2}\approx 0.481211,$ (4.29)

in agreement with (4.19).

###  4.3 Even particle clusters

This third ensemble is defined by the condition that all clusters of particles
(i.e., of occupied sites) have even lengths. We have ${\cal
I}=\\{2,4,6,\dots\\}$ and ${\cal J}=\\{1,2,3,\dots\\}$, so that

$I(z)=\frac{z^{2}}{1-z^{2}},\qquad J(z)=\frac{z}{1-z}.$ (4.30)

The formula (2.8) reads

${\cal N}(z)=\frac{1}{1-z-z^{2}},$ (4.31)

implying that the numbers of configurations are again given by Fibonacci
numbers:

${\cal N}_{N}=F_{N+1}.$ (4.32)

The formula (2.15) reads

$Z(z,x)=\frac{1}{1-z-x^{2}z^{2}}.$ (4.33)

The polynomials

$D(z)=1-z-z^{2},\qquad D(z,x)=1-z-x^{2}z^{2}$ (4.34)

have degree $\Delta=2$ in $z$. The number $M$ of particles is necessarily
even. The expression (4.33) yields after some algebra

${\cal N}_{N,M}={N-{\scriptstyle{\scriptstyle 1\over\scriptstyle
2}}M\choose{\scriptstyle{\scriptstyle 1\over\scriptstyle 2}}M}.$ (4.35)

The minimal value of $M$ is 0, whereas its maximal value is either $N$ (if $N$
is even) or $N-1$ (if $N$ is odd).

Asymptotic expressions in the thermodynamic limit are also simple. We have

$z_{0}(x)=\frac{\sqrt{1+4x^{2}}-1}{2x^{2}},$ (4.36)

so that (3.4) yields

$F(\beta)=\ln\frac{1+\sqrt{1+4\rme^{2\beta}}}{1+\sqrt{5}},$ (4.37)

and so

$\rho_{\star}=c_{1}=\frac{5-\sqrt{5}}{5}\approx 0.552786,$ (4.38)

and

$c_{2}=\frac{4\sqrt{5}}{25},\quad c_{3}=-\frac{8\sqrt{5}}{125},\quad
c_{4}=-\frac{16\sqrt{5}}{125},\quad\hbox{etc.}$ (4.39)

Here again, both $x^{2}$ and $z_{0}(x)$ can be expressed as rational functions
of the density $\rho$:

$x^{2}=\frac{\rho(2-\rho)}{4(1-\rho)^{2}},\qquad
z_{0}(x)=\frac{2(1-\rho)}{2-\rho},$ (4.40)

so that (3.13) yields the explicit expression

$S(\rho)=\frac{1}{2}(2-\rho)\ln(2-\rho)-(1-\rho)\ln(2(1-\rho))-\frac{1}{2}\,\rho\ln\rho$
(4.41)

for $0<\rho<1$. In particular,

$S_{\star}=\ln\frac{1+\sqrt{5}}{2}\approx 0.481211,$ (4.42)

in agreement with (4.32), is the same as in the previous ensemble (see
(4.29)).

Figure 1 shows plots of the configurational entropy $S(\rho)$ against the
particle density $\rho$, for the three simple ensembles investigated in
section 4.

Figure 1: Configurational entropy $S(\rho)$ of the three simple ensembles
investigated in section 4, against particle density $\rho$. Red curve (1):
flat ensemble (see (4.13)). Green curve (2): ensemble with isolated empty
sites (see (4.28)). Blue curve (3): ensemble with even particle clusters (see
(4.41)).

##  5 $k$-mer deposition model

In this section we investigate the problem of the deposition of $k$-mers,
i.e., clusters of $k$ particles, starting from an empty lattice [60, 61, 62].
This is a prototypical example of the class of RSA models discussed in the
Introduction (see [28, 29, 30] for reviews). The integer $k\geq 2$ is the only
parameter of the model, with $k=2$ corresponding to dimers, $k=3$ to trimers,
and so on. Our aim is to investigate the statistical ensemble of the blocked
(or jammed) configurations, where no single $k$-mer can be inserted any more.
These configurations consist of sequences of contiguous $k$-mers, separated by
clusters of empty sites whose length is at most $k-1$. Figure 2 shows a
typical blocked configuration of the trimer problem, together with the
corresponding configuration of Rydberg atoms with blockade range $b=2$ (see
section 6).

The statistical ensemble of blocked configurations of $k$-mers has been
studied by combinatorial methods [33, 34, 35]. It is investigated by yet
another approach in [50].

Figure 2: Top row: typical blocked configuration of the trimer problem. Bottom
row: corresponding configuration of Rydberg atoms with blockade range $b=2$
(see section 6).

###  5.1 General theory

The ensemble of blocked configurations can be described in terms of
independent clusters, and therefore studied by the renewal approach, with
${\cal I}=\\{k,2k,3k,\dots\\}$ being the sublattice of index $k$, whereas
${\cal J}=\\{1,2,\dots,k-1\\}$.

We have therefore

$I(z)=\frac{z^{k}}{1-z^{k}},\qquad J(z)=\frac{z-z^{k}}{1-z}.$ (5.1)

The formulas (2.8) and (2.15) respectively read

${\cal N}(z)=\frac{1-z^{k}}{1-z-z^{k}+z^{2k}},$ (5.2)
$Z(z,x)=\frac{1-z^{k}}{1-z-x^{k}z^{k}+x^{k}z^{2k}}.$ (5.3)

The first of these results was derived by a purely combinatorial approach in
[34]. The numerators and denominators of (5.2) and (5.3) have the common root
$z=1$. As a consequence, the degree of the denominators

$\displaystyle D(z)=1-z-z^{k}+z^{2k},$ $\displaystyle
D(z,x)=1-z-x^{k}z^{k}+x^{k}z^{2k}$ (5.4)

can be reduced to $\Delta=2k-1$.

The relationship between the parameter $x$ and the smallest root $z_{0}(x)$ of
the polynomial $D(z,x)$ takes the form

$x^{k}=\frac{1-z_{0}(x)}{z_{0}(x)^{k}(1-z_{0}(x)^{k})}.$ (5.5)

The expression (3.14) for the density $\rho$ therefore reads

$\rho=\frac{k(1-z_{0}(x))(1-z_{0}(x)^{k})}{k+(1-k)z_{0}(x)-2kz_{0}(x)^{k}+(2k-1)z_{0}(x)^{k+1}}.$
(5.6)

The expression (3.13) for the configurational entropy simplifies to

$S(\rho)=-(1-\rho)\ln
z_{0}(x)+\frac{\rho}{k}\ln\frac{1-z_{0}(x)^{k}}{1-z_{0}(x)},$ (5.7)

where $\rho$ varies between the extremal values

$\rho_{\rm min}=\frac{k}{2k-1},\qquad\rho_{\rm max}=1.$ (5.8)

The maximum of the configurational entropy reads $S_{\star}=-\ln z_{\star}$
(see (3.16)), where $z_{\star}=z_{0}(1)$ obeys $D(z_{\star})=0$ (see (5.4)),
i.e.,

$1-z_{\star}-z_{\star}^{k}+z_{\star}^{2k}=0.$ (5.9)

The corresponding particle density reads

$\rho_{\star}=c_{1}=\frac{kz_{\star}^{k}(1-z_{\star}^{k})}{z_{\star}+kz_{\star}^{k}-2kz_{\star}^{2k}}.$
(5.10)

This expression can be obtained either from (5.5) and (5.6), or by using the
definition (3.4) and the expansion (3.5) of the configurational free energy
$F(\beta)$. The second approach yields the higher cumulant amplitudes $c_{n}$
as well. We mention here the expression of the variance amplitude for further
reference:

$c_{2}=\frac{k^{2}z_{\star}^{k}(1-z_{\star}^{k})(z_{\star}^{2}-z_{\star}^{k+1}+z_{\star}^{2k+1}-k^{2}z_{\star}^{3k})}{(z_{\star}+kz_{\star}^{k}-2kz_{\star}^{2k})^{3}}.$
(5.11)

The above expressions somehow simplify in the case of dimers ($k=2$) and in
the regime where $k$ is very large. These two situations are studied in detail
below.

###  5.2 The case of dimers $(k=2)$

The general theory simplifies as follows in the case of dimers. First, (2.8)
reads

${\cal N}(z)=\frac{1+z}{1-z^{2}-z^{3}},$ (5.12)

implying that the total numbers ${\cal N}_{N}$ of configurations obey the
recursion

${\cal N}_{N}={\cal N}_{N-2}+{\cal N}_{N-3},$ (5.13)

defining the Padovan numbers $P_{N}$. These integers are listed in entry
A000931 of the OEIS [59], together with many formulas and references. The
initial values ${\cal N}_{0}={\cal N}_{1}={\cal N}_{2}=1$ exactly lead to

${\cal N}_{N}=P_{N}.$ (5.14)

The recursion (5.13) and its solution (5.14) were obtained by combinatorial
approaches in [33, 35].

The case of dimers is also the only situation where (5.5) and (5.6) yield
rational expressions for $x^{2}$ and $z_{0}(x)$ in terms of the density
$\rho$:

$x^{2}=\frac{(3\rho-2)^{3}}{4\rho(1-\rho)^{2}},\qquad
z_{0}(x)=\frac{2(1-\rho)}{3\rho-2}.$ (5.15)

As a consequence, (5.7) translates to

$S(\rho)=-\frac{1}{2}(3\rho-2)\ln(3\rho-2)-(1-\rho)\ln(2(1-\rho))+\frac{1}{2}\,\rho\ln\rho,$
(5.16)

where the density $\rho$ varies between $\rho_{\rm min}=2/3$ and $\rho_{\rm
max}=1$.

The quantity $z_{\star}=z_{0}(1)$ obeys the cubic equation

$z_{\star}^{3}+z_{\star}^{2}-1=0,$ (5.17)

and so

$z_{\star}=\frac{1}{6}\bigl{(}(100+12\sqrt{69})^{1/3}+(100-12\sqrt{69})^{1/3}-2\bigr{)}\approx
0.754877$ (5.18)

is the reciprocal of the so-called plastic number

$\phi=\frac{1}{6}\bigl{(}(108+12\sqrt{69})^{1/3}+(108-12\sqrt{69})^{1/3}\bigr{)}\approx
1.324717,$ (5.19)

obeying

$\phi^{3}-\phi-1=0,$ (5.20)

and describing the asymptotic growth of Padovan numbers: $P_{N}\sim\phi^{N}$.
We have

$\displaystyle S_{\star}$ $\displaystyle=$ $\displaystyle-\ln
z^{\star}=\ln\phi\approx 0.281199,$ $\displaystyle\rho_{\star}$
$\displaystyle=$
$\displaystyle\frac{2(z^{\star}+1)}{3z^{\star}+2}=\frac{2(3z_{\star}^{2}+z_{\star}+7)}{23}\approx
0.822991,$ $\displaystyle c_{2}$ $\displaystyle=$
$\displaystyle\frac{4(29z_{\star}^{2}+2z_{\star}-9)}{529}\approx 0.068318.$
(5.21)

The first expression of $\rho_{\star}$ has been derived from (5.15), whereas
the second one has been obtained by reducing the first one by means of the
definition (5.17) of $z_{\star}$. The expression of $c_{2}$ has been derived
from (5.11) by the same procedure. Any rational expression in $z_{\star}$ can
indeed be reduced to a quadratic polynomial.

###  5.3 The regime of large $k$

The theory also simplifies for large $k$. There, a scaling regime where
$z_{0}(x)$ is close to unity dictates both the behavior of the cumulant
amplitudes $c_{n}$ and the form of the configurational entropy $S(\rho)$ in
the vicinity of its maximum $S_{\star}$. In order to explore this regime, we
set

$z_{0}(x)=\exp\left(-\frac{u(x)}{k}\right).$ (5.22)

Terms of relative order $1/k$ will be consistently neglected throughout the
following. The key equations (5.5), (5.6) and (5.7) respectively simplify to

$x^{k}\approx\frac{1}{k}\,u(x)\rme^{u(x)},$ (5.23)
$\rho\approx\frac{u(x)}{u(x)+1},$ (5.24)
$S(\rho)\approx\frac{1}{k}\,\frac{u(x)}{u(x)+1}\left(1+\ln\frac{k}{u(x)}\right).$
(5.25)

The last two relations can be combined to give

$S(\rho)\approx\frac{\rho}{k}\,\left(1+\ln\frac{k(1-\rho)}{\rho}\right).$
(5.26)

Let us consider first the maximum $S_{\star}$ of the configurational entropy
and the corresponding value $\rho_{\star}$ of the particle density. The most
direct approach consists in setting $x=1$ in (5.23). We thus find that
$u_{\star}=u(1)$ obeys

$u_{\star}\rme^{u_{\star}}\approx k,$ (5.27)

whereas (5.24) and (5.25) respectively become

$\rho_{\star}\approx\frac{u_{\star}}{u_{\star}+1},$ (5.28)
$S_{\star}\approx\frac{u_{\star}}{k}.$ (5.29)

The solution to (5.27) reads

$u_{\star}\approx W(k),$ (5.30)

in terms of the Lambert $W$ function. To leading order as $k$ is very large,
we have

$u_{\star}\approx\ln k,$ (5.31)

and therefore

$\rho_{\star}\approx 1-\frac{1}{\ln k},$ (5.32) $S_{\star}\approx\frac{\ln
k}{k}.$ (5.33)

The above estimates involving logarithmic factor will be commented and
illustrated at the end of this section. For the time being, let us show that
they can be turned into full asymptotic expansions in inverse powers of $\ln
k$. Introducing the notations

$\lambda=\ln k,\qquad\mu=\ln\lambda=\ln\ln k,$ (5.34)

and setting

$u_{\star}=\lambda-\mu+{\varepsilon},$ (5.35)

the expression (5.27) translates to

${\varepsilon}\approx-\ln\left(1+\frac{{\varepsilon}-\mu}{\lambda}\right).$
(5.36)

This equation can be solved by iteration, yielding the expansion

${\varepsilon}\approx\frac{\mu}{\lambda}+\frac{\mu(\mu-2)}{2\lambda^{2}}+\frac{\mu(2\mu^{2}-9\mu+6)}{6\lambda^{3}}+\cdots$
(5.37)

Inserting (5.35), (5.37) into (5.28), (5.29), we obtain the expansions

$\displaystyle\rho_{\star}\approx
1-\frac{1}{\lambda}-\frac{\mu-1}{\lambda^{2}}-\frac{\mu^{2}-3\mu+1}{\lambda^{3}}-\frac{2\mu^{3}-11\mu^{2}+12\mu-2}{2\lambda^{4}}+\cdots,$
(5.38)
$S_{\star}\approx\frac{1}{k}\left(\lambda-\mu+\frac{\mu}{\lambda}+\frac{\mu(\mu-2)}{2\lambda^{2}}+\frac{\mu(2\mu^{2}-9\mu+6)}{6\lambda^{3}}+\cdots\right).$
(5.39)

All terms of the above asymptotic expansions can be trusted. The present
approach indeed neglects corrections of relative order $1/k$, which are
exponentially small in $\lambda$. Conversely, (5.27), (5.28) and (5.29) can be
thought of as all-order resummations of the above asymptotic expansions.

The shape of the entropy $S(\rho)$ in the vicinity of its maximum $S_{\star}$
can be investigated by simplifying the expression (5.26) in the regime where
$1-\rho$ is proportional to $1/\lambda$. This scaling is suggested by the
estimate (5.32) of $\rho_{\star}$. Introducing the variable

$\xi=\lambda(1-\rho),$ (5.40)

we recover from (5.26) the first two terms of the expansion (5.39) of
$S_{\star}$, as well as a scaling expression for the large-deviation function
$\Sigma(\rho)=S_{*}-S(\rho)$ to leading order in $\lambda$, namely

$\Sigma(\rho)\approx\frac{\Phi(\xi)}{k},$ (5.41)

where the scaling function reads

$\Phi(\xi)=\xi-1-\ln\xi.$ (5.42)

This function vanishes for $\xi_{*}=\lambda(1-\rho_{\star})=1$, in agreement
with (5.32) and with the first two terms of (5.38), around which it behaves
quadratically as

$\Phi(\xi)\approx\frac{(\xi-1)^{2}}{2},$ (5.43)

so that

$\Sigma(\rho)\approx\frac{\lambda^{2}(\rho-\rho_{\star})^{2}}{2k},$ (5.44)

in agreement with (3.18), and with (5.50) to leading order in $\lambda$.

The behavior of the cumulant amplitudes $c_{n}$ can also be investigated along
the same lines. Setting

$\beta=\frac{\sigma}{k},\qquad\hbox{i.e.,}\quad
x=\exp\left(\frac{\sigma}{k}\right),$ (5.45)

where the parameter $\sigma$ is independent of $k$, (5.23) becomes

$u(x)\rme^{u(x)}\approx k\rme^{\sigma},$ (5.46)

hence

$u(x)\approx W(k\rme^{\sigma}).$ (5.47)

The configurational free energy introduced in (3.4) reads

$F(\beta)\approx\frac{u(x)-u_{\star}}{k}.$ (5.48)

Expanding $u(x)$ in powers of $\sigma$ and identifying coefficients with
(3.5), we obtain

$c_{1}=\rho_{\star}\approx\frac{u_{\star}}{u_{\star}+1}$ (5.49)

(see (5.28), (5.32), (5.38)), as well as

$\displaystyle c_{2}$ $\displaystyle\approx$
$\displaystyle\frac{ku_{\star}}{(u_{\star}+1)^{3}}$ (5.50)
$\displaystyle\approx$
$\displaystyle\frac{k}{\lambda^{2}}\left(1+\frac{2\mu-3}{\lambda}+\frac{3\mu^{2}-11\mu+6}{\lambda^{2}}+\cdots\right),$
$\displaystyle c_{3}$ $\displaystyle\approx$
$\displaystyle-\frac{k^{2}u_{\star}(2u_{\star}-1)}{(u_{\star}+1)^{5}}$ (5.51)
$\displaystyle\approx$
$\displaystyle-\frac{2k^{2}}{\lambda^{3}}\left(1+\frac{6\mu-11}{2\lambda}+\frac{12\mu^{2}-50\mu+35}{2\lambda^{2}}+\cdots\right),$

and so on. To leading order in $\lambda$, all cumulant amplitudes scale as

$c_{n}-\delta_{n1}\approx(-1)^{n}(n-1)!\frac{k^{n-1}}{\lambda^{n}}.$ (5.52)

Inserting the above leading-order estimate into (3.5) and summing the series,
we obtain a scaling formula for the configurational free energy, namely

$F(\beta)\approx\beta-\frac{1}{k}\,\ln\frac{\lambda+k\beta}{\lambda}.$ (5.53)

The expression (3.15) then yields

$\rho\approx 1-\frac{1}{\lambda+k\beta}.$ (5.54)

Using (3.20), (3.21), we recover the scaling expression (5.41), (5.42) for the
large-deviation function $\Sigma(\rho)$.

Let us now comment and illustrate the above results. The most striking feature
of the large-$k$ regime is the occurrence of logarithms in the leading-order
estimates (5.32) and (5.33). These logarithmic corrections originate in the
following peculiar feature of the large-$k$ regime. The length of any cluster
of empty sites between two sequences of $k$-mers may take a very large number
$(k-1)$ of different values. This proliferation of the possible numbers of
consecutive empty sites affects the renewal formalism as follows. In the naive
scaling regime where $x^{k}$ and $z^{k}$ are of order unity, $I(xz)$ remains
of order unity, whereas $J(z)$ grows proportionally to $k$. This fundamental
dissymmetry between occupied and empty sites manifests itself by the presence
of a factor $k$ in the right-hand side of (5.27), whose solution scales as
(5.31). It is therefore at the origin of the observed logarithmic corrections
to scaling. The slow convergence of the most probable density $\rho_{\star}$
to the largest possible density $\rho_{\rm max}=1$ is the foremost consequence
of this mechanism.

Figure 3 shows plots of the configurational entropy $S(\rho)$, multiplied by
$k$, against the particle density $\rho$ for a broad range of values of $k$,
equally spaced on a logarithmic scale. The heights of the maxima $kS_{\star}$
(black symbols) are roughly equidistant, in agreement with the prediction
(5.33). For modest values of $k$, the entropy curves are roughly symmetric.
Accordingly, the most probable densities $\rho_{\star}$ are not far from the
middle of the interval of values of $\rho$, i.e., $\rho_{\rm mid}=3/4$. The
asymptotic prediction (5.32) for the most probable density $\rho_{\star}$
implies that the entropy curves eventually become very asymmetric for very
large values of $k$, with their maxima approaching the upper edge of the
interval at logarithmic speed. This asymmetry is indeed observed to set in
very slowly.

Figure 3: Configurational entropy $S(\rho)$ of the $k$-mer problem, multiplied
by $k$ and plotted against particle density $\rho$. Bottom to top: $k=10$, 20,
40, 80, 160, 320, 640 and 1280. Symbols: coordinates
$(\rho_{\star},kS_{\star})$ of the maxima of the entropy curves.

Figure 4 shows the maximal entropy $S_{\star}$, multiplied by $k$ and plotted
against $\ln k$. The values of $kS_{\star}$ (red) are compared to the all-
order large-$k$ estimate $u_{\star}$ (see (5.29), (5.30)) (blue). The latter
estimate converges very fast to the data, in agreement with the expectation
that this convergence is in $1/k$, roughly speaking, i.e., exponentially fast
at the scale of the plot.

Figure 4: Maximal configurational entropy $S_{\star}$ of statistical ensemble
of blocked $k$-mer configurations, multiplied by $k$ and plotted against $\ln
k$. Red curve: values of $kS_{\star}$ for finite $k$. Blue curve: large-$k$
estimate (see (5.29), (5.30)).

Figure 5 shows the most probable density $\rho_{\star}$ plotted against $\ln
k$. This density (red) exhibits a non-monotonic dependence on $k$. More
details will be given in the discussion of figure 6. The data are compared to
the all-order large-$k$ estimate (see (5.28), (5.30)) (blue). The accuracy of
the latter estimate is far less impressive than for $S_{\star}$ (see figure
4).

Figure 5: Most probable density $\rho_{\star}$ of statistical ensemble of
blocked $k$-mer configurations, against $\ln k$. Red curve: values of
$\rho_{\star}$ for finite $k$. Blue curve: large-$k$ estimate (see (5.28),
(5.30)). Figure 6: Particle densities of blocked $k$-mer configurations,
against $k$. Red curve: most probable density $\rho_{\star}$ of the
statistical ensemble. Blue curve: dynamical density $\rho_{\infty}$ (see
(5.55)). Horizontal dashed line: Rényi parking constant $R$ (see (5.57)).

Figure 6 presents a comparison between the a priori (or static) density of the
problem of $k$-mers, i.e., the most probable density $\rho_{\star}$ of the
statistical ensemble of blocked configurations investigated above (red), and
the final (or dynamical) density $\rho_{\infty}$ of the blocked configurations
reached by the deposition dynamics starting from an empty lattice (blue).

The dynamical density is exactly known for all values of $k$ [60, 61, 62, 35]:

$\rho_{\infty}=k\int_{0}^{1}\exp\Biggl{(}-2\sum_{j=1}^{k-1}\frac{1-y^{j}}{j}\Biggr{)}\,{\rm
d}y.$ (5.55)

For $k=2$, we recover the result by Flory for the dimer deposition problem
[63]:

$\rho_{\infty}=1-\rme^{-2}\approx 0.864664.$ (5.56)

The modest range $(k\leq 40)$ used in figure 6 allows a good visibility of the
following traits. The dynamical density $\rho_{\infty}$ is a monotonically
decreasing function of $k$, whereas the static density $\rho_{\star}$ exhibits
a non-monotonic dependence on $k$, reaching its minimum $\rho_{\star}\approx
0.758316$ for $k=9$, as already noticed in [34]. Both particle densities cross
between 15 and 16. As a consequence, for $k\leq 15$ we have
$\rho_{\infty}>\rho_{\star}$, as in most common RSA and related models [37],
whereas the reverse inequality $\rho_{\infty}<\rho_{\star}$ holds for $k\geq
16$. For large $k$, the dynamical density converges to the celebrated Rényi
parking constant [64]:

$R=\int_{0}^{\infty}\exp\left(-2\int_{0}^{y}\frac{1-\rme^{-x}}{x}\,{\rm
d}x\right){\rm d}y\approx 0.747597,$ (5.57)

describing the final density of the blocked configurations for the RSA of unit
intervals on the continuous line. The corrections to the above limit have been
shown [61] to be given by a power series in inverse powers of $k$:

$\rho_{\infty}=R+\frac{R_{1}}{k}+\frac{R_{2}}{k^{2}}+\cdots,$ (5.58)

with $R_{1}\approx 0.216181$, $R_{2}\approx 0.036255$. The convergence of
$\rho_{\infty}$ to its limit $R$ (horizontal dashed line) is much faster than
the logarithmically slow convergence of $\rho_{\star}$ to the limit $\rho_{\rm
max}=1$.

##  6 Rydberg atoms

This section is devoted to configurations of assemblies of trapped ultracold
Rydberg atoms. In the simple one-dimensional setting described in the
introduction, Rydberg atoms are viewed as particles occupying the sites of a
one-dimensional optical lattice, with a constraint stemming from the Rydberg
blockade, namely that each occupied site must have at least $b$ empty sites on
either side. The integer $b\geq 1$ is referred to as the blockade range of the
model. Our aim is to investigate the ensemble of all blocked configurations,
where no single atom can be inserted any more [35, 50].

A blocked configuration consists of isolated occupied sites (the Rydberg
atoms) separated by clusters of empty sites whose length is at least $b$, in
order to obey the blockade constraint, and at most $2b$, since an extra
Rydberg atom could be inserted in the middle of an empty range of size $2b+1$.
On a finite sample with open boundary conditions, there can be at most $b$
empty sites on the left of the first occupied one and at most $b$ empty sites
on the right of the last occupied one. Blocked configurations of Rydberg atoms
can therefore be described in terms of independent clusters. Within the
renewal approach of section 2, clusters of occupied and empty sites
respectively correspond to ${\cal I}=\\{1\\}$ and ${\cal
J}=\\{b,b+1,\dots,2b\\}$. The renewal approach must however be complemented in
order to take boundary conditions into account, namely the presence of empty
sites near both endpoints, whose numbers belong to the set ${\cal
B}=\\{0,1,\dots,b\\}$. The associated generating series read

$I(z)=z,\qquad J(z)=\frac{z^{b}(1-z^{b+1})}{1-z},\qquad
B(z)=\frac{1-z^{b+1}}{1-z}.$ (6.1)

The formula (2.8) becomes

$\displaystyle{\cal N}(z)$ $\displaystyle=$ $\displaystyle
1+B(z)I(z)B(z)+B(z)I(z)J(z)I(z)B(z)+\cdots$ (6.2) $\displaystyle=$
$\displaystyle\frac{1+I(z)(B(z)^{2}-J(z))}{1-I(z)J(z)}.$

Similarly, the formula (2.15) becomes

$Z(z,x)=\frac{1+I(xz)(B(z)^{2}-J(z))}{1-I(xz)J(z)}.$ (6.3)

Using (6.1), the expressions (6.2) and (6.3) read explicitly

$\displaystyle{\cal
N}(z)=\frac{1-z+z^{2}-z^{b+1}-z^{b+2}+z^{2b+2}}{(1-z)(1-z-z^{b+1}+z^{2b+2})},$
(6.4) $\displaystyle
Z(z,x)=\frac{1+(x-2)z+z^{2}-xz^{b+1}-xz^{b+2}+xz^{2b+2}}{(1-z)(1-z-xz^{b+1}+xz^{2b+2})}.$
(6.5)

These rational expressions are not singular at $z=1$, so that their
denominators actually read

$\displaystyle D(z)=1-z-z^{b+1}+z^{2b+2},$ $\displaystyle
D(z,x)=1-z-xz^{b+1}+xz^{2b+2}.$ (6.6)

These denominators do not depend on the specific boundary conditions. This is
to be expected, as they encode the properties of the system in the
thermodynamic limit. They can be mapped onto the denominators of the $k$-mer
problem (see (5.4)) by setting

$k=b+1,$ (6.7)

and changing $x$ into $x^{k}$.

Figure 2 (see section 5) demonstrates the equivalence underlying the above
observation at the level of single configurations. A Rydberg atom followed by
$b$ empty sites (to its right) can be mapped onto a $k$-mer, where $b$ and $k$
are related by (6.7). The numbers $M_{\rm RA}$ of Rydberg atoms and $M$ of
particles in the $k$-mer problem, and the corresponding densities $\rho_{\rm
RA}$ and $\rho$, are therefore related by

$M_{\rm RA}=\frac{M}{k},\qquad\rho_{\rm RA}=\frac{\rho}{k}.$ (6.8)

The mapping between $k$-mers and Rydberg atoms with blockade range $b$ is
however not unique. For instance, a $k$-mer can equally well represent a
Rydberg atom preceded by $b$ empty sites (to its left). As a consequence of
this non-uniqueness, the equivalence between both models does not exactly hold
on finite systems with prescribed boundary conditions. This explains why the
denominators (6.6) and (5.4) are simply related to each other, as observed
above, whereas the full generating series (6.4), (6.5) are not simply related
to (5.2), (5.3).

All results derived in section 5 concerning the $k$-mer problem in the
thermodynamic limit apply mutatis mutandis to blocked configurations of
Rydberg atoms on the formally infinite chain. Hereafter we focus our attention
onto two quantities which are more specific to the latter problem.

The first observable of interest is the mean distance $\langle B\rangle$
between successive Rydberg atoms along the chain, measured in lattice
spacings. In the statistical ensemble of blocked configurations, this mean
distance reads

$\langle B\rangle=\frac{1}{(\rho_{\rm RA})_{\star}}=\frac{k}{\rho_{\star}},$
(6.9)

where quantities entering the rightmost side pertain to the $k$-mer problem,
studied in section 5. The mean interatomic distance $\langle B\rangle$ only
depends on the blockade range $b$. It is given in table 1 up to $b=10$, and
plotted against $b$ in figure 7 up to $b=40$. Black straight lines show the
extremal values $B_{\rm min}=b+1$ and $B_{\rm max}=2b+1$. Actual values of
$\langle B\rangle$ (red line with symbols) are compared to the large-$k$
estimate for the ratio $k/\rho_{\star}$ (see (5.28), (5.30)) (blue line). The
latter estimate has the asymptotic expansion (see (5.38))

$\langle
B\rangle=b\left(1+\frac{1}{\lambda}+\frac{\mu}{\lambda^{2}}+\frac{\mu(\mu-1)}{\lambda^{3}}+\cdots\right),$
(6.10)

with

$\lambda=\ln b,\qquad\mu=\ln\lambda=\ln\ln b,$ (6.11)

implying that $\langle B\rangle\approx b(1+1/\ln b)$ is hardly larger than
$B_{\rm min}\approx b$ at large $b$. The growth of $\langle B\rangle$ is
already rather well represented by the above estimate for the modest range of
$b$ shown in figure 7.

$\begin{array}[]{|c|c|c|}\hline\cr b&\langle B\rangle&Q\\\ \hline\cr
1&\;2.430159&-\,0.958493\\\ 2&\;3.814962&-\,0.955953\\\
3&\;5.181490&-\,0.955998\\\ 4&\;6.535473&-\,0.956436\\\
5&\;7.879669&-\,0.956919\\\ 6&\;9.215803&-\,0.957378\\\
7&10.545079&-\,0.957798\\\ 8&11.868394&-\,0.958181\\\
9&13.186446&-\,0.958531\\\ 10&14.499793&-\,0.958852\\\ \hline\cr\end{array}$
Table 1:  Mean interatomic distance $\langle B\rangle$ (see (6.9)) and Mandel
$Q$ parameter (see (6.13)) in the statistical ensemble of blocked
configurations of Rydberg atoms with blockade range $b$, up to $b=10$. Figure
7: Mean interatomic distance $\langle B\rangle$ (see (6.9)) of blocked
configurations of Rydberg atoms, against blockade range $b$. Red line with
symbols: values of $\langle B\rangle$. Blue line: large-$k$ estimate (see
(5.28), (5.30)). Black lines: extremal values $B_{\rm min}=b+1$ and $B_{\rm
max}=2b+1$.

The second observable of interest is the so-called Mandel $Q$ parameter [65]:

$Q=\frac{\langle M_{\rm RA}^{2}\rangle_{c}}{\langle M_{\rm RA}\rangle}-1.$
(6.12)

This parameter is commonly used in quantum optics and atomic physics. It
provides a measure of the deviation with respect to a Poissonian distribution,
for which $Q=0$. In the present case, the Mandel $Q$ parameter has a well-
defined value in the thermodynamic limit, which only depends on $b$, namely
(see (3.7))

$Q=\frac{c_{2}}{kc_{1}}-1.$ (6.13)

Quantities in the right-hand side again pertain to the $k$-mer problem,
studied in section 5. The above $Q$ parameter is given in table 1 up to
$b=10$, and plotted against $b$ in figure 8 up to $b=40$. It turns out that
$Q$ is always near $Q_{\rm min}=-1$, and has a very weak non-monotonic
dependence on $b$, with a maximum at $b=2$. This observation is in qualitative
agreement with various experiments on Rydberg atoms, where rather large
negative values of $Q$ have been reported, testifying strongly sub-Poissonian
statistics [39, 41, 43, 44]. The asymptotic estimate of $Q$ at large $b$,
namely (see (5.35), (5.37), (5.49), (5.50))

$Q\approx\frac{1}{(u_{\star}+1)^{2}}-1=-\,1+\frac{1}{\lambda^{2}}+\frac{2(\mu-1)}{\lambda^{3}}+\cdots,$
(6.14)

exhibits a logarithmically slow convergence toward $Q_{\rm min}=-1$. The above
estimate is however too large (i.e., too far from $Q_{\rm min}$) to be visible
in figure 8. It is altogether of little practical use, except for extremely
large $b$.

Figure 8: Mandel $Q$ parameter (see (6.13)) of blocked configurations of
Rydberg atoms, against blockade range $b$.

##  7 Discussion

In this paper we have put forward an alternative method to investigate
statistical ensembles of constrained configurations of particles on the one-
dimensional lattice. The scope of this renewal approach is restricted to local
constraints which are expressible in terms of the lengths of clusters of
occupied and empty sites. Within this scope, the present renewal method is
more systematic and easier to implement than traditional approaches involving
either direct combinatorial reasoning or the transfer-matrix formalism. The
key formulas (2.8) and (2.15) are indeed explicit, given the sets ${\cal I}$
and ${\cal J}$ of permitted cluster lengths.

In the broad class of rational models, the complexity of a statistical
ensemble is measured by the degree $\Delta$ of the polynomial $D(z)$. In
particular, the numbers of configurations on finite lattices of length $N$
obey a linear recursion with constant integer coefficients, whose number of
terms is at most $\Delta+1$. The integer $\Delta$ is the analogue of the
dimension of the transfer matrix in the transfer-matrix approach summarized in
B. The renewal approach it however more straightforward, as the transfer-
matrix formalism requires both the choice of a relevant set of partial
partition functions and the explicit building of the corresponding transfer
matrix. Furthermore, the renewal approach extends to non-rational models,
which would require the construction of an infinite-dimensional transfer
operator.

The renewal approach has been illustrated in detail on the $k$-mer deposition
model and on assemblies of trapped Rydberg atoms with blockade range $b$. In
the latter case, the presence of specific boundary conditions led us to extend
the renewal approach and to generalize the formulas (2.8) and (2.15) to (6.2)
and (6.3). The statistical ensembles of blocked configurations of $k$-mers and
of Rydberg atoms are essentially equivalent to each other, with the
identification $k=b+1$. Their most remarkable common feature is the occurrence
of logarithmic corrections in the regime where $k$ or $b$ become large, whose
origin has been explained in detail. In the $k$-mer model, the most probable
density $\rho_{\star}$ approaches its maximal value $\rho_{\rm max}=1$ very
slowly, with a large correction scaling as $1/\ln k$. In the case of Rydberg
atoms, the Mandel $Q$ parameter is always very near its minimal value $Q_{\rm
min}=-1$, irrespective of the blockade range $b$. Its logarithmically slow
asymptotic convergence to $Q_{\rm min}$ is therefore unobservable, except for
irrealistically large $b$.

Finally, it would be desirable to extend either the present renewal method or
the transfer-matrix approach to more complex geometries besides the one-
dimensional case. In this context, regular trees seem to be the most promising
setting.

It is a pleasure for us to thank Tomislav Došlić, Mate Puljiz, Stjepan Šebek
and Josip Žubrinić for fruitful exchanges during the concomitant elaboration
of their preprint [50] and of the present work. PLK is grateful to IPhT Paris-
Saclay for excellent working conditions.

## Data availability statement

Data sharing not applicable to this article as no datasets were generated or
analyzed during the current study.

##  Appendix A Several species of particles

In this appendix we show that the renewal approach can be generalized to
models having several species of particles. We denote these species by
$a=1,\dots,A$. Each site of the infinite half-line is occupied by a particle
of some species. If empty sites (holes) are permitted, they are represented
for definiteness by the last species $(a=A)$.

We consider the statistical ensemble of configurations defined by the
constraints that the lengths of clusters of $a$-particles belong to some set
${\cal I}_{a}$, encoded in the generating series

$I_{a}(z)=\sum_{i\in{\cal I}_{a}}z^{i}.$ (1.1)

The model considered in section 2 corresponds to $A=2$, with $a=1$ and $a=2$
respectively corresponding to particles (occupied sites) and holes (empty
sites), so that ${\cal I}_{1}={\cal I}$, ${\cal I}_{2}={\cal J}$.

The generating series of the numbers of configurations,

${\cal N}(z)=\sum_{N\geq 0}{\cal N}_{N}z^{N},$ (1.2)

can be derived along the lines of (2.6)–(2.8). We have

${\cal N}(z)=1+\sum_{a=1}^{A}{\cal N}_{a}(z),$ (1.3)

with

${\cal N}_{a}(z)=I_{a}(z)\Bigl{(}1+\sum_{b\neq a}{\cal
N}_{b}(z)\Bigr{)}=I_{a}(z)({\cal N}(z)-I_{a}(z)),$ (1.4)

hence

${\cal N}_{a}(z)=\frac{I_{a}(z)}{1+I_{a}(z)}\,{\cal N}(z),$ (1.5)

and finally

${\cal N}(z)={\displaystyle{\displaystyle 1\over\displaystyle
1-\sum_{a=1}^{A}\frac{I_{a}(z)}{1+I_{a}(z)}}}.$ (1.6)

For $A=2$, we have

${\cal N}(z)=\frac{(1+I_{1}(z))(1+I_{2}(z))}{1-I_{1}(z)I_{2}(z)},$ (1.7)

in agreement with (2.8). For $A=3$, we have

$\displaystyle{\cal
N}(z)=\frac{(1+I_{1}(z))(1+I_{2}(z))(1+I_{3}(z))}{1-I_{1}(z)I_{2}(z)-I_{1}(z)I_{3}(z)-I_{2}(z)I_{3}(z)-2I_{1}(z)I_{2}(z)I_{3}(z)},$

and so on.

The generating series of the numbers ${\cal N}_{N,M_{1},\dots,M_{A}}$ of
configurations with given prescribed numbers $M_{a}$ of $a$-particles can be
derived along the same lines, by attributing a positive weight $x_{a}$ to each
$a$-particle. We have

$Z(z,x_{1},\dots,x_{A})={\displaystyle{\displaystyle 1\over\displaystyle
1-\sum_{a=1}^{A}\frac{I_{a}(x_{a}z)}{1+I_{a}(x_{a}z)}}}.$ (1.9)

The expressions (1.6) and (1.9) hold in full generality. In the case where all
generating series $I_{a}(z)$ are rational, the resulting series ${\cal N}(z)$
and $Z(z,x_{1},\dots,x_{A})$ are also rational functions of $z$ and of the
weights $x_{a}$.

The simplest ensemble in the rational class is again the flat one, where there
are no constraints at all on the cluster lengths. This generalizes the
ensemble considered in section 4.1. We have

$I_{a}(z)=\frac{z}{1-z}$ (1.10)

for all species $a$. The formula (1.6) reads

${\cal N}(z)=\frac{1}{1-Az},$ (1.11)

and so

${\cal N}_{N}=A^{N}.$ (1.12)

The formula (1.9) reads

$Z(z,x_{1},\dots,x_{A})={\displaystyle{\displaystyle 1\over\displaystyle
1-z\sum_{a=1}^{A}x_{a}}},$ (1.13)

and so

${\cal N}_{N,M_{1},\dots,M_{A}}={N\choose
M_{1},\dots,M_{A}}=\frac{N!}{\displaystyle{\prod_{a=1}^{A}M_{a}!}}$ (1.14)

is the multinomial coefficient, with the constraint $M_{1}+\cdots+M_{A}=N$.
The above results express that each site is independently occupied by a
particle of any species $a=1,\dots,A$.

##  Appendix B Transfer-matrix formalism

In this appendix we demonstrate the equivalence between the renewal approach
put forward in this work and the transfer-matrix approach, on the explicit
example of the ensemble where empty sites are isolated, investigated in
section 4.2.

The key point of the transfer-matrix formalism consists in introducing partial
partition functions, defined by assigning fixed values to the occupations of
the few rightmost sites, in such a way that these partition functions obey
closed linear recursions. In the present case, we introduce
$Z_{N}^{\bullet}(x)$ and $Z_{N}^{\circ}(x)$, defined by conditioning the
configurations on the state (occupied or empty) of the rightmost site. We have
then $Z_{N}(x)=Z_{N}^{\bullet}(x)+Z_{N}^{\circ}(x)$.

The constraint that empty sites are isolated implies that the partial
partition functions obey the recursion

$\pmatrix{Z_{N+1}^{\bullet}(x)\cr Z_{N+1}^{\circ}(x)}={\bf
T}(x)\pmatrix{Z_{N}^{\bullet}(x)\cr Z_{N}^{\circ}(x)},$ (2.1)

where ${\bf T}(x)$ is the $2\times 2$ transfer matrix

${\bf T}(x)=\pmatrix{x&x\cr 1&0}.$ (2.2)

The characteristic polynomial of ${\bf T}(x)$ reads

$P(\lambda,x)=\lambda^{2}-x\lambda-x,$ (2.3)

so that its eigenvalues are

$\lambda_{\pm}(x)=\frac{x\pm\sqrt{x(x+4)}}{2}.$ (2.4)

The largest eigenvalue of ${\bf T}(x)$ obeys

$\lambda_{+}(x)=\frac{1}{z_{0}(x)},$ (2.5)

where $z_{0}(x)$ is the nearest root of the denominator $D(z,x)$ (see (3.1)),
which enters the analysis of the thermodynamic limit.

The initial conditions to the recursion (2.1) read $Z_{1}^{\bullet}(x)=x$ and
$Z_{1}^{\circ}(x)=1$, as there is a single configuration of each type
(${\bullet}$ and ${\circ}$). These conditions translate to
$Z_{0}^{\bullet}(x)=1$ and $Z_{0}^{\circ}(x)=0$. The partial generating series
$Z^{\bullet}(z,x)$ and $Z^{\circ}(z,x)$, defined in analogy with (2.13), are
therefore given by

$\pmatrix{Z^{\bullet}(z,x)\cr Z^{\circ}(z,x)}=(1-z{\bf
T}(x))^{-1}\pmatrix{1\cr 0}.$ (2.6)

We have

$(1-z{\bf T}(x))^{-1}=\frac{1}{1-xz-xz^{2}}\pmatrix{1&xz\cr z&1-xz},$ (2.7)

and so

$Z^{\bullet}(z,x)=\frac{1}{1-xz-xz^{2}},\qquad Z^{\circ}(z,x)=\frac{z}{1-xz-
xz^{2}},$ (2.8)

and finally

$Z(z,x)=\frac{1+z}{1-xz-xz^{2}},$ (2.9)

in agreement with (4.20).

Setting $x=1$ in (2.8), we obtain

${\cal N}^{\bullet}(z)=\frac{1}{1-z-z^{2}},\qquad{\cal
N}^{\circ}(z)=\frac{z}{1-z-z^{2}},$ (2.10)

and so

${\cal N}_{N}^{\bullet}=F_{N+1},\qquad{\cal N}_{N}^{\circ}=F_{N},$ (2.11)

where $F_{n}$ are the Fibonacci numbers (see (4.18)), and finally

${\cal N}_{N}=F_{N+2},$ (2.12)

in agreement with (4.19).

The expression (2.6) implies that the denominator $D(z,x)$ entering (2.7) and
(2.8) is proportional to the characteristic polynomial $P(\lambda,x)$ for
$\lambda=1/z$. This property is fully general. It implies that the degree
$\Delta$ of $D(z,x)$ coincides with the dimension of the transfer matrix ${\bf
T}(x)$. It also yields the identity (2.5).

## References

## References

  * [1] Thouless D J, Anderson P W and Palmer R G 1977 Phil. Mag. 35 593–601
  * [2] Kirkpatrick S and Sherrington D 1977 Phys. Rev. B 17 4384–4403
  * [3] Mézard M, Parisi G and Virasoro M A 1986 Spin Glass Theory and Beyond (Singapore: World Scientific)
  * [4] Götze W and Sjögren L 1992 Rep. Prog. Phys. 55 241–376
  * [5] Biroli G and Monasson R 2000 Europhys. Lett. 50 155–161
  * [6] Debenedetti P G and Stillinger F H 2001 Nature 410 259–267
  * [7] Berthier L and Biroli G 2011 Rev. Mod. Phys. 83 587–645
  * [8] Jäckle J 1981 Phil. Mag. 44 533–545
  * [9] Palmer R G 1982 Adv. Phys. 31 669–735
  * [10] Cornell S J, Kaski K and Stinchcombe R B 1991 Phys. Rev. B 44 12263–12274
  * [11] De Smedt G, Godrèche C and Luck J M 2003 Eur. Phys. J. B 32 215–225
  * [12] Derrida B and Gardner E 1986 J. Phys. (France) 47 959–965
  * [13] Masui S, Southern B W and Jacobs A E 1989 Phys. Rev. B 39 6925–6933
  * [14] Fredrickson G H and Andersen H C 1984 Phys. Rev. Lett. 53 1244–1247
  * [15] Jäckle J and Eisinger S 1991 Z. Phys. B 84 115–124
  * [16] Sollich P and Evans M R 1999 Phys. Rev. Lett. 83 3238–3241
  * [17] Crisanti A, Ritort F, Rocco A and Sellitto M 2000 J. Chem. Phys. 113 10615–10634
  * [18] Dean D S and Lefèvre A 2001 Phys. Rev. Lett. 86 5639–5642
  * [19] Dean D S and Lefèvre A 2001 Phys. Rev. E 64 046110
  * [20] Lefèvre A and Dean D S 2001 J. Phys. A: Math. Gen. 34 L213–L220
  * [21] Prados A and Brey J J 2001 J. Phys. A: Math. Gen. 34 L453–L459
  * [22] De Smedt G, Godrèche C and Luck J M 2002 Eur. Phys. J. B 27 363–380
  * [23] Palmer R G and Frisch H L 1985 J. Stat. Phys. 38 867–872
  * [24] Elskens Y and Frisch H L 1987 J. Stat. Phys. 48 1243–1248
  * [25] Privman V 1992 Phys. Rev. Lett. 69 3686–3688
  * [26] Lin J C and Taylor P L 1993 Phys. Rev. E 48 4305–4308
  * [27] Krapivsky P L 1994 J. Stat. Phys. 74 1211–1225
  * [28] Evans J W 1989 Rev. Mod. Phys. 65 1281–1329
  * [29] Talbot J, Tarjus G, Van Tassel P R and Viot P 2000 Colloids Surfaces A 165 287–324
  * [30] Krapivsky P L, Redner S and Ben-Naim E 2010 A Kinetic View of Statistical Physics (Cambridge: Cambridge University Press)
  * [31] Dean D S 2000 Eur. Phys. J. B 15 493–498
  * [32] Lefèvre A and Dean D S 2001 Eur. Phys. J. B 21 121–128
  * [33] Došlić T and Zubac I 2016 Ars Math. Contemp. 11 255–276
  * [34] Došlić T 2019 Ars Math. Contemp. 17 79–88
  * [35] Krapivsky P L 2020 Phys. Rev. E 102 062108
  * [36] Godrèche C and Luck J M 2005 J. Phys.: Condens. Matter 17 S2573–S2590
  * [37] Krapivsky P L and Luck J M 2022 Jamming and metastability in one dimension: from the kinetically constrained Ising chain to the Riviera model Preprint arXiv:2211.12815
  * [38] Baule A, Morone F, Herrmann H J and Makse H A 2018 Rev. Mod. Phys. 90 015006
  * [39] Saffman M, Walker T G and Mølmer K 2010 Rev. Mod. Phys. 82 2313–2363
  * [40] Jaksch D, Cirac J I, Zoller P, Rolston S L, Côté R and Lukin M D 2000 Phys. Rev. Lett. 85 2208–2211
  * [41] Liebisch T C, Reinhard A, Berman P R and Raithel G 2005 Phys. Rev. Lett. 95 253002
  * [42] Pohl T, Demler E and Lukin M D 2010 Phys. Rev. Lett. 104 043002
  * [43] Viteau M, Huillery P, Bason M G, Malossi N, Ciampini D, Morsch O, Arimondo E, Comparat D and Pillet P 2012 Phys. Rev. Lett. 109 053002
  * [44] Hofmann C S, Gn̈ter G, Schempp H, de Saint-Vincent M R, Gärttner M, Evers J, Whitlock S and Weidemüller M 2013 Phys. Rev. Lett. 110 203601
  * [45] Bernien H, Schwartz S, Keesling A, Levine H, Omran A, Pichler H, Choi S, Zibrov A S, Endres M, Greiner M, Vuletić V and Lukin M D 2017 Nature 551 579–598
  * [46] Sanders J, van Bijnen R, Vredenbregt E and Kokkelmans S 2014 Phys. Rev. Lett. 112 163001
  * [47] Lawler E L, Lenstra J K and Rinnooy Kan A H G 1980 SIAM J. Computing 9 558–565
  * [48] Ebadi S, Keesling A, Cain M, Wang T T, Levine H, Bluvstein D, Semeghini G, Omran A, Liu J G, Samajdar R, Luo X Z, Nash B, Gao X, Barak B, Farhi E, Sachdev S, Gemelke N, Zhou L, Choi S, Pichler H, Wang S T, Greiner M, Vuletić V and Lukin M D 2022 Science 376 1209–1215
  * [49] Nguyen M T, Liu J G, Wurtz J, Lukin M D, Wang S T and Pichler H 2023 PRX Quantum 4 010316
  * [50] Došlić T, Puljiz M, Šebek S and Žubrinić J 2023 Complexity function of jammed configurations of Rydberg atoms Preprint arXiv:2302.08791
  * [51] Cox D R 1962 Renewal Theory (London: Methuen)
  * [52] Cox D R and Miller H D 1965 The Theory of Stochastic Processes (London: Chapman & Hall)
  * [53] Feller W 1957, 1971 An Introduction to Probability Theory and its Applications 2nd ed (New York: Wiley)
  * [54] Godrèche C and Luck J M 2001 J. Stat. Phys. 104 489–524
  * [55] Schulz J H P, Barkai E and Metzler R 2014 Phys. Rev. X 4 011028
  * [56] Krapivsky P L 2013 J. Stat. Mech. P06012
  * [57] Godfrey M J and Moore M A 2018 Phys. Rev. Lett. 121 075503
  * [58] Zhang Y X, Godfrey M J and Moore M A 2020 Phys. Rev. E 102 042614
  * [59] The OEIS Foundation Inc 2011 The On-Line Encyclopedia of Integer Sequences
  * [60] González J J, Hemmer P C and Høye J S 1974 Chem. Phys. 3 228–238
  * [61] Bartelt M C, Evans J W and Glasser M L 1993 J. Chem. Phys. 99 1438–1439
  * [62] Bonnier B, Boyer D and Viot P 1994 J. Phys. A: Math. Gen. 27 3671–3682
  * [63] Flory P J 1939 J. Am. Chem. Soc. 61 1518–1521
  * [64] Rényi A 1958 Publ. Math. Inst. Hung. Acad. Sci. 3 109–127
  * [65] Mandel L 1979 Optics Lett. 4 205–207