MAXIMUM GAPS IN ONE-DIMENSIONAL HARD-CORE MODELS DINGDING DONGAND NITYA MANI Abstract. We study the distribution of the maximum gap size in one-dimensional hard-core models. First

2025-05-02 0 0 567.18KB 15 页 10玖币

侵权投诉

MAXIMUM GAPS IN ONE-DIMENSIONAL HARD-CORE MODELS

DINGDING DONG∗AND NITYA MANI†

Abstract. We study the distribution of the maximum gap size in one-dimensional hard-core models. First,

we randomly sequentially pack rods of length 2 onto an interval of length L, subject to the hard-core

constraint that rods do not overlap. We ﬁnd that in a saturated packing, with high probability there is no

gap of size 2 −o(1/L) between adjacent rods, but there are gaps of size at least 2 −1/L1−εfor all ε > 0.

We subsequently study a variant of the hard-core process, the one-dimensional “ghost” hard-core model

introduced by Torquato and Stillinger [19]. In this model, we randomly sequentially pack rods of length 2

onto an interval of length L, such that placed rods neither overlap with previously placed rods nor previously

considered candidate rods. We ﬁnd that in the inﬁnite time limit, with high probability the maximum gap

between adjacent rods is smaller than log Lbut at least (log L)1−εfor all ε > 0.

1. Introduction

The R´enyi parking problem is a classical combinatorial question that gives a simple example of a random

sequential addition (RSA) process; it is a speciﬁc instantiation of a one-dimensional hard-core model of much

interest in statistical mechanics.

The setup for the parking problem proceeds as follows. Consider a closed interval [0, L] for L > 2, into

which rods of length 2 sequentially arrive at integer times. When each rod arrives, we attempt to place it

uniformly at random in the interval, subject to the hard-core condition that rods cannot overlap with each

other. In 1958, R´enyi proved the following well-known result.

Theorem 1.1 (R´enyi [16]).In the above setup, let N(L)be the random variable representing the number

of rods placed in a saturated packing of [0, L](when no more rods can ﬁt without violating the hard-core

constraint). Then,

lim

L→∞

2E[N(L)]

L=α,

where αis the R´enyi parking constant

α:= Z∞

exp −2Zx

1−e−y

ydydx ≈0.7475979202.

In this work, we study the distribution of gaps between adjacent rods in the saturated state, focusing on

the upper extreme. In particular, we seek to understand the following:

Question 1.2. What can we say about the largest gap that arises in a saturated packing of length 2rods

into an interval of length Lby rods of length 2, subject to the hard-core constraint?

Itoh [10] studied a delay integral equation that characterizes the distribution of the minimum gap sizes

in a saturated conﬁguration, following methods of Dvoretzky and Robbins [7]. The distribution of gap sizes

was also examined in the study of the nearest neighbors problem in one-dimensional random sequential

adsorption [17]. In [10], Itoh observed that the expected minimum gap size in a saturated conﬁguration on

an interval of length Lis smaller than any constant ε > 0 in the large Llimit. This work was subsequently

extended to give approximations of the upper tail of the distribution of minimum gap sizes in [14]. These

works, as noted in §4 of [6], imply an analogous integral recurrence for the CDF of the maximum gap size

in a saturated packing. In [6] the authors provided some preliminary observations and noted that further

study of the maximum gap size was of substantial interest.

In this work, we give a threshold for the maximum gap size in a saturated conﬁguration of the hard-core

model, observing that with high probability, a saturated one-dimensional hard-core packing on an interval

∗Department of Mathematics, Harvard University, Cambridge, MA. Email: ddong@math.harvard.edu.

†Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA. Email: nmani@mit.edu.

arXiv:2210.10088v1 [math.PR] 18 Oct 2022

2 DINGDING DONG∗AND NITYA MANI†

of length Lhas no gap of size 2 −o(1/L) but does have gaps of size 2 −1/L1−εfor all ε > 0. More precisely,

we prove the following result.

Theorem 1.3. The following holds in the saturated conﬁguration of a one-dimensional hard-core process on

an interval of length Lpacked by rods of length 2, for Lsuﬃciently large:

•with high probability, there are no gaps of size 2−o(1/L);

•for all a > 0, with positive probability, there exists a gap of size at least 2−a/L;

•for all ε > 0, with high probability, there exists a gap of size at least 2−1/L1−ε.

In the classical one-dimensional hard-core model described above, cars that fail to park have no eﬀects on

future parking attempts. We will be interested in a variant of the hard-core model, motivated by the ghost

RSA process introduced in work of [19] studying sphere packings. Unlike the classical random sequential

addition process, where much is unknown even in 2 dimensions, the authors of [19] are able to analytically

derive the n-point correlation functions and limiting densities, exactly solving the ghost sphere packing model

in arbitrary dimension.

We study the one-dimensional ghost hard-core model, akin to the hard-core model above, focusing on

properties of this process in the inﬁnite time limit. We give a precise deﬁnition below:

Deﬁnition 1.4. We attempt to place rods of length 2 on an interval of length L, as follows:

•Initialize X= [0, L] and Y=∅.

•For t= 1,2, . . . :

–If the X\Yhas no connected component of length 2, abort.

–Choose a uniformly random point x∈[0, L].

–If x∈[0,1) ∪(L−1, L], reject x, replace Yby Y∪((x−1, x + 1) ∩[0, L]), and continue.

–If (x−1, x + 1) ∩Y6=∅, reject x, replace Yby Y∪(x−1, x + 1), and continue.

–Else, accept x, replace Yby Y∪(x−1, x + 1), and continue.

Several further observations about the occupancy probabilities and the pair correlation function associated

to this process can be found in Appendix A.

In the inﬁnite time limit of the one-dimensional ghost hard-core process (on an interval of length L), with

high probability there is no gap of size log L, but there are gaps of size at least (log L)1−εfor arbitrarily

small ε > 0. More precisely, we have the following:

Theorem 1.5. The following holds in the inﬁnite time limit of a one-dimensional ghost hard-core process

on an interval of length Lpacked by rods of length 2, for Lsuﬃciently large:

•with high probabiity, all gaps are smaller than log L;

•for all ε > 0,with high probability, there exists a gap of size (log L)1−ε.

Overview of article. We begin in Section 2 by reviewing the classical one-dimensional hard-core model

and introducing the ghost RSA process of [19]. In Section 3 we prove Theorem 1.3. We prove Theorem 1.5

in Section 4. The ghost hard-core process is very diﬀerent from the classical hard-core process; we illustrate

some diﬀerences to give some context in Appendix A.

One of our primary motivations for studying large gaps in these hard-core processes is to provide a glimpse

into what gaps might look like in a random sequential addition process in higher dimensions. Theorem 1.5

hints that in higher dimensions, in the inﬁnite time limit, a ghost packing may still have room for many

more spheres/cubes to be packed without overlap; we discuss further in Section 5.

Acknowledgements. We would like to thank Henry Cohn and Salvatore Torquato for helpful discussions,

ideas for writing improvements, and several useful reference suggestions for background. NM was supported

by the Hertz Graduate Fellowship and by the NSF GRFP #2141064.

2. Preliminaries

2.1. Notation. Throughout this article, we consider packing rods of length 2 onto an interval of length L,

which we model by the closed interval [0, L]⊆R. Unless stated otherwise, we study conﬁgurations in the

inﬁnite time limit of the two processes, the 1D classical hard-core model and the 1D ghost hard-core model.

We sometimes refer to the inﬁnite time limit of the 1D classical hard-core model as saturation, since

at this limit, no more rods can be packed without violating the hard-core constraint. We sometimes omit

MAXIMUM GAPS IN ONE-DIMENSIONAL HARD-CORE MODELS 3

Figure 1. R´enyi’s parking constant. The blue curve denotes the expected parking density

2E[N(L)]/L, the orange curve denotes the R´enyi parking constant α, and the green curve

(depicted on the right) denotes the approximate function α+2α−2

the modiﬁer hard-core when describing models, as all models considered in this article are subject to the

hard-core constraint. We also employ the following notation conventions.

•Let N(L) denote the number of rods in the classical model at saturation and e

N(L) denote the

number of rods in the ghost model in the inﬁnite time limit.

•Let G(L, r) denote the number of gaps of length at least rin the classical model at saturation, and

G(L, r) denote the number of gaps of length at least rin the ghost model in the inﬁnite time limit.

•For points x1, . . . , xnon the interval, let π(x1,· · · , xn;L) be the n-point correlation function in the

classical hard-core model, the probability that all of x1, . . . , xnare occupied by rods at saturation; let

eπ(x1,· · · , xn;L) be the corresponding n-point correlation function of the ghost model in the inﬁnite

time limit.

For quantities depending on L, we use f=o(g), fgand g`interchangeably to denote that

limL→∞ f/g = 0; we use f=O(g) to denote that there exists a constant C≥0 such that f≤Cg for

suﬃciently large L; we use f∼gto denote that limL→∞ f/g = 1

2.2. Classical 1D hard-core model at saturation. Consider the classical 1D hard-core model, where

we place rods of length 2 on an interval of length L. It is easy to check the following recurrence relation on

E[N(L)]:

E[N(L)] = ZL−1

x=1

L−2(1 + E[N(x−1)] + E[N(L−x−1)])dx = 1 + 2

L−2ZL−2

E[N(x)] dx.

As noted in the introduction, in [16], R´enyi established that this mean density of rods converges to the

R´enyi parking constant α≈0.748. Dvoretzky and Robbins [7] gave a more reﬁned estimate of the rate of

convergence. In particular, they proved that

E[N(L)] = αL/2 + α−1 + O((4e/L)L/2−3/2),

indicating very fast convergence of the expected parking density 2E[N(L)]/L to the following approximate

density α+2α−2

Understanding the n-point correlation functions is a primary motivating question when analyzing statis-

tical mechanics models. The occupancy probability, π(x, L) is the chance that point xis covered by a rod

at saturation; it has the basic symmetry property π(x, L) = π(L−x, L) for all x∈[0, L] and was studied

along with other statistics of the correlation function in the one-dimensional hard-core model in [5].

One similar observation that arises from such analysis concerns the pair correlation function, π(x1, x2;L),

the probability that both x1, x2are occupied at saturation. It will be convenient to think about this

correlation when both x1, x2are far away from the boundary, and thus we could imagine packing rods of

length 2 on a circle of length L. We observe that this pair correlation function is identical to the cover

probability on an interval of length L−2, by cutting one of the rods in half and unwinding, i.e.

π(x1, x2;L) = π(|x1−x2| − 1, L −2).

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

MAXIMUMGAPSINONE-DIMENSIONALHARD-COREMODELSDINGDINGDONG*ANDNITYAMANIAbstract.Westudythedistributionofthemaximumgapsizeinone-dimensionalhard-coremodels.First,werandomlysequentiallypackrodsoflength2ontoanintervaloflengthL,subjecttothehard-coreconstraintthatrodsdonotoverlap.Wendthatinasaturatedpackin...

展开>> 收起<<

MAXIMUM GAPS IN ONE-DIMENSIONAL HARD-CORE MODELS DINGDING DONGAND NITYA MANI Abstract. We study the distribution of the maximum gap size in one-dimensional hard-core models. First.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

MAXIMUM GAPS IN ONE-DIMENSIONAL HARD-CORE MODELS DINGDING DONGAND NITYA MANI Abstract. We study the distribution of the maximum gap size in one-dimensional hard-core models. First

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: