# Central Limit Theorem for Coloured Hard Dimers

Authors: Maria Simonetta Bernabei; Horst Thaler
Journal: Journal of Probability and Statistics
 (2010)

---

## Abstract

We study the central limit theorem for a class of coloured graphs. This means that we investigate the limit behavior of certain random variables whose values are combinatorial parameters associated to these graphs. The techniques used at arriving this result comprise combinatorics, generating functions, and conditional expectations.


---

## Body

## 1. Introduction

In this paper we want to verify the central limit theorem (CLT) in the context of a combinatorial problem for coloured hard dimer configurations, which comprise a certain class of labeled graphs onℝ. We will consider two combinatorial parameters that characterize our hard dimers and will therefore investigate a bivariate mass function. The problem is interesting as far as it is difficult to reformulate the task in such a manner that a general CLT becomes applicable. The proof here is based on the explicit knowledge of the bivariate mass function and is a generalization of the original De Moivre-Laplace theorem. By the way, coloured hard dimers are applied in the framework of causally triangulated (2+1)-dimensional quantum gravity. We believe that our result could be employed for further study on the asymptotics of the one-step propagator, as it has been defined in [1] by means of an inversion formula.Let us describe the objects we are interested in. Given a sequenceξN of length N of consecutive blue and red vertices on the one-dimensional lattice ℤ, one defines a dimer to be an edge connecting two nearest sites of the same colour. The dimer’s colour is given by the colour of its boundary vertices. A coloured hard dimer configuration (CHDC) is defined to be a sequence ξN together with a sequence of dimers on it, which must not intersect. We include also the empty CHDC, that is, the configuration when no dimers are present. In Figure 1, an example of a CHDC is shown.Figure 1
A CHDC(N=13) with two red dimers and one blue dimer.In graph-theoretic language, CHDCs form a subclass of labeled graphs whose vertices and edges carry one of two possible labels (here termed colours). For a given CHDCD, let nb(D),nr(D) denote the numbers of blue, red dimers and nbr(D) the number of inner vertices, that is, vertices inside dimers that are not boundary points. Below we shall consider the numbers (nb,nr,nbr) as random variables (r.v.s) investigating their joint probability generating function. Due to the symmetry w.r.t. nb and nr, this will lead us to the joint mass function of the r.v.s (nb+nr,nb+nr+γb+γr), where γb(D) and γr(D) denote the number of blue and red vertices which are not occupied by dimers (“single points”).The paper is organized as follows. In Section2, we give an explicit formula for the combinatorial generating function and define the probability mass function associated with CHDCs, with an exact expression for its normalizing constant, that is, CN=(3/2)N-1. Moreover, we find the right probability distribution for the r.v. nb+nr+nbr. In Section 3, we calculate the first two moments of the r.v. nb+nr. In Section 4, we prove a CLT for the pair of r.v.s (nb+nr,nb+nr+γb+γr). The limit distribution is a bivariate Gaussian distribution with correlation coefficient equal to -1/3.


## 2. Coloured Hard Dimers and Probability Distributions

With the definitions made in the introduction, the following constraint(2.1)2nb(D)+2nr(D)+nbr(D)+γb(D)+γr(D)=N
holds. In the example above (Figure 1),
(2.2)nb(D)=1,nr(D)=2,nbr(D)=3,γb(D)=3,γr(D)=1.First, we want to find the combinatorial generating function of the variablesnb,nr,nbr. This is given as  (2.3)F̃N(u,v,w)=∑ξNFξN(u,v,w),
where (2.4)FξN(u,v,w)=∑CHDC′sonξNunb(D)vnr(D)wnbr(D),u,v,w∈R.
It is useful to define further variables t and s, where t corresponds to the number of sites occupied by dimers and s to the number of coloured hard dimers  (2.5)t=N-γb(D)-γr(D),s=nb(D)+nr(D).In the next proposition, we prove an exact formula forF̃N, using combinatorial arguments.Lemma 2.1.
The combinatorial generating functionF̃N has the following explicit expression, for any N:
(2.6)F̃N(u,v,w)=2N(1+∑t=1N∑s=1[t/2](N-t+ss)(t-s-1s-1)(u+v4)s(w2)t-2s),
where [·] denotes the integer part.Proof of Lemma2.1.
Consider a CHDCD on any ξN with fixed but arbitrary N. We set nb(D)=g, nr(D)=h, nbr(D)=m, γb(D)=γb, and γr(D)=γr. By (2.1) and (2.5) the following equalities
(2.7)2g+2h+m+γb+γr=N,t=2g+2h+m
hold.
First, we fix the number of blue and red dimers and that of single pointsγb and γr. Note that by (2.7) m is also fixed. The dimers of the same colour are considered indistinguishable. Then, we calculate all possible permutations of g blue dimers, h red dimers, γb blue single points, and γr red single points, that is,
(2.8)(g+h+γb+γr)!g!h!γb!γr!.
Now, for any nontrivial given permutation of coloured dimers and single points, that is, nb+nr≠0 (the empty CHDCs contribute a factor 2N), we have to see in how many ways we can distribute the given m inner vertices over the given dimers. The number of all these combinations is
(2.9)(m+g+h-1g+h-1).
Therefore, all contributions are summed to
(2.10)2N+∑Ng,h,m:2g+2h+m=1∑γb+γr=N-2g-2h-m(g+h+γb+γr)!g!h!γb!γr!(m+g+h-1g+h-1)ugvhwm.
Since g+h+γb+γr=N-g-h-m and γr=N-2g-2h-m-γb, we have
(2.11)F̃N(u,v,w)=2N+∑Ng,h,m:2g+2h+m=1(N-g-h-m)!g!h!(N-2g-2h-m)!(m+g+h-1g+h-1)ugvhwm×∑γb=0N-2g-2h-m(N-2g-2h-mγb).
In obtaining (2.11), we have multiplied and divided the generic term of the previous sum by (N-2g-2h-m)!. The binomial formula yields 2N-2g-2h-m, and (2.11) becomes
(2.12)2N(1+∑Ng,h,m:2g+2h+m=1(N-g-h-m)!g!h!(N-2g-2h-m)!(m+g+h-1g+h-1)(u4)g(v4)h(w2)m).
Now by multiplying and dividing the generic term of the sum by (g+h)!, we get
(2.13)2N(1+∑Ng,h,m:2g+2h+m=1(N-g-h-mg+h)(m+g+h-1g+h-1)(g+hg)(u4)g(v4)h(w2)m).
Performing the variable changements s=g+h and t=2g+2h+m, with s and t as above, we get
(2.14)F̃N(u,v,w)=2N(1+∑t=1N∑s=1[t/2](N-t+ss)(t-s-1s-1)(u+v4)s(w2)t-2s).
In the last sum, we applied again the binomial formula
(2.15)∑g=0s(sg)(u4)g(v4)s-g=(u+v4)s.
Therefore, we get formula (2.6) where only the indices s and t appear. The lemma is so proved.If we want to understand the appearance of CHDCs in probabilistic terms it is natural to assign each CHDC the same probability, so that the combinatorial frequency of particular configurations will be proportional to their probability. For this, let us define a family of probability spaces(ΩN,ℱN,PN)N∈ℕ≥1. We choose ΩN, to be the set of all different CHDCs. The σ-algebra ℱN is the power set of ΩN and for PN we take the probability measure having uniform distribution on ΩN. Normalizing the function F̃N by F̃N|(u,v,w)=(1,1,1) then just gives the joint probability generating function of the random variables nb,nr,nbr, defined on (ΩN,ℱN,PN), which count, for each hard dimer configuration, the number of blue, red dimers and the number of inner vertices, respectively.The main result of this section is an explicit formula for the normalizing constantCN of the probability measure PN, that holds for any N, derived by evaluating the combinatorial generating function F̃N at the point u=v=w=1. Considering the change of variable k=N-t+s, we have  (2.16)CN=2N(1+∑k=1N-1∑s=1k(ks)(N-k-1s-1)12N-k)=2N∑k=1N(N-1k-1)12N-k=2⋅3N-1.Throughout the text, we use the convention that(ab)=0, whenever a<b, a<0 or b<0.Remark 2.2.
Note that, upon normalization, the factors(ks)(N-k-1s-1) in (2.16) yield a hypergeometric distribution with respect to the variable s. Here, the sample size is N-k and k (resp., N-k-1) are the total number of successes (resp. failures). Therefore, summing over s, we get the binomial coefficient (N-1k-1).In this way, we have also found the joint mass functionP̃N related to the r.v.s nb+nr and nb+nr+γb+γr, more precisely,  (2.17)P̃N(s,k)=PN(nb+nr=s;nb+nr+γb+γr=k)
is given by  (2.18)P̃N(s,k)={(23)N-1,fors=0,(ks)(N-k-1s-1)(23)k-1(13)N-k,otherwise.Remark 2.3.
From (2.18), we deduce that the r.v. nb+nr+γb+γr is binomial with parameters N-1 and 2/3. Since nb+nr+nbr=N-(nb+nr+γb+γr), it follows that the r.v. nb+nr+nbr is also binomial with parameters N-1 and 1/3.


## 3. Number of Dimers: The First Two Moments

When proving a CLT, we have to rescale the r.v.s by subtracting the means and dividing by the standard deviations in question. In the previous section, we have seen thatnb+nr+γb+γr is binomial, whose moments are known. Although the distribution of the r.v. nb+nr is not of common type, we are able to compute its mean and variance. For this, we rely on the fact that the conditional distribution of nb+nr, given nb+nr+γb+γr, is hypergeometric by Remark 2.2. We start with the computation of the mean.Proposition 3.1.
For anyN, the following formula
(3.1)EN(nb+nr)=2N-19
holds.ByEN, we indicate the mean with respect to the probability measure PN.Proof.
By the properties of the conditional expectation and taking into account Remark2.2, we have
(3.2)EN(nb+nr)=∑k=1NEN(nb+nr∣nb+nr+γb+γr=k)PN(nb+nr+γb+γr=k)=∑k=1Nk(N-k)N-1(N-1k-1)(23)k-1(13)N-k.
In fact, the expectation of our hypergeometric distribution is k(N-k)/(N-1). Hence,
(3.3)EN(nb+nr)=13∑k=1Nk(N-2k-1)(23)k-1(13)N-1-k=13[23(N-2)+1]=2N-19.
In the last sum, we have used the decomposition k=(k-1)+1 which gives the first and zeroth moment of the binomial distribution with parameters N-2 and 2/3.Remark 3.2.
By identity (2.1), Remark 2.3, and from (3.1), we are able to calculate the single point number’s mean. In fact
(3.4)EN(γb+γr)=N-EN(nb+nr)-EN(nb+nr+nbr)=N-2N-19-N-13=49(N+1).
Note that, as N→∞,
(3.5)EN(γb+γr)≍49N≍2EN(nb+nr),
that is, for the present model, the expected number of single points is asymptotically twice the expected number of dimers. Moreover, fixing the number of single points, the conditional probability distribution of γb (resp., γr) is binomial and symmetric.In order to find the variance ofnb+nr, we apply the law of total variance involving the conditional expectation and the conditional variance, (see, e.g., [2])(3.6)Var⁡N(nb+nr)=EN(Var⁡N(nb+nr∣nb+nr+γb+γr))+Var⁡N(EN(nb+nr∣nb+nr+γb+γr)).
The symbol VarN indicates the variance w.r.t. PN. We recall that the conditional variance of a r.v. X given a r.v. Y is defined as (3.7)Var⁡(X∣Y)=E(X2∣Y)-(E(X∣Y))2.
Alternatively one can define Var(X∣Y) as that function of Y, whose value at Y=y is given by (3.8)Var⁡(X∣Y=y)=E(X2∣Y=y)-(E(X∣Y=y))2.
In the next Lemmas, we find the exact expressions of the two terms in (3.6).Lemma 3.3.
For allN, one has
(3.9)EN(Var⁡N(nb+nr∣nb+nr+γb+γr))=481(N-3).Proof.
As above, we use the fact that the variance of the hypergeometric distribution is known. In our case,(3.10)Var⁡N(nb+nr∣nb+nr+γb+γr=k)=(N-k)(N-k-1)k(k-1)(N-1)2(N-2).
This entails that
(3.11)EN(Var⁡N(nb+nr∣nb+nr+γb+γr))=∑k=1NEN(Var⁡N(nb+nr∣nb+nr+γb+γr=k))PN(nb+nr+γb+γr=k)=19∑k=1N-2k(k-1)N-1(N-3k-1)(23)k-1(13)N-2-k=19(N-1)[49(N-3)(N-4)+43(N-3)]=481(N-3).
In fact, we can writek(k-1)=(k-1)(k-2)+2(k-1), so that the factorial moments of the binomial distribution with parameters N-3 and 2/3 appear. It is easy to check that its second factorial moment is 4/9(N-3)(N-4).Lemma 3.4.
For allN, it holds that
(3.12)Var⁡N(EN(nb+nr∣nb+nr+γb+γr))=281(N+7).Proof.
Using again the properties of the conditional expectation, we have(3.13)Var⁡N(EN(nb+nr∣nb+nr+γb+γr))=EN(EN(nb+nr∣nb+nr+γb+γr)2)-(EN(nb+nr))2.
From Proposition 3.1, we know that EN(nb+nr)=(2N-1)/9, so that it remains to compute the first term in (3.13). The latter is given by
(3.14)EN(EN(nb+nr∣nb+nr+γb+γr)2)=∑k=1Nk2(N-k)2(N-1)2(N-1k-1)(23)k-1(13)N-k.
As in the previous Lemma 3.3, it is useful to use the factorial moments of the binomial distribution. In achieving this, we simply write (N-k)2=(N-k)(N-k-1)+(N-k). According to this decomposition, the sum (3.14) splits into two terms, which we denote by A1 and A2, respectively. The first term A1 is
(3.15)A1=N-29(N-1)∑k=1N-2k2(N-3k-1)(23)k-1(13)N-2-k=N-29(N-1)[49(N-3)(N-4)+2(N-3)+1],A2=13(N-1)∑k=1N-1k2(N-2k-1)(23)k-1(13)N-1-k=13(N-1)[49(N-2)(N-3)+2(N-2)+1].
In the above computations, we have used the equality k2=(k-1)(k-2)+3(k-1)+1, so that the factorial moments come into play. From (3.13) and (3.15), it is easy to get (3.12).Finally, we are able to state the next proposition for the variance ofnb+nr.Proposition 3.5.
For allN, one has
(3.16)Var⁡N(nb+nr)=281(3N+1).Proof.
This follows immediately from (3.6) and Lemmas 3.3 and 3.4.Remark 3.6.
From the formulas for the mean and the variance ofnb+nr ((3.1) and (3.16)), one can deduce that the distribution of nb+nr is asymptotically not binomial. In fact, EN(nb+nr)≍(2/9)N and VarN(nb+nr)≍(2/27)N≠(2/9)·(7/9)N. In the next section, we prove that it is asymptotically Gaussian, for large N, that is, a CLT holds.


## 4. Central Limit Theorem for the Dimers’ Number

In the present section, we study the asymptotic distribution of the dimers’ number, in particular, we prove a CLT for the total number of dimers plus single pointsnb+nr+γb+γr, analyzed in Section 2, and the number of dimers nb+nr. The limit distribution is a bivariate Gaussian distribution with correlation coefficient equal to -1/3.The following proof is a generalization of De Moivre-Laplace's Theorem.Theorem 4.1.
A central limit theorem holds for the joint probability distribution. This means that for any-∞≤a<b≤∞ and -∞≤a′<b′≤∞, one has
(4.1)lim⁡N→∞∑s:x∈(a,b)k:y∈(a′,b′)P̃N(s,k)=12π2/3∫ab∫a′b′e-(3/4)(z2+z′2+(23/3)zz′)dzdz′,
where
(4.2)x=s-(2/9)N6N/9,y=k-(2/3)N2N/3.Remark 4.2.
In (4.2) above, we consider only the first order of the expectations and the variances with respect to N. It is easy to see that the result remains the same when including terms of zeroth order, as they do not contribute to the asymptotics.Proof.
We have the following.
Step 1.
We shall first verify a local version of the CLT, that is,(4.3)PN(nb+nr=s;nb+nr+γb+γr=k)=1(2π)2((2/27)N)((2/9)N)(2/3)e-(3/4)(x2+(23/3)xy+y2)(1+rx,y(N)),
where x,y are given by (4.2). Moreover, limN→∞rx,y(N)=0, uniformly with respect to x and y, belonging to finite intervals (a,b) and (a′,b′), respectively.
By the remark above and the fact that the indicess and k are both of order N, we can forget the constants in (2.18), that is, k-1≍k and N-k-1≍N-k, as N→∞.
As in De Moivre-Laplace’s Theorem, we apply Stirling's formula to the binomial coefficients in (2.18). In the present model, we have two binomial coefficients instead of one, so that the calculus becomes heavier than in De Moivre-Laplace’s Theorem. We write
(4.4)(ks)(N-ks)(23)k(13)N-k=eλN,s,k︸AN,s,k⋅12π(s(k-s)/k)2π(s(N-k-s)/(N-k))︸BN,s,k⋅(k3s)s(2k3(k-s))k-s(2(N-k)3s)s(N-k3(N-k-s))N-k-s︸CN,s,k,
where
(4.5)λN,s,k≡λk-λs-λk-s+λN-k-λs-λN-k-s,112n+1≤λn≤112n,
for every n∈ℕ.
Taking into account (4.2), we consider the first factor AN,s,k in (4.4) with respect to the variables x and y. It is easy to see that
(4.6)AN,s,k=1+rx,y(1)(N),
with rx,y(1)(N)→0, as N→∞, uniformly with respect to x and y. In fact, since x,y belong to bounded intervals, one can estimate λN,s,k uniformly from above and from below with respect to x and y.
For the factorBN,s,k in (4.4), the following asymptotic holds
(4.7)BN,s,k≍12π(6N/9)(2N/3)2/3,
as N→∞.   In fact, from (4.2), we estimate
(4.8)s(k-s)k=427N(1+rx,y(2)(N)),
with rx,y(2)(N)→0, as N→∞, uniformly with respect to x and y.
Analogously,(4.9)s(N-k-s)N-k=227N(1+rx,y(3)(N)),
with rx,y(3)(N)→0, as N→∞, uniformly with respect to x and y.
By (4.7), we see that the correlation coefficient can be ±1/3. Its sign will be determined later.
Finally, we consider the logarithm of the last factorCN,s,k in (4.4),
(4.10)ln⁡CN,s,k=-sln⁡(3sk)-(k-s)ln⁡(3(k-s)2k)-sln⁡(3s2(N-k))-(N-k-s)ln⁡(3(N-k-s)N-k)≡∑i=14CN,s,ki.
Now we express each term of the sum in (4.10) CN,s,ki, i=1,2,3,4, in terms of x and y, defined in (4.2). We start with CN,s,k1,
(4.11)CN,s,k1=-2N9(2N+3x)ln⁡(1+3x-y2N+y).
Since the last logarithm above is of the form ln(1+z), with z→0, we can expand it around z=0, ln(1+z)=z-(z2/2)+o(z2), as z→0. The same is true for each logarithm function present in any CN,s,ki, i=1,2,3,4. So CN,s,k1 becomes, as N→∞,
(4.12)CN,s,k1≍-2N18(2N+3x)(3x-y)(22N-3x+3y)(2N+y)2.
Analogously, for the other CN,s,ki, i=2,3,4, we find
(4.13)CN,s,k2≍2N72(22N-3x+3y)(3x-y)(42N+3x+3y)(2N+y)2,CN,s,k3≍-2N18(2N+3x)(3x+2y)(22N-3x-6y)(2N-2y)2,CN,s,k4≍22N9(N/2-3x-3y)(3x+2y)(2N+3x)(2N-2y)2.
From (4.12)-(4.13), we find the main contribution
(4.14)∑i=14CN,s,ki≍-34[x2+233xy+y2].
We have thus proven formula (4.3).
Remark 4.3.
Note that the last term in (4.14) is of the form
(4.15)-12(1-ρ2)(x2-2ρxy+y2),
with ρ=-1/3. We get thus a bivariate Gaussian distribution with correlation coefficient equal to -1/3, that is, the r.v.s nb+nr and nb+nr+γb+γr are negatively correlated.
Step 2.
Now, we want to show formula (4.1), adapting the steps from the one-dimensional case, see [3]. For finite a,b and a′,b′, this follows from (4.3) which implies that the l.h.s. of (4.1) is just a Riemann sum approximation to the r.h.s.. To understand infinite boundaries, we consider, for example, the particular case where a=a′=-∞ and b,b′<∞. The other cases can be treated similarly. Let f(z,z′) be the joint density function of the integral in (4.1). Since
(4.16)∫R2f(z,z′)dzdz′=1,
there exist for all ε>0 finite constants A,A′>0 such that
(4.17)∫-AA∫-A′A′f(z,z′)dzdz′≥1-ε.
Moreover, for all ε>0∃N¯ : for all N≥N¯(4.18)|∑|x|≤A|y|≤A′P̃N(s,k)-∫∫|z|≤A|z′|≤A′f(z,z′)dzdz′|≤ε.
From (4.17) and (4.18), we deduce that
(4.19)∑|x|≤A|y|≤A′P̃N(s,k)≥1-2ε.
for N large enough. Without loss of generality, we now assume that A≥b,A′≥b′. Then, it remains to verify that, for all ε′>0,
(4.20)|∑-∞<x≤b-∞<y≤b′P̃N(s,k)-∫∫-∞<z≤b-∞<z′≤b′f(z,z′)dzdz′|≤ε′,
for N large enough. In order to show this, one has to express the double sum and integral of (4.20) by means of the larger domains {-∞<x≤A-∞<y≤A′} and {-∞<z≤A-∞<z′≤A′} by subtraction of appropriate terms. The resulting sums and integrals can be split over domains which may be finite or infinite. The sums over the finite domains are again Riemann approximations to the corresponding integrals. The sums and integrals over the infinite domains can be made arbitrarily small by employing estimates (4.17) and (4.19), which completes the proof.Choosinga′=-∞,b′=∞ in Theorem 4.1, we get the following result.Corollary 4.4.
A CLT holds for the r.v.nb+nr, that is, for any -∞≤a<b≤∞, one has
(4.21)lim⁡N→∞∑s:x∈(a,b)PN(nb+nr=s)=12π∫abe-z2/2dz.



---

*Source: 781681-2011-01-16.xml*