Thierry E Huillet

A BOSE-EINSTEIN APPROACH TO THE RANDOM PARTITIONING OF AN INTEGER

Keywords: Bose-Einstein and Integer Partitioning Random integer partition, random allocation, discrete covering of the circle, discrete spacings, balls in boxes, Bose-Einstein, k-nearest neighbor random graph

Consider N equally-spaced points on a circle of circumference N . Choose at random n points out of N on this circle and append clockwise an arc of integral length k to each such point. The resulting random set is made of a random number of connected components. Questions such as the evaluation of the probability of random covering and parking configurations, number and length of the gaps are addressed. They are the discrete versions of similar problems raised in the continuum. For each value of k, asymptotic results are presented when n, N both go to ∞ according to two different regimes. This model may equivalently be viewed as a random partitioning problem of N items into n recipients. A grand-canonical balls in boxes approach is also supplied, giving some insight into the multiplicities of the box filling amounts or spacings. The latter model is a k-nearest neighbor random graph with N vertices and kn edges. We shall also briefly consider the covering problem in the context of a random graph model with N vertices and n (out-degree 1) edges whose endpoints are no more bound to be neighbors.

Introduction

Many authors considered the problems related to the coverage of the unit circle by arcs of equal sizes randomly placed on the circle, among which [START_REF] Withworth | Excercises on choice and chance[END_REF], [START_REF] Stevens | Solution to a geometrical problem in probability[END_REF], [START_REF] Feller | An introduction to probability theory and its applications[END_REF], [START_REF] Flatto | The random division of an interval and the random covering of a circle[END_REF], [START_REF] Siegel | Random arcs on the circle[END_REF], [START_REF] Holst | A note on random arcs on the circle[END_REF], [START_REF] Holst | On the random coverage of the circle[END_REF], [START_REF] Huillet | Random covering of the circle: the size of the connected components[END_REF]. In this Note, motivated by a Remark in the paper ( [START_REF] Cannings | Modelling protein-protein interactions networks from yeast-2-hybrid screens with random graphs[END_REF], p.18) on random graphs, we shall be concerned by a discrete version to the above problem, following [START_REF] Holst | On discrete spacings and the Bose-Einstein distribution[END_REF] and [START_REF] Ivchenko | On the random covering of a circle: a discrete model[END_REF]: Consider N equally spaced points (vertices) on the circle of circumference N so with arc length 1 between consecutive points. Sample at random n out of these N points and consider the discrete random spacings between consecutive sampled points, turning clockwise on the circle. Let k be an integer and append clockwise an arc of length k to each sampled points, forming a random set of arcs on the circle. What is the probability that the circle is covered? If the circle is not covered, how many gaps do we have in the random set of arcs? What is the probability that no arc overlap (the discrete hard rods model), what is the probability that no arc overlap and that the gaps lengths are smaller than k itself (the discrete version of Rényi's parking model). All these questions require some understanding of both the smallest and largest spacings in the sample. This model can equivalently be formulated in terms of the random partitioning of N items into n recipients. Here also, the distributions of the smallest and largest shares attached to each of the recipients are of fundamental interest. We will focus on the thermodynamical limit regime: n, N → ∞ while n/N → ρ and also, sometimes, in a regime where n, N → ∞, while n 1 -n N k → α, 0 < α < ∞. In the first regime, the occurrence of say covering and parking configurations are exponentially rare in the whole admissible density range of ρ, whereas in the second one they are macroscopically frequent. At the heart of these models is the Bose-Einstein distribution for discrete spacings. Finally, a Bosonic grand canonical approach to the above model will be considered where N balls are assigned at random to N boxes. For this urn model, we will study the number of empty boxes and the number of boxes with i balls, giving some insight into the spacings multiplicities, both in the canonical and the grand-canonical ensembles.

The model just developed is a k-nearest neighbors random graph with N vertices and kn edges. In the last Section, we consider a random graph with N vertices and n (out-degree 1) edges whose endpoints are no more necessarily neighbors, being now chosen at random on the whole set of vertices. In this model of a different kind, each of the n sampled points is allowed to create a link far away with any of the N vertices, not necessarily with neighbors. We estimate the covering probability for this random graph model in the spirit of Erdős-Rényi (see [START_REF] Bollobás | Random graphs[END_REF]). We show that, in sharp contrast to the k-nearest neighbor graph, there exists a critical density ρ c = 1e -1 above which covering occurs with probability one. The take-home message is to what extent when connections are not restricted to neighbors, the chance of connectedness is increased.

Random partition of an integer and discrete spacings

Consider a circle of circumference N, with N integer. Consider N equally spaced points on the circle so with arc length 1 between consecutive points. We shall call this discrete set of points the N -circle. Draw at random n ∈ {2, .., N -1} points without replacement at the integer sites of this circle (thus, with M 1 , .., M n independent and identically distributed, say iid, and uniform on {1, .., N }). Pick at random one the points M 1 , .., M n and call it M 1:n . Next, consider the ordered set of integer points (M m:n , m = 1, .., n), turning clockwise on the circle, starting from M 1:n . Let N m,n = M m+1:n -M m:n , m = 1, .., n -1, be the consecutive discrete spacings, with N n,n = M 1:n -M n:n , modulo N , closing the loop. Under our hy-

pothesis, N m,n d = N n , m = 1, .., n, independent of m, the distribution of which is F Nn (k) := P (N n > k) = 1 -F Nn (k) = N -k-1 n-1 / N -1 n-1 , with EN n = N/n.
It is indeed a result of considerable age (see e.g. [START_REF] Holst | On discrete spacings and the Bose-Einstein distribution[END_REF]) that identically distributed (id) discrete spacings

N n := (N m,n ; m = 1, .., n), with |N n | := m N m,n = N can be generated as the conditioning (1) N n = G n | {|G n | = N } ,
where

|G n | := n m=1 G m is the sum of n iid geometric(α) random variables ≥ 1 (with P (G 1 ≥ k) = α k-1 , k ≥ 1, α ∈ (0, 1)) and so N n has the claimed Pòlya-Eggenberger PE (1, n -1) distribution: P (N n = k) = N -k-1 n-2 / N -1 n-1 , k = 1, .., N -n + 1.
Note that as n, N → ∞, while n/N = ρ < 1 is fixed, using Stirling formula, we get the convergence in distribution

(2) N n d → G,
where G ≥ 1 is a discrete random variable (rv) with geometric(1ρ) distribution:

P (G ≥ m) = (1 -ρ) m-1 , m ≥ 1. The limiting expected value of N n is 1/ρ. With k := (k m ; m = 1, .., n), the joint law of N n is (3) P (N n = k) = 1 N -1 n-1 1 (|k| = N ) ,
which is the exchangeable uniform distribution on the restricted discrete N -simplex |k| := n m=1 k m = N , k m ≥ 1, also known as the Bose-Einstein distribution. This distribution occurs in the following Pòlya-Eggenberger urn model context (see [START_REF] Johnson | Urn models and their application. An approach to modern discrete probability theory[END_REF]): An urn contains n balls all of different colors.. A ball is drawn at random and replaced together while adding another ball of the same color.. Repeating this Nn times, N n is the number of balls of the different colors in the urn. See [START_REF] Holst | On discrete spacings and the Bose-Einstein distribution[END_REF].

From the random model just defined, we get,

(4) N = n m=1 N m,n
which corresponds to a random partition of N into n id parts or components ≥ 1.

It also models the following random allocation problem (see [START_REF] Kolchin | Random allocations[END_REF]): N items are to be shared at random between n recipients. N m,n is the amount of the N items allocated to recipient m. Although all shares are id, there is a great variability in the recipients parts as it will become clear from the detailed study of the smallest and largest shares in the sample.

This model is connected to the continuous spacings between n randomly placed points on the unit circle in the following way: As N → ∞, N n /N d → S n where S n := (S 1,n , .., S n,n ) has Dirichlet uniform density function on the continuous unit n-simplex [START_REF] Pyke | Spacings (With discussion)[END_REF] (5) f S1,..,Sn (s 1 , .., s n ) = (n -1)! • δ ( n m=1 sm-1) .

Let P n (1) := n m=1 1 (N m,n > 1) be the amount of sampled points whose distance to their clockwise neighbors is more than one unit. There are n -P n (1) sampled points which are neighbors, therefore

N = 1 • (n -P n (1)) + n m=1 N m,n 1 (N m,n > 1) = n + n m=1
(N m,n -1) + where i + = max (i, 0) . Appending an arc of length 1 clockwise to the n sampled points and considering the induced covered set from {1, .., N }, L n (1) := n m=1 (N m,n -1) + represents the length of the gaps (the size of the uncovered set). So, from the model L n (1) = Nn is a constant and

N -n = n m=1
(N m,n -1) + corresponds to a random partition of Nn into n id parts or components ≥ 0. Stated differently, the length of the covered set L n (1) = N -L n (1) is constant equal to n, which is obvious.

Of considerable interest is the sequence (N m:n ; m = 1, .., n) obtained while ordering the components sizes (N m,n ; m = 1, .., n), with N 1:n ≤ .. ≤ N n:n .

By the exclusion-inclusion principle, the cumulative distribution function F Nm:n (k) = P (N m:n ≤ k) is easily seen to be (6)

F Nm:n (k) = 1 N -1 n-1 n q=m n q n p=n-q (-1) p+q-n q n -p N -pk -1 n -1
which has been known for a while in the context of spacings in the continuum (see [START_REF] Withworth | Excercises on choice and chance[END_REF]).

In particular,

F Nn:n (k) := P (N n:n ≤ k) = 1 N -1 n-1 n p=0 (-1) p n p N -pk -1 n -1 and (7)
F N1:n (k) := P (N 1:n > k) = N -nk -1 n -1 / N -1 n -1 (8)
are the largest and smallest component sizes distributions in this case.

In the formula giving F Nn:n (k) , with [x] standing for the integral part of x, the sum should as well stop at n ∧ N -n k , observing i j = 0 if i < j.

Clearly, if k = 1, P (N n:n = 1) = 0 (= 1) whatever n < N (if n = N ). If k = 2 and N > 2n, P (N n:n ≤ 2) = P (N n:n = 2) = 0. If N = 2n, P (N n:n = 2) = 1/ 2n-1 n-1
is the probability of a regular configuration with all sampled points equally-spaced by two arc length units. If n < N < 2n, P (N n:n = 2) is the probability of a configuration with 2n -N neighbor points distant of one arc length unit and Nn points distant of two units.

As N, k → ∞ while k/N → s N -pk -1 n -1 / N -1 n -1 → (1 -ps) n-1 + With 0 < a < b ≤ N, the joint law of (N 1:n , N n:n ) is given by (9) P (N 1:n > a, N n:n ≤ b) = n m=0 (-1) m N -1 n-1 n m N -(na + m (b -a)) -1 n -1 .
In the random partitioning of N image, it gives the probability that the shares of all n recipients all range between a and b. Putting (a = k, b = N ) and (a = 0, b = k) gives F Nn:n (k) and F N1:n (k) . This formula was first obtained by [START_REF] Darling | On a class of problems related to the random division of an interval[END_REF] in the continuum. Putting next a = k, b = 2k, we get

(10) P (N 1:n > k, N n:n ≤ 2k) = 1 N -1 n-1 n m=0 (-1) m n m N -(n + m) k -1 n -1 . When k = 1, we have P (N 1:n > 1, N n:n ≤ 2) = N -1 n-1 -1 1 N =2n . If N = 2n, 2n-1 n-1
-1 is the probability of the configuration where the n sampled points are exactly equally-spaced, each by two arc length units.

As n, N → ∞ while n/N → ρ < 1, with E a rv with rate 1 exponential distribution

(11) -log (1 -ρ) n (N 1:n -1) d → E; ρ log n N n:n a.s. → 1,
suggesting that the smaller (larger) integer component in the partition of N is of order n -1 (respectively log n) in the considered asymptotic regime. More precisely, using the joint law of (N

1:n , N n:n ) (12) -log (1 -ρ) n (N 1:n -1) , N n:n - log n ρ d → (E, G) ,
where (E, G) are independent rvs on R + ×R with distributions P (E > t) = e -t and P (G ≤ t) = e -e -t with E (G) = γ, the Euler constant (exponential and Gumbel).

Although in the random partitioning of N , all parts attributed to each recipient are id, there is a great variability in the shares as the smallest one is of order 1 and the largest one of order log n.

N -circle covering problems

Let S n := {M 1 , .., M n } be the discrete set of points drawn at random on the N -circle with circumference N . Fix k ∈ {1, .., N }. Consider the coarse-grained discrete random set of intervals

(13) S n (k) := {M 1 + l, .., M n + l, 1 ≤ l ≤ k}
appending clockwise an arc of integral length k ≥ 1 to each starting-point atom of S n .

The number of gaps and the length of the covered set. Let P n (k) be the number of gaps of S n (k) (which is also the number of connected components), so with P n (k) = 0 as soon as the N -circle is covered by S n (k).

Let also L n (k) be the total integral length of S n (k). As there are n -P n (k) spacings covered by k and P n (k) gaps each contributing of k to the covered length, it can be expressed as a contribution of two terms (i ∧ j = min (i, j)),

(14) L n (k) = n-Pn(k) m=1 N m:n + kP n (k) = n m=1 (N m,n ∧ k) .
Note also that the vacancy, which is the length of the N -circle not covered by any arc is

(15) L n (k) := N -L n (k) = Pn(k) p=1 (M n-p+1:n -k) = n m=1 (N m,n -k) + ,
summing the gaps' lengths over the gaps (with N n:nk the largest gaps size and N n-Pn(k)+1:nk the smallest gaps' size). We recover the result (i) originally due to [START_REF] Stevens | Solution to a geometrical problem in probability[END_REF] and its asymptotic consequences. The following statements are mainly due to Holst, see [START_REF] Holst | On discrete spacings and the Bose-Einstein distribution[END_REF]. It holds that (i) The distribution of P n (k) is ( 16)

P (P n (k) = p) = n p N -1 n-1 n m=p (-1) m-p n -p m -p N -mk -1 n -1 . (ii) As n, N → ∞, while n 1 -n N k → α, 0 < α < ∞ (17) P n (k) → Poi (α) ,
where Poi(α) is a random variable with Poisson distribution of parameter α.

(iii)

a. Number of gaps. As n, N → ∞ 0 while n/N → ρ, with 0 < ρ < 1, (18) 1 √
n P n (k) -n (n/N ) k d → N →∞ N 0, σ 2 = ρ k 1 -ρ k .
where N m, σ 2 stands for the normal law with mean m and variance σ 2 .

b. Gap length:

(19) 1 √ n L n (k) -N (1 -n/N ) k d → N →∞ N 0, σ 2
where

σ 2 = 1 + ρ -ρ k ρ k -(ρ + kρ) 2 ρ 2k-1 , ρ = 1 -ρ.
The proofs of (ii) and (iiib) are in [START_REF] Holst | On discrete spacings and the Bose-Einstein distribution[END_REF]. The one of (iiia) follows from similar Central Limit Theorem arguments developed there. In the first case (ii), n ∼ N 1 -α N 1/k and so n is very close to N : because of that, there are finitely many gaps in the limit and the covering probability is e -α , so macroscopic. Whereas in the second case (iii), n ∼ ρN is quite small: the number of gaps is of order nρ k and the covering probability is expected to be exponentially small. Note from (iiib) that the variance of the limiting normal law is 0 when k = 1, in accordance with the fact that L n (1) = Nn remains constant. ⋄

The number of arcs needed to cover the N -circle. In (16), P (P n (k) = 0) is the cover probability and P (P n (k) = n) the probability that no overlap of arcs or rods takes place (the hard rods model). We have

P (P n (k) = 0) = P (N n:n ≤ k) .
The cover probability P (P n (k) = 0) is also the probability that the number of arcs of length k (the sample size), say N (k), required to cover the N -circle is less or equal than n. We have N (k) = inf (n : N n:n ≤ k). In other words, P (N (k) > n) = P (N n:n > k) and so EN (k) = N n=1 P (N n:n > k), with

P (N n:n > k) = 1 N -1 n-1 n m=1 (-1) m-1 n m N -mk -1 n -1 .
We wish to estimate EN (k) as N grows large.

When

n 1 -n N k → α, so when n ∼ N 1 -α N 1/k , we have P (P n (k) = 0) = P (N (k) ≤ n) → e -α . Therefore, as N → ∞ (20) N 1/k 1 - N (k) N d → E k ,
where E k has a Weibull(k) distribution with

P (E k > x) = e -x k and E (E k ) = Γ 1 + k -1 . Thus (21) EN (k) ∼ N →∞ N 1 - Γ 1 + k -1 N 1/k + o N -1/k
is the estimated expected number of length-k arcs required to cover the N -circle.

4.

Large deviation rate functions in the thermodynamical limit: Hard rods, covering and parking configurations k-Hard rods configurations are those for which N 1:n > k ≥ 1 (the smallest part in the decomposition of N exceeds the arc-length k : appending an arc of length k to all sampled points does not result in overlapping of the added arcs). k-Covering configurations with k > 1 are those for which N n:n ≤ k (the largest part in the decomposition of N is smaller than arc-length k : appending an arc of length k to each sampled points results in the covering of all points of the N -circle, a connectedness property). k-Parking configurations are those for which both (N 1:n > k and N n:n ≤ 2k) (the smallest part in the decomposition of N exceeds the arc-length k and the largest part in the decomposition of N is smaller than twice the arc-length k : appending an arc of length k to all sampled points results in a hard rods configuration where sampled points are separated by gaps of length at least k but with the extra excess gaps being smaller than k, so with no way to add a new rod (or car) with size k without provoking an overlap). All these configurations are exponentially rare in the thermodynamic limit n, N → ∞ while n/N → ρ ∈ (0, 1) . We make precise this statement by computing the large deviation rate functions in each case, extending to the discrete formulation similar results obtained in the continuum, see [START_REF] Huillet | Random covering of the circle: the configuration-space of the free deposition process[END_REF].

4.1. Hard rods. k-hard rods configurations are those for which (N 1:n > k > 1) [In the partitioning approach of the fortune N amongst n recipients, this event is realized if the share of the poorest is bounded below by k, a rare event]. When the number of sampled points n is a fraction of N (the case with a density n = ρN ), there are too few sampled points for a non-overlapping configuration to occur with a reasonably large probability. Rather, one expects that the probability of nonoverlapping (hard-rods) configurations tends to zero exponentially fast. To see this, we need to evaluate the large n expansion of P (N 1:n > k). Note that the event N 1:n > k is an event with positive probability if and only if N ≥ n (k + 1) so, in the sequel, we shall assume that ρ < 1/ (k + 1), k ≥ 1. We have

P (N 1:n > k) = Z n,N k1,..,kn≥1 n m=1 1 km=N = Z n,N N -1 n-1 ∼ C n N n 1 - n N N -n Z n,N
where Z n,N = k1,..,kn≥1 n m=1 1 km>k 1 km=N . In the limit n, N → ∞ with n/N → ρ,

(22) - 1 n log P (N 1:n > k) → - 1 ρ (ρ log ρ + (1 -ρ) log (1 -ρ))+ lim n→∞ - 1 n log Z n,N .
In the limit n, N → ∞ with fixed n/N limit, the quantity P (N 1:n > k) is easier to evaluate in an isobaric ensemble where the pressure p is held fixed instead of k m . Therefore, relaxing the constraint k m = N , we shall work instead with the modified random variables N m,n , with exponentially tilted law

P N m,n = k m > k, m = 1, .., n = n m=1 1 km>k e -pkm
Z n,p .

Here . The latter equation relating p, ρ and k is an equation of state. Due to the equivalence of ensembles principle, see [START_REF] Dunlop | Hard rods: statistics of parking configurations[END_REF] for similar arguments, we have: Z n,N = e pN Z n,p O N -1/2 , leading to:

-1 n log Z n,N ∼ -1 n log Z n,p -p ρ .
Proceeding in this way, we finally get

(23) - 1 n log P (N 1:n > k) → F hr (p, ρ) = - 1 ρ (ρ log ρ + (1 -ρ) log (1 -ρ)) - p ρ -log e -p(k+1)
1e -p , with ρ ∈ (0, 1/ (k + 1)). Here, thermodynamical "pressure" p > 0 and density ρ are related through the "state equation" ∂ p F hr (p, ρ) = 0 which can consistently be checked to be (24)

1 ρ = k + 1 + e -p 1 -e -p , leading to p = -log 1-ρ(k+1) 1-ρk
> 0 (which is well-defined and positive because ρ < 1/ (k + 1)). Thus F hr is an explicit entropy-like positive function of ρ and k, namely

(25) F hr (ρ) = - 1 ρ ((1 -ρ) log (1 -ρ) -(1 -ρ (k + 1)) log (1 -ρ (k + 1)) + (1 -ρk) log (1 -ρk))
In the thermodynamical limit, hard-rods configurations are exceptional and the hard-rods large deviation rate function F hr is an explicit function of ρ and k. We conclude that with probability tending to 1, N 1:n = 1: In the partitioning approach of the fortune N amongst n recipients, the share of the poorer is the smallest possible.

As ρ ↑ 1/ (k + 1), pressure tends to ∞ and F hr (ρ) → (k + 1) log (k + 1)-k log (k) > 0. As ρ ↓ 0, pressure tends to 0 and F hr (ρ) → 0. 1 km≤k e -pkm = e -p 1e -pk 1e -p n and proceeding as for the hard rods case, we easily get

- 1 n log P (N n:n ≤ k) → F c (p, ρ)
where the covering large deviation rate function is

(26) F c (p, ρ) = - 1 ρ (ρ log ρ + (1 -ρ) log (1 -ρ)) - p ρ -log e -p 1 -e -pk 1 -e -p .
Here, thermodynamical pressure p and density ρ ∈ (1/k, 1) are related through the covering state equation

∂ p F c (p, ρ) = 0, namely (27) 1 ρ = 1 + e -p 1 -e -p - ke -pk 1 -e -pk .
For all finite arc-length k, k-covering configurations are also exceptional. The k-covering large deviation rate function F c is in general an implicit function of ρ and k, ρ ∈ (1/k, 1) . When ρ ↓ 1/k, pressure tends to -∞ and F c (ρ) → k log k -(k -1) log (k -1) > 0. As ρ ↑ 1, pressure tends to ∞ and F c (ρ) → 0. By continuity, there is a value of ρ 0 inside the definition domain of ρ where p = 0. We have

F c (p, ρ 0 ) = -1 ρ 0 (ρ 0 log ρ 0 + (1 -ρ 0 ) log (1 -ρ 0 )) -log k.
In the partitioning approach of the fortune N amongst n recipients, the share of the richest is bounded above with probability tending to 0 exponentially fast.

Remark: When k = 2, the covering equation of state can be solved explicitly because it boils down to a second degree equation in e -p . One finds p =log 1-ρ 2ρ-1 . Plugging in this expression of p in F c (p, ρ) with k = 2 gives

F c = - 1 ρ (2ρ log ρ -(2ρ -1) log (2ρ -1)) ,
an explicit function of ρ ∈ (1/2, 1) . Note that p ↑ ∞ as ρ ↑ 1, p ↓ -∞ as ρ ↓ 1/2 and p = 0 when ρ = 2/3. We have F c (p, 2/3) = 3 2 log 3 -2 log 2.

4.3. Parking configurations. Parking configurations are those for which we have (N 1:n > k, N n:n ≤ 2k) . In the partitioning approach of the fortune N amongst n recipients, this event is realized if the share of the richest is bounded above by twice the share of the poorest. Assume n, N → ∞ with n/N → ρ ∈ (1/ (2k) , 1/ (k + 1)).

One expects that the probability of k-parking configurations tends to zero exponentially fast. Working now with

Z n,p = k1,..,kn≥1 n m=1
1 k<km≤2k e -pkm = e -p(k+1) 1e -pk 1e -p n and proceeding as for the hard rods case, we easily get

- 1 n log P (N 1:n > k, N n:n ≤ 2k) → F π (p, ρ)
where the parking large deviation rate function is (28)

F π (p, ρ) = - 1 ρ (ρ log ρ + (1 -ρ) log (1 -ρ)) - p ρ -log e -p(k+1) 1 -e -pk 1 -e -p .
Here, thermodynamical pressure p and density ρ ∈ (1/k, 1) are related through the parking equation of state

∂ p F π (p, ρ) = 0, namely (29) 1 ρ
= k + 1 + e -p 1 -e -p - ke -pk 1 -e -pk .
The parking configurations large deviation rate function F π is an implicit function of ρ and k with ρ ∈ (1/ (2k) , 1/ (k + 1)) . The latter formula can be extended to the border case k = 1. Indeed, when k = 1, ρ = 1/2, pressure tends to ∞ and F π (p, ρ) = 2 log 2. From Stirling formula, this is in agreement with the fact

P (N 1:n > 1, N n:n ≤ 2) = N -1 n-1 -1 = 0 only if N = 2n,
which is the probability of the regular configuration where the n sampled points are all exactly equally-spaced by two arc length units.

Remark: When k = 2, the parking equation of state can be solved explicitly to give p =log 1-3ρ 4ρ-1 . Plugging in this expression of p into F π (p, ρ) with k = 2 gives F π as an explicit function of ρ ∈ (1/4, 1/3) . Note that p ↑ ∞ as ρ ↑ 1/3, p ↓ -∞ as ρ ↓ 1/4 and p = 0 when ρ = 2/7.

The grand canonical partition of N

Suppose N indistinguishable balls are assigned at random into N indistinguishable boxes. Let N n,N ≥ 0 be the number of balls in box number n. This leads to a random partition of N now into N id summands which are ≥ 0 :

(30) N = N n=1
N n,N .

We have (31)

P (N 1,N = k 1 , .., N N,N = k N ) = 1 2N -1 N
, which is a Bose-Einstein distribution on the full N -simplex:

k n ≥ 0 satisfying N n=1 k n = N .
Summing over all the k n but one, the marginal distribution of N 1,N is easily seen to be (32)

P (N 1,N = k) = 2N -k-2 N -k 2N -1 N
, k = 0, .., N.

Let P N = N n=1 1 (N n,N > 0) count the number of summands which are strictly positive (the number of non-empty boxes). With k m ≥ 1 satisfying

n m=1 k m = N , we obtain (33) P (N 1,N = k 1 , .., N n,N = k n ; P N = n) = N n 2N -1 N
, which is independent of the filled box occupancies (k 1 , .., k n ) (the probability being uniform).

As there are N -1 n-1 sequences k m ≥ 1, m = 1, .., n satisfying n m=1 k m = N , summing over the k m ≥ 1, we get the hypergeometric distribution for P N :

(34)

P (P N = n) = N n N -1 n-1 2N -1 N , n = 1, .., N.
This distribution occurs in the following urn model: Draw N balls without replacement from an urn containing 2N -1 balls in total, N of which are white, N -1 are black. The law of P N describes the distribution of the number of white balls drawn from the urn. Its mean is N 2 / (2N -1) ∼ N/2 and its variance is

N 2 (N -1) / 2 (2N -1) 2 ∼ N/8.
As a result, (35)

P (N 1,N = k 1 , .., N n,N = k n | P N = n) = 1 N -1 n-1 1 (|k| = N )
which is the spacings conditional Bose-Einstein model with k ≥ 1 described in [START_REF] Darling | On a class of problems related to the random division of an interval[END_REF].

The balls in boxes model just defined is therefore an extension of the conditional Bose-Einstein model allowing the number of sampled points to be unknown and random.

Repetitions (grand canonical). It is likely that some boxes contain the same number of particles. To take these multiplicities into account, let A i,N , i ∈ {0, .., N } count the number of boxes with exactly i balls, that is (36)

A i,N = # {n ∈ {1, .., N } : N n,N = i} = N n=1 1 (N n,N = i) .
Then N i=0 A i,N = N where N i=1 A i,N = P N is the number of filled boxes and A 0,N = N -P N the number of empty ones. The joint probability of the A i,N is given by the Ewens formula (see [START_REF] Ewens | The sampling theory of selectively neutral alleles[END_REF] and [START_REF] Huillet | Sampling formulae arising from random Dirichlet populations[END_REF]) (37)

P (A 0,N = a 0 , A 1,N = a 1 , .., A N,N = a N ) = 1 2N -1 N N ! N i=0 a i ! , on the set N i=0 a i = N i=1 ia i = N.
Let us now investigate the marginal law of the A i,N . Firstly, the law of A 0,N = N -P N clearly is (38)

P (A 0,N = a 0 ) = N a0 N -1 a0 2N -1 N , a 0 = 0, .., N -1, with E (A 0,N ) ∼ N/2. Secondly, recalling A i,N = N n=1 1 (N n,N = i) , with (
N ) l := N (N -1) .. (Nl + 1), using the exchangeability of (N 1,N , .., N N,N ), the probability generating function of A i,N (i = 0) reads

E z Ai,N = 1 + l≥1 (z -1) l l! (N ) l P (N 1,N = .., N l,N = i) . Using P (N 1,N = k 1 , .., N l,N = k l ) = 2N -l-l 1 km-1 N -l-1 / 2N -1 N -1 , we get the falling factorial moments of A i,N as (39) m l,i (N ) := E (A i,N ) l = (N ) l 2N -l -li -1 N -l -1 / 2N -1 N -1 , where l ∈ {0, .., l (i) = (N -1) ∧ [N/i]} . The marginal distribution of A i,N is thus (40) P (A i,N = a i ) = l(i) l=ai (-1) l-ai l! l a i m l,i (N ) , a i ∈ {0, .., l (i)} . If l = 1, E (A i,N ) = N 2N -i-2 N -2 / 2N -1 N -1 . The variance of A i,N is σ 2 (A i,N ) = m 2,i (N ) + m 1,i (N ) -m 1,i (N ) 2 .
In particular, we find that E (A 1,N ) = N (N + 1) / (2 (2N + 1)) ∼ N/4 is the mean number of singleton boxes in the grand canonical model: when N is large, about one fourth out of the N boxes is filled by singletons (recall that one half of N is filled by no ball). The variance of A 1,N is σ 2 (A 1,N ) ∼ N/4 so we expect that A 1,N , properly normalized, converges to a normal distribution. Next, we can check that E (A 2,N ) ∼ N/8 and further that E (A i,N ) ∼ N/2 i+1 , showing a geometric decay in i of E (A i,N ) .

Finally, note that the probability that A i,N takes its maximal possible value l (i) is

P (A i,N = l (i)) = m l(i),i (N ) /l (i)! = N l (i) / 2N -1 N -1 .
For example P (A 1,N = N -1) = N/ 2N -1 N -1 is the (exponentially small) probability that all N boxes are filled by singletons.

Multiplicities and conditioning.

Let us now investigate the same problem while conditioning on P N = n.

Firstly, note that N i=1 iA i,N (i) = N is the total number of balls. Using the multinomial formula, with N i=1 ia i = N and N i=1 a i = n, we thus get (41)

P (A 1,N = a 1 , .., A N,N = a N , P N = n) = N n 2N -1 N n! N i=1 a i ! and (42) P (A 1,N = a 1 , .., A N,N = a N | P N = n) = n! N -1 n-1 1 N i=1 a i ! .
The latter formulae give the joint (Ewens-like) distributions of the repetition vector count.

Let us investigate the marginal distribution of the A i,N conditional given P N = n. Firstly, the law of If l = 1, E (A i,N | P N = n) = n N -i-1 n-2 / N -1 n-1 . In particular, E (A 1,N | P N = n) = n (n -1) / (N -1) is the mean number of singleton boxes. In the thermodynamical limit n, N → ∞, n/N → ρ, E (A 1,N | P N = n) ∼ ρn and a fraction ρ of the n filled boxes is filled with singletons. For the variance, we have σ 2 (A 1,N | P N = n) ∼ ρn. We can also check that a fraction ρ (1ρ) of the n filled boxes is filled with doubletons: E (A 2,N | P N = n) ∼ ρ (1ρ) n and more generally that

A 0,N = N -P N is P (A 0,N = a 0 | P N = n) = δ a0-(N -n) . Secondly, recalling A i,N = N n=1 1 (N n,N = i) , with (n) l = n (n -
E (A i,N | P N = n) ∼ ρ (1 -ρ) i n.
Finally, note that the probability that A i,N reaches its maximal possible value l (i) is

P (A i,N = l (i) | P N = n) = m l(i),i (n, N ) /l (i)! = n l (i) / N -1 n -1 .
For example P (A 1,N = n -1 | P N = n) = n/ N -1 n-1 is the probability that n -1 boxes are filled by singletons and one box by Nn + 1 balls, which is obvious.

where H ρ (x) = ρ log ρ-x log x-(ρx) log (ρx)+x log (1µ (ρ))+(ρx) log µ (ρ) . The function x → H ρ (x) is concave and attains its maximum at x = ρ (1µ (ρ)) < 1-ρ, which is outside the integration interval [1ρ, ρ]. By the saddle point method So only in the low-density range 1 2 < ρ < 1e -1 is the graph's connectedness probability exponentially small. Note that the graph large deviation rate function F G is maximal (minimal) at ρ = 1/2 (ρ c = 1e -1 ), with F G (ρ c ) = -3-e e-1 log (e -2) > 0.

We conclude that in the random graph approach to the covering problem, in sharp contrast to the k-nearest neighbor graph, there exists a critical density ρ c = 1e -1 above which covering occurs with probability one. These results illustrate to what extent, when connections are not restricted to neighbors, the chance of connectedness is increased. This question was also raised in ( [START_REF] Cannings | Modelling protein-protein interactions networks from yeast-2-hybrid screens with random graphs[END_REF], p.18) in relation with Small-World graphs.

1 ρ

 1 constant. Defining G n,p :=log Z n,p , we have ∂ p G n,p = E N,p N m,n1Nm,n>k and one must choose p in such a way that ∂ p G n,p = N , leading to N = n k + 1 + e -p 1-e -p or = e -p 1-e -p + k + 1, so p =log 1-ρ(k+1) 1-ρk

1 / N - 1 n- 1 , 1 / N -1 n - 1 ,

 11111 1) .. (nl + 1) (and (n) 0 := 1), using the exchangeability of (N 1,N , .., N N,N ), the conditional probability generating function of A i,N readsE z Ai,N | P N = n = 1 + l≥1 (z -1) l l! (n) l P (N 1,N = i, .., N l,N = i | P N = n) . Using P (N 1,N = k 1 , .., N l,N = k l | P N = n) = N -l 1 km-1 n-l-we get the conditional falling factorial moments of A i,N as (43) m l,i (n, N ) := E (A i,N ) l | P N = n = (n) l Nli -1 nl -where l ∈ {0, .., l (i) = (n -1) ∧ [(N -1) /i]} . The conditional marginal distribution of A i,N is thus (44) P (A i,N = a i | P N = n) = l,i (n, N ) .

  →∞, n/N →ρ -1 n log P n,N (cover) = F G (ρ) := -1 ρ H ρ (1ρ) > 0.

  4.2. Covering configurations. Covering configurations are those for which we have (N n:n ≤ k) . In the partitioning approach of the fortune N amongst n recipients, this event is realized when the share of the richest is bounded above by k (a rare event). Assume n, N → ∞ with n/N → ρ ∈ (1/k, 1) where k > 1 is fixed. One also expects that the probability of covering configurations by arcs of length k tends to zero exponentially fast. Working now with

		n
	Z n,p =
	k1,..,kn≥1	m=1

Random Graph Connectivity

The latter model may be viewed as a clockwise k-nearest neighbor graph with N vertices and kn edges. Consider as before N equally spaced points (vertices) on the N -circle so with arc length 1 between consecutive points. Draw at random n ∈ {2, .., N -1} points without replacement at the integer vertices of this circle. Assume N ≤ 2n and draw an edge at random from each of the n sampled points, removing each sampled point once it has been paired. At the end of this process, we get a random graph with N vertices and n (out-degree 1) edges whose endpoints are no more neighbors, being now chosen at random on {1, .., N }. We wish to estimate the covering probability for this new model in the spirit of Erdős-Rényi random graphs.

Let B m , m = 1, .., n be a sequence of independent (but not id) Bernoulli rvs with success probabilities

which is just the probability to hit all points of the un-sampled set {n + 1, .., N } at least once in a uniform pairing without replacement of the n-sample. This covering probability is the probability of connectedness of the random graph with N vertices and n out-degree 1 edges. It is of course zero if N > 2n. Let p n = 1 n n m=1 p m be the sample mean of the Bernoulli rvs. The covering probability can be bounded by (46)

Assume n, N → ∞ while n/N → ρ so with ρ ∈ (1/2, 1) . Then → µ (ρ) and so P N (cover) → 1 if ρ ≥ ρ c := 1e -1 because in this case the probability to estimate is

with µ (ρ) ∈ 1-ρ ρ , 1 . Whereas, when ρ < 1-e -1 , the bound for the covering probability can be estimated by