Large Deviations in Random Sequential Adsorption

In a random sequential adsorption process, objects are deposited randomly, irreversibly, and sequentially; if an attempt to add an object results in an overlap with previously deposited objects, the attempt is discarded. The process continues until the system reaches a jammed state when no further additions are possible. Exact analyses have been performed only in one-dimensional models, and the average number of absorbed particles has been computed in a few solvable situations. We analyze a process in which landing on an empty site is allowed when at least $b$ neighboring sites on the left and the right are empty. For the minimal model ($b=1$), we compute the full counting statistics of the occupation number.


I. INTRODUCTION
Random sequential adsorption (RSA) is a toy model mimicking the irreversible deposition of suspended particles onto substrates. The RSA model postulates that the deposition events are random: If the new particle is sufficiently far away from already deposited ones, it sticks to the substrate; otherwise, the deposition event is discarded. In the two-dimensional setting, the RSA models have been applied to modeling chemisorption on singlecrystal surfaces and adsorption in colloidal systems [1][2][3][4][5]. There are also applications in nanotechnology, see [6][7][8][9]. The RSA models have been also used in high dimensions, e.g. in the context of packing problems [10].
The first RSA model with adsorption of dimers was introduced by Flory for the description of reactions along a long polymer chain [11]. Another beautiful RSA model with adsorption on a continuous one-dimensional line was introduced by Rényi [12] as a toy model of car parking. The RSA type of models has been also used in several other one-dimensional settings, e.g., in modeling polymer translocation [13,14] and describing zero-temperature dynamics of Ising chains [15][16][17].
The RSA models mimic the generation Rydberg excitations. In experiments, a laser excites ultra-cold atoms on a lattice from the ground state to a Rydberg state (see e.g. [18][19][20][21]). Interactions between Rydberg atoms cause the blockage forbidding the excitation of atoms sufficiently close to a Rydberg atom. When the radiative decay of the Rydberg atoms can be ignored, this RSA model mimics certain features of the excitation process [22], although it disregards features like the non-ergodic quantum dynamics of Rydberg-blockaded chains (see [23][24][25][26] and references therein).
We investigate a model in which particles are absorbed randomly and irreversibly onto an interval with L sites. We assume that each particle attaches to a single site. The blockage effect is modeled by the requirement that adjacent particles are separated by at least b vacant sites. In experimental realizations with Rydberg atoms where excitation plays the role of deposition, these systems typically occupy L ∼ 50 lattice sites. For such relatively small systems, fluctuations are significant and they can be probed experimentally [21,27]. The minimal model with blockage radius b = 1 is especially popular in the realm of laser-driven Rydberg lattice gases [23][24][25][26]28].
In Sec. II, we compute the average occupation number and a few other basic properties of the minimal model. The average occupation number was already established by Flory in a mathematically isomorphic model [11], our goal is to outline the tools which we employ later. The minimal model is further studied in Sec. III where we compute the full counting statistics of the occupation number. In the general case when the blockage radius is arbitrary (Sec. IV), the average occupation number is still easily computable; the generating function encoding all the cumulants satisfies a Riccati equation which appears unsolvable for any b ≥ 2. Cumulants can still be extracted one by one via more and more cumbersome calculations, so we only determine the variance (the computations are relegated to Appendix A). The extreme probabilities of maximally sparse and maximally dense jammed configurations are tractable for arbitrary b ≥ 1.

II. THE MINIMAL MODEL: AVERAGE PROPERTIES
The exclusion interaction between particles is modeled by requiring that the two sites surrounding an occupied site are empty. Thus there is the blockade effect as each absorbed particle forbids future adsorption into the nearest-neighbor sites. Eventually, the system reaches a jammed state. For instance, is a jammed configuration with N = 9 occupied sites on the interval of length L = 19. Locally, jammed states vary from realization to realization. More global features of jammed states become deterministic in the thermodynamic limit, L → ∞; e.g., the fraction of short segments • • • is 1−3e −2 , while the fraction of the long segments • • • • is 3e −2 . Since we study fluctuations, so we must analyze finite systems. We consider open intervals that are relevant in the context of Rydberg atoms; the extension to rings is straightforward.
A. The average number of occupied sites Here we outline the computation of the average number A L = N of occupied sites on an open interval of length L. We employ an approach essentially developed by Flory [11], see also a textbook [29]; our analysis (Sec. III) of the cumulant generating function will proceed along similar lines.
For small L, one can compute A L = N by hand. For instance, N = 1 when L = 1 and 2; for L = 4, one gets N = 2. For L = 3 and L ≥ 5, the total number N of absorbed particles varies from realization to realization, e.g. N = 1 (probability 1/3) or N = 2 (probability 2/3) when L = 3. Thus To compute A L for arbitrary L, suppose k is the landing site of the first particle. The intervals of lengths k − 2 and L − k − 1 on the left and right of the first deposited particle are subsequently filled independently. This key feature makes the one-dimensional situation tractable. For our model, we arrive at the recurrence Using the generating function we convert the recurrence (3) into a differential equation Solving this linear inhomogeneous differential equation subject to the initial condition A(0) = 0 we obtain from which Using (7) one can extract the large L behavior: B. Behavior near the boundary In the L → ∞ limit the jamming density is When L 1, the probability that a site in the bulk is occupied is very close to (9). Near the boundary the densities are different.
Let us first compute the probability p L that the leftmost is occupied. For small L, one can compute p L by hand to yield etc. Generally, the probability p L satisfies the recurrence which is established similarly to the recurrence (3). Using the generating function we convert the recurrence (11) into a differential equation which is solved to yield Expanding P (x) we obtain In the L → ∞ limit, i.e. for the semi-infinite lattice, the left-most site is occupied with probability which substantially exceeds the probability (9) that a bulk site is occupied. The probability q L that the second site, viz. the site adjacent to the left-most site is occupied, is dual to the probability p L : for L ≥ 2. In particular The probability r L that the third site is occupied satisfies the recurrence Using the generating function we convert the recurrence (19) into a differential equation with P (x) given by (14). Solving (21) subject to R(0) = 0 we obtain from which In particular A longer calculation gives These results hint that with some positive rational A n , B n , C n , D n . Recalling that π ∞ = ρ jam , one gets

C. The total number of jammed states
The total number of jammed states J L satisfies an obvious recurrence The solution of this recurrence subject to the boundary conditions J 0 = J 1 = 1 and J 2 = 2 is encapsulated in the generating function In particular, the asymptotic behavior is where r is the real root of the cubic equation r 3 = r + 1 known as a plastic number. The Padovan sequence (26) is a cousin of the Fibonacci sequence, it arises in several applications, see e.g. [30,31].

III. THE MINIMAL MODEL: FULL COUNTING STATISTICS
One-dimensional RSA models are often tractable (see [1,2,29] for a review) and basic features like the jamming density have been probed analytically. For the minimal model with b = 1, we have shown (Sec. II) how to compute the jamming density, the behavior near the boundary, and the total number of jammed states. In this section we analyze fluctuations.

A. Full counting statistics
Consider an interval of length L. The RSA procedure brings the system into a jammed state. The total number N of absorbed particles fluctuates from realization to realization. Here we compute the cumulant generating function that encodes all the cumulants of N . Thus we want to compute the average where P (N, L) is the probability to have N particles in a jammed state. The standard relation then gives all the cumulants: the average N c = N , the variance N 2 c = N 2 − N 2 , etc. The function F (λ, L) ≡ e λN grows exponentially with L. The cumulant generating function encapsulates all cumulants: To determine F (λ, L) we proceed in the same way as in the derivation of the average and obtain a recurrence expressing that after the first deposition event, say at site k, the intervals on the left and the right are filled independently. (The one-dimensional nature of the problem is crucial for this property.) The recurrence (33) applies for all L ≥ 1 if we set We now introduce the generating function To recast (33) into an equation for the generating function we multiply (33) by Lx L−1 and sum over all L ≥ 1.
The left-hand side turns into The right-hand side becomes and using the boundary conditions (34) we simplify the double sum to and recast the recurrence (33) into a Riccati equation which turns out to be solvable. The solution of Eq. (36) subject to the initial condition Φ(λ, 0) = 1 reads where Λ ≡ e λ/2 . The generating function Φ(λ, x) has a simple pole at x = y = y(λ). Using (37) we find that the pole is implicitly determined by The cumulant generating function is plotted in Fig. 1. We already know the dominant exponential factor in F (λ, L) ∝ e LU (λ) . The exact result (37) allows one to find a pre-exponential factor. A straightforward calculation gives the residue of the simple pole of Φ(λ, x). We find when L 1. The cumulant generating function is implicitly defined through (38)- (39). Expanding U (λ) we recover already known value of the first cumulant: N = Lρ jam . In principle, one can determine an arbitrary cumulant. We haven't succeeded in finding an explicit general formula.
Here we merely list a few cumulants that are extracted by expanding U (λ) implicitly given by (38) The so-called Mandel Q parameter [32] indicates that the statistics is strongly sub-Poissonian in the present case. The ratios N n c / N of cumulants to the average are known as Fano factors [33]. Here are a few Fano factors

B. Extremal jammed states
Extremal jammed states are the states with the largest and the smallest number of occupied sites. Let us extract the probabilities of such states from the behavior of the cumulant generating function in the λ → ±∞ limits. An asymptotic analysis of (38) yields (see also Fig. 1) where we dropped the terms vanishing in the λ → ±∞ limits and denoted by u the positive root of the equation u tanh(u) = 1; numerically u = 1.19967864 . . .. Combining (40) and (44) we get To appreciate the first asymptotic in (45) we note that in the λ → −∞ limit the dominant contribution to the sum in Eq. (29) is provided by the jammed state with the smallest number of occupied sites. This jammed state has N min = (L+2)/3 particles explaining the dominant e λL/3 factor. The 3 −L/3 pre-factor gives the probability to end up in such jammed state.
In the λ → ∞ limit the dominant contribution to the sum (29) is provided by the jammed state with the largest number of occupied sites: We have N max = (L + 1)/2 and this explains the e λL/2 factor in (45). The u −L pre-factor is the probability to end up in the jammed state with the largest number of occupied sites. Thus the large deviation technique gives the asymptotic behaviors of the probability to reach the extremal jamming jammed states: The probabilities P (N min , L) and P (N max , L) can be also computed exactly as follows. Let us start with maximally dense jammed states (46b). The maximally dense state with N max = n particles may occur when L = 2n−1 or L = 2n. For concreteness, consider the first case. The probability µ n = P (n, 2n − 1) can be recurrently determined from The boundary conditions read Introducing the generating function we convert the recurrence (48) into a Riccati equation which is solved to yield Analyzing the divergence of the generating function when x → u 2 , we extract the large n asymptotic For maximally sparse jammed states (46a), say when L = 3n and N min = n, the probabilities ν n = P (n, 3n) satisfy the recurrence from which P (n, 3n) = 3 −n (55a) A similar but longer analysis gives two other series of probabilities of maximally sparse jammed states: P (n, 3n − 1) = 3n + 2 5 1 3 n−1 (55b) and P (n, 3n − 2) = 63n 2 + 45n + 8 350 Thus, in the realm of the RSA model, the defect-free arrays arise with exponentially small probabilities. The defect-free arrays (46a)-(46b) of Rb atoms excited to Rydberg states have been recently assembled experimentally by Bernien et al. [23].
One can verify that P (N, 1) = δ N,1 and P (N, 2) = δ N,1 . We now introduce the generating function This definition implies that Using (56)-(59) we obtain a differential equation for the generating function which is mathematically identical to Eq. (36). The solution of (60) subject to the boundary condition P(x, 0) = 1 is thus identical to (37) in different notation: Generally N lies within the bounds

IV. ARBITRARY BLOCKAGE RADIUS
In this section, we analyze the model with an arbitrary blockage radius and show that some characteristics remain analytically tractable. (In the context of ultra-cold Rydberg atoms, models with b > 1 are often relevant, see e.g. [34,35].)

A. The average number of occupied sites
The average number of occupied sites obeys This recurrence is applicable for all L ≥ 1 after setting A j = 0 for j ≤ 0. Using the generating function (4) we convert (63) into a differential equation Solving (64) subject to A(0) = 0 yields where we shortly write Using (65) we extract the density of occupied sites in the L → ∞ limit. For the minimal model we recover ρ 1 = (1 − e −2 )/2. The next jammed density ρ 2 also admits an explicit expression through standard special functions: is an error function. The following jammed densities are The maximally dense and maximally sparse jammed states provide obvious upper and lower bounds on the jammed density: These bounds hint that the limit exists and further suggest that 1 2 < C < 1. One can compute C using (67) and performing an asymptotic analysis. First we re-write (67) as We then write y = 1 − v/b and transform (71) into In the b → ∞ limit, we can use the asymptotic relation 1 − v b j → e −vj/b and replace summation over j by in- known as the Rényi's parking constant [12]. The efficiency of the coverage is measured by the ratio of the jamming density ρ b to the upper bound: The function F (λ, L) satisfies the recurrence which we recast into a differential equation for the generating function Φ = Φ(λ, x) defined by Eq. (35): This Riccati equation (74) appears solvable only for the minimal b = 1 model. It is still possible to determine the variance by analyzing ∂ λ Φ(λ, x) and ∂ 2 λ Φ(λ, x) at λ = 0. These functions satisfy equations which can be deduced from (74); solving these equation we determined the variance, see Appendix A.
We also note that the probability distribution P (N, L) satisfies a recurrence relation generalizing (56). Using the generating function (58) we recast the recurrence (75) into a Riccati equation which is mathematically identical to (74) and appears unsolvable when b = 2, 3, 4, . . ..

C. Extremal jammed states
The probabilities of the largest possible deviations, i.e. extremal jammed states, can be probed analytically using the same approach as in Sec. III B. We start with maximally dense jammed states and choose for concreteness such states with N max = n in the chains of length is an example of such maximally dense jammed state with N max = 6 and L = 16 for the model with the blockage radius is b = 2. The probabilities µ n = P (n, (b + 1)n − b) satisfy the recurrence and the boundary condition (49). The generating function (50) satisfies a Riccati equation Solving this Riccati equation subject to µ(0) = 1 yields Here I p is the modified Bessel function and we have used shorthand notation β = (1 + b) −1 and z = 2β √ bx. The denominator in (80) vanishes when x → y, where y = y(b) is found from This zero is simple and hence µ n ∼ [y(b)] −n . Re-writing in terms of the length of the chain, we arrive at The plot of u(b) is shown in Fig. 2 To extract more explicit results in the b → ∞ limit we recall that Since z = 2β by(b) 1 when b 1 limit, i.e. β 1, it suffices to keep the first three terms in (83). Using additionally Γ(β) β −1 we obtain in the leading order, from which we deduce This is asymptotically exact when b → ∞, but provides a reasonable approximation already for small b, see Fig. 2.
Maximally sparse jammed states are easier to analyze than maximally dense jammed states. For instance, for chains of length L = (2b + 1)n we have N min = n and the probabilities ν n = P (n, (2b + 1)n) to generate such states satisfy the recurrence from which ν n = (2b + 1) −n .

V. CONCLUSIONS
We have studied a class of one-dimensional random sequential adsorption (RSA) models parametrized by a positive integer b ≥ 1, the number of sites on the left and the right of an occupied site which must be empty. This class of models is tractable. For instance, we have determined the average number of occupied sites, the average densities near the boundaries, and the extreme probabilities to fall into maximally dense or minimally dense jammed states. We have mostly focused on large deviations and derived a Riccati equation for the cumulant generating function. This Riccati equation is solvable only for the minimal model, b = 1. When b ≥ 2, it is still possible to extract lower cumulants via perturbation analysis. In Appendix A we determined the variance. The complexity of such calculations quickly increases with the order of the cumulant, the computation of the variance is already rather involved. The probabilities of maximally sparse jammed states exhibit a simple dependence on b; in the most clean situation of chains of length L = (2b + 1)n when N min = n, the probabilities are (2b + 1) −n . The probabilities of maximally dense jammed states are more challenging: to extract the asymptotic behavior one must solve a Riccati equation for the generating function encoding these probabilities, this is possible for arbitrary b.
The RSA models are occasionally tractable on quasione-dimensional structures, e.g., on ladders. In particular, the RSA model with b = 1 has been studied, and the jamming density has been computed [36,37]. The derivation [36,37] of the jamming density is significantly more convoluted than in the purely one-dimensional setting, but perhaps the extreme probabilities would be easier to derive. The maximal density is again ρ max = 1 2 , while the minimal density on the ladder, ρ min = 1 4 , is smaller than in the one-dimensional setting.
The RSA models are often analytically tractable on lattices without loops, e.g. on the Bethe lattices [1] and some classes of infinite trees [38]. Large tree-like graphs, i.e. graphs with few loops, can be also tractable. For instance, the RSA model on the sparse Erdős-Rényi random graphs with b = 1 has been studied, see [39][40][41][42]. It would be interesting to determine the full counting statistics of the occupation number for this RSA model. which follows from F (0, L) ≡ 1, see (29), and the definition (36) of the generating function Φ(λ, x).
Differentiating Eq. (74) twice over λ, setting λ = 0 and using (A3) we find that B(x) obeys where we have used the shorthand notation Integrating (A4) and using B(0) = 0 we obtain We extract the first two cumulants by analyzing the singular behaviors of A(x) and B(x) near x = 1. Using Eq. (64) we find that A(x) has a pole of degree two Similarly using (A5)-(A7a) one finds that B(x) has a pole of degree three Extracting the amplitudes from the exact solution (A6) is not straightforward. One may try to insert (A7b) into (A4), with the right-hand side computed with the help of (A7a). This gives B 3 = 2ρ 2 b , but does not fix B 2 . To determine B 2 we combine (A6) and (A7b) to find To appreciate that the singular behaviors of A(x) and B(x) near x = 1 give the cumulants we start by recalling that the function Φ(λ, x) has a simple pole at y(λ), so when x → y(λ), with Y (0) = 1, y(0) = 1 (A11) as it follows e.g. from Eq. (A3). The average and the variance are found from the cumulant generating function U (λ) = − ln y(λ) to yield where (· · · ) = d(··· ) dλ λ=0 . Differentiating Eq. (A10) over λ, setting λ = 0 and using (A11) we find Comparing (A7a) and (A13a) we conclude that and thus re-derive that ρ b is indeed the jammed density. Comparing (A7b) and (A13b) and using (A14) we get Collecting these results we arrive at the final formula for the Mandel Q parameter. The jammed density ρ b admits an integral representation, Eq. (67), while J b given by (A9) requires taking the limit of an integral. (The naive replacement, x → 1, in (A9) gives erroneous integral representation.) It is still possible to extract very accurate results, e.g. one finds Q 2 ≈ −0.9518 indicating that the statistics of the occupation number is also strongly sub-Poissonian when b = 2. One can similarly compute higher cumulants. For instance, to determine the third cumulant one deduces the governing equation for ∂ 3 λ Φ(λ, x) λ=0 from (74), solves it and from the singular behavior at x = 1 extracts y ; the third cumulant is then 3y y − 2(y ) 3 − y .