Gilles Bonnet
email: gilles.bonnet@uni-osnabrueck.de

Pierre Calka
email: pierre.calka@univ-rouen.fr

Matthias Reitzner
email: matthias.reitzner@uni-osnabrueck.de

Cells with many facets in a Poisson hyperplane tessellation

Keywords: Poisson hyperplane tessellation, random polytopes, typical cell, directional distribution, Complementary Theorem, D.G. Kendall's problem, shape distribution MSC. 60D05, 52A22

Let Z be the typical cell of a stationary Poisson hyperplane tessellation in R d . The distribution of the number of facets f (Z) of the typical cell is investigated. It is shown, that under a well-spread condition on the directional distribution, the quantity n 2 d-1 n P(f (Z) = n) is bounded from above and from below. When f (Z) is large, the isoperimetric ratio of Z is bounded away from zero with high probability.

These results rely on one hand on the Complementary Theorem which provides a precise decomposition of the distribution of Z and on the other hand on several geometric estimates related to the approximation of polytopes by polytopes with fewer facets.

From the asymptotics of the distribution of f (Z), tail estimates for the so-called Φ content of Z are derived as well as results on the conditional distribution of Z when its Φ content is large.

Introduction

One of the classical models in stochastic geometry to generate a random mosaic is the construction via a Poisson hyperplane process. A Poisson hyperplane process consists of countably many random hyperplanes in R d chosen in such a way, that their distribution is translation invariant, the distribution of the direction of the hyperplanes follows a directional distribution ϕ, and the number of hyperplanes hitting an arbitrary convex set K is Poisson distributed.

Such a Poisson hyperplane process tessellates R d into countably many convex polytopes, the tiles of the mosaic. The distribution of a tile chosen at random is the distribution of the so-called typical cell Z, a random polytope.

The typical cell has been investigated intensively in the past decades, numerous papers have been dedicated to describe quantities associated with this cell, for example volume, surface area, mean width, number of facets, etc. The expected number of facets f (Z) of the typical cell and the expected volume V d (Z) are known, see e.g. the first works due to Miles [START_REF] Miles | The random division of space[END_REF][START_REF] Miles | The various aggregates of random polygons determined by random lines in a plane[END_REF] and Matheron [START_REF] Matheron | Random sets and integral geometry[END_REF] as well as Chapter 10 from the seminal book of Schneider and Weil [START_REF] Schneider | Stochastic and integral geometry. Probability and its Applications[END_REF] and the survey [START_REF] Calka | Tessellations. In New perspectives in stochastic geometry[END_REF].

But in almost all cases the distribution of these quantities is out of reach, and even good approximations are extremely difficult and unknown so far. Our main theorem fills this gap for the number of facets of Z, giving precise asymptotics for the tails of the distribution.

Theorem 1.1. There exists a constant c 1 > 0, depending on ϕ, such that for n ≥ d + 1,

P(f (Z) = n) < c n 1 n -2n d-1 .
Furthermore, there exists an integer n ϕ such that P(f (Z) = n) is either vanishing or strictly decreasing for n ≥ n ϕ .

Here and in the sequel, c i will denote a positive constant which depends on dimension d. It will be specified when it depends on ϕ or another parameter.

It is clear that in general there is no matching lower bound, for example if the directions of the hyperplane process are concentrated on a finite set. We prove that, if the directional distribution satisfies a mild condition, we have lower bounds of the same order in n as the upper bound above. In the following, we call ϕ well spread if there exists a cap on the unit sphere where ϕ is bounded from below by a multiple of the surface area measure. Theorem 1.2. Assume that ϕ is well spread. Then there exists a constant c 2 > 0, depending on ϕ, such that for n ≥ d + 1,

P(f (Z) = n) > c n 2 n -2n d-1 .
The occurring constant will be made more explicit in Section 4, in particular its dependence on the directional distribution ϕ of η.

Maybe a simple conjecture for the distribution of the number of facets f (Z) of the typical cell of a Poisson hyperplane tessellation would have been the Poisson distribution. Yet our theorem disproves this, as a more intricate conjecture we state that f (Z) follows a Compound Poisson distribution. Theorems 1.1 and 1.2 prove the asymptotic expansion ln P(f

(Z) = n) = - 2 d -1 n ln n + Θ(n)
as n → ∞ where the implicit constants in the error term Θ(n) are strictly positive. We pose it as an open problem whether ln P(f

(Z) = n) = - 2 d -1 n ln n + cn + Θ(ln n).
Support for this conjecture comes from the planar case where Calka and Hilhorst [START_REF] Calka | Random line tessellations of the plane: statistical properties of many-sided cells[END_REF] stated a more precise result if ϕ is rotation invariant. In [START_REF] Hilhorst | Heuristic theory for many-faced d-dimensional PoissonVoronoi cells[END_REF], Hilhorst investigates the similar case of the typical cell of a Poisson-Voronoi tessellation and provides heuristics for getting an analogous asymptotic expansion for the probability that the typical Poisson-Voronoi cell has n facets. He obtains as a first term -2 d-1 n ln(n), as in the present paper, but does not make the second term fully explicit (indeed, the constant c d introduced in (2.10) therein is unknown). In particular, the approximation result provided by Lemma 3.3 matches to some extent the statement (2.10) in [START_REF] Hilhorst | Heuristic theory for many-faced d-dimensional PoissonVoronoi cells[END_REF], i.e. many of the n facets of Z lie in an annulus with thickness of order n -2 d-1 multiplied by a size functional of Z. This suggests that improving Theorems 1.1 and 1.2 requires new ingredients and notably a substantial improvement of Lemma 3.3.

In the following our aim is to show that cells with many facets are far away from any lower dimensional convex body. To do this we measure the distance from the ball using the isoperimetric ratio of a convex set K. Denote by V i the i-th intrinsic volume (see Section 2.1 for the definition). For any 1 ≤ i < j ≤ d we call V j (K) 1/j V i (K) -1/i the (i, j)-isoperimetric ratio of K. The isoperimetric inequality says that this ratio is maximized precisely for balls. On the other hand when the isoperimetric ratio of K vanishes, K must be lower dimensional.

The next theorem shows that the isoperimetric ratio V j (Z) 1/j V i (Z) -1/i of the typical cell is bounded away from zero with high probability if the cell has many facets. Hence cells with many facets cannot be too elongated.

Theorem 1.3. Assume that ϕ is well spread and that 1 ≤ i < j ≤ ⌈(d -1)/2⌉. For any δ ∈ (0, 1), there exist constants ǫ and n 0 , depending on ϕ, i, j and δ such that

P V j (Z) 1 j V i (Z) 1 i < ǫ f (Z) = n ≤ δ n for all n ≥ n 0 .
To describe the distribution of the typical cell Z we need the notion of the Φcontent of a convex body K. The Φ-content measures in a certain sense the size of the convex set depending on the directional distribution ϕ of the hyperplane tessellation. It is given by

Φ(K) := S d-1 h(K, u) dϕ(u),
where h(K, u) := max{ x, u | x ∈ K} is the value of the support function of K at u. That the Φ content is an important quantity of a Poisson hyperplane process is immediately clear since the number of hyperplanes hitting an arbitrary convex set K is Poisson distributed with parameter γΦ(K). The real number γ > 0 is the intensity of the hyperplane process. In the important case where ϕ is a constant and hence the directional distribution is the uniform distribution on S d-1 , the Φ-content of a convex set K is just the well known mean width V 1 (K) of K up to a constant. For more information we refer to Section 2.1.

Again the distribution of Φ(Z) is unknown, and in this case even the expectation is out of reach. Here we succeed in computing the tail behaviour of the size-functional Φ(Z).

Theorem 1.4. There exist constants c 3 > c 4 > 0 and c 5 > 0 depending on ϕ, such that the following holds. For a > 0, we have

P(Φ(Z) > a) < exp -γa + c 3 (γa) d-1 d+1
.

Assume that ϕ is well spread. Then, for a > γ -1 c 5 , we also have

P(Φ(Z) > a) > exp -γa + c 4 (γa) d-1 d+1
.

Again we can use our bounds on the distribution of the Φ-content of the typical cell to show that big cells are not too elongated. Theorem 1.5. Assume that ϕ is well spread and that 1 ≤ i < j ≤ ⌈(d -1)/2⌉. Then for any ǫ > 0 sufficiently small we have

lim a→∞ P V j (Z) 1 j V i (Z) 1 i < ǫ | Φ(Z) > a = 0.
It is a long standing general conjecture that extremal cells of Poisson hyperplane mosaics converge to a limit shape. This question is known as Kendall's problem and has attained great interest with a large number of important contributions, see [START_REF] Kovalenko | A proof of a conjecture of David Kendall on the shape of random polygons of large area. (Russian)[END_REF] [10] [11] [12] [13] and the surveys [START_REF] Calka | Tessellations. In New perspectives in stochastic geometry[END_REF] [8] [9] [START_REF] Calka | Asymptotic methods for random tessellations[END_REF]. For a precise definition of the shape s(Z), of the cell Z we refer to Section 2.1. It turned out that many size functionals allow positive solutions of Kendall's problem, but the first intrinsic volume, the Φcontent and the number of facets resisted all attemps so far. In the contrary, Hug and Schneider [START_REF] Hug | Asymptotic shapes of large cells in random tessellations[END_REF]Thm. 4] gave an example where the shape of the cell containing the origin, i.e. the zero cell, under the condition that is has a big Φ-content does not concentrate.

Theorems 1.3 and 1.5 are first attemps to close the existing gaps. They show that the shape s(Z) of the typical cell cannot be too elongated if either the number of facets or the Φ-content is large. At a first glance they seem to be in conflict with the example given by Hug and Schneider. Yet for their example they used a measure ϕ which is concentrated on finitely many points and thus not well spread. Next we prove that their theorem holds when the zero cell is replaced by the typical cell.

Theorem 1.6. Assume ϕ is concentrated on a finite number of points, f (Z) ≤ n max with probability one. Then there is a limiting shape distribution,

lim a→∞ P(s(Z) ∈ S|Φ(Z) ≥ a) = P(s(Z) ∈ S|f (Z) = n max ).
Note that when conditioning on the number of facets f (Z), the shape s(Z) of the typical cell is independent of the size Φ(Z) (see the Complementary Theorem 2.2) and is given explicitly in Theorem 2.2.

The paper is organized as follows. In Section 2, we fix the general setting and introduce the so-called Complementary Theorem, which is a practical disintegration of the distribution of the typical cell Z. This is the fundamental probabilistic tool for showing our main results. In Section 3, we provide the required geometric ingredients which deal with the approximation of polytopes by polytopes with fewer facets. Section 4 is devoted to the proof of the main results about cells with many facets, i.e. Theorems 1.1, 1.2 and 1.3. Finally, in Section 5, we prove Theorems 1.4, 1.5 and 1.6 which deal with the big cells, i.e. with a large Φ content.

Notations and the Complementary Theorem

Setting and notations

As standard references to the following material from convex geometry we refer to the books by Schneider [START_REF] Schneider | Convex Bodies: The Brunn-Minkowski Theory[END_REF] and Gruber [START_REF] Gruber | Convex and discrete geometry, Grundlehren der Mathematischen Wissenschaften[END_REF] We work in a d-dimensional Euclidean vector space R d , d ≥ 2, with scalar product •, • , norm • and origin o. We denote by B(x, r) the closed ball and by S(x, r) = ∂B(x, r) the sphere with center x and radius r, by B d = B(o, 1) the unit ball and by S d-1 = ∂B d the unit sphere. Let H be the space of affine hyperplanes in R d with its usual topology and Borel structure. Every hyperplane H ∈ H has a unique representation

H(u, t) := {x ∈ R d : x, u = t}.
with u ∈ S d-1 and t > 0. For a given hyperplane H ∈ H, we write H -, resp. H + , for the closed halfspace with boundary H which contains, resp. excludes the origin,

H(u, t) -= {x ∈ R d : x, u ≤ t} and H(u, t) + = {x ∈ R d : x, u ≥ t}.
We denote by H := H × {±1} the space of halfspaces.

Let K be the set of convex bodies (compact convex sets of R d with non-empty interior) and denote by K o the relative interior of a set K ∈ K. We write P for the set of all polytopes, and f (P ) for the number of facets of a polytope P ∈ P. Denote by P n = {P ∈ P|f (P ) = n} the set of n-topes, hence P n ⊂ P ⊂ K. For any t > 0, and K, L ∈ K we define

tK := {tx : x ∈ K}, K + L := {x + y : x ∈ K, y ∈ L}
where the latter is the Minkowski sum of K and L.

The sets K, P, and P n are equipped with the Hausdorff distance d H ,

d H (K, L) = min{r : K ⊂ L + rB d , L ⊂ K + rB d },
and with the associated topology and Borel structure. Steiner's formula says that the volume of the Minkowski sum of K ∈ K and a ball of radius r is a polynomial in r,

V d (K + rB d ) = d i=0 κ i V d-i (K)r i
where κ i denotes the volume of the i-dimensional unit ball, and V i (K) is the i-th intrinsic volume of K. E.g., V d is the usual volume, 2V d-1 the surface area and V 1 a multiple of the mean width of K. Steiner's formula can be generalized to all intrinsic volumes,

V j (K + rB d ) = j i=0 d -j + i i κ d-j+i κ d-j V j-i (K)r i . (2.1)
The isoperimetric inequality tells us that for 1 ≤ i < j ≤ d the isoperimetric ratio is bounded,

V j (K) 1 j V i (K) 1 i ≤ κ 1 j j κ 1 i i (2.2)
with equality if and only if K is a ball. The ratio is well defined if the dimension of K is at least i and equals zero if and only if the dimension is at most (j -1). In Theorems 1.3 and 1.5 we prove that with high probability the isoperimetric ratio of the cells with many facets is bounded away from zero, thus proving that it is not too close to a (j -1)-dimensional convex body. Let η be a stationary Poisson hyperplane process in R d , that is a Poisson point process in the space H invariant under translation. We often identify a simple counting measure with its support, so that for any set A ⊂ H, both notations η(A) and |η ∩ A| denote the number of elements of η in A.

Since η is stationary, its intensity measure E η(•) decomposes into Lebesgue measure and an even probability measure ϕ on S d-1 ,

E η(•) = γµ(•) := γ S d-1 ∞ 0 1 (H(u, t) ∈ •) dt dϕ(u), (2.3)
where γ > 0 and µ is a measure on H. We call γ the intensity and ϕ the directional distribution of the hyperplane process η. We assume that the support of ϕ is not contained in a great circle of S d-1 . When ϕ is the normalized surface area measure on S d-1 , we say that η is isotropic.

The closure of each of the connected components of the complement of the union H∈η H is almost surely a polytope (because the support of ϕ is not contained in a great circle). These polytopes are the cells of the Poisson hyperplane mosaic X induced by η. We can see X as a point process in P. To describe the distribution of X we need the notion of the Φ-content of a convex body K which is given by

Φ(K) := S d-1 h(K, u) dϕ(u),
where h(K, u) := max{ x, u : x ∈ K} is the value of the support function of K at u. In the important case when ϕ is a constant and hence the directional distribution is the uniform distribution on S d-1 , the Φ-content of a convex set K is up to a constant just the first intrinsic volume V 1 (K).

We will have to replace bounds expressed in terms of the first intrinsic volume V 1 (K) by bounds expressed in terms of Φ. Because V 1 and Φ are homogeneous of degree one, and Φ is continuous and strictly positive on the compact set

{convex compact sets K ⊂ R d : V 1 (K) = 1 and o ∈ K}, we see that 0 < c Φ := sup K∈K V 1 (K)/Φ(K) < ∞. Thus for all K ∈ K, V 1 (K) ≤ c Φ Φ(K).
(2.4)

The definition of Φ is motivated by the fact that, for any K ∈ K,

P(η ∩ K = ∅) = e -γΦ(K) .
Note that Φ is homogeneous of degree 1 and translation invariant, Φ(tK + x) = tΦ(K) for any K ∈ K, t ≥ 0 and x ∈ R d . In the special case where η is isotropic, 2Φ is the so called mean width of K. Note that K ⊂ K implies that Φ(K) > 0 since K contains at least 2 points. For a set X ⊂ K of convex bodies we define

X Φ := {K ∈ X : Φ(K) = 1} ⊂ X .
Let c : K → R d be a center function, i.e. a measurable map compatible with translations and homogeneous under the scale action: c(tK + x) = tc(K) + x for any t ∈ (0, ∞) and any x ∈ R d . For example, c can be the center of mass. In this paper we assume that c(K) ∈ K for every K ∈ K and that c is 1-Lipschitz, i.e. c(K)c(L) ≤ d H (K, L) for K, L ∈ K. For a set X ⊂ K of convex bodies we define X c := {K ∈ X : c(K) = o} ⊂ X .

In particular, P c denotes the set of polytopes with center at the origin. Due to the natural homeomorphism

P → R d × P c P → (c(P ), P -c(P )) ,
we will consider from now on X as a germ-grain process in R d with grain space P c . Since η is stationary, this is also the case for X. That implies the existence of a probability measure Q on P c such that the intensity measure of the germ-grain process X decomposes into Q and Lebesgue measure λ d ,

E X({P -c(P ) ∈ C, c(P ) ∈ A}) = γ (d) λ d (A) Q(C) (2.5)
for C ⊂ P c . We call Q the grain distribution, and the constant γ

(d) = E X({P ∈ P, c(P ) ∈ [0, 1] d }) the intensity of X. It is easy to see that γ (d) is a multiple of γ d
, where γ is the intensity of the Poisson hyperplane process. A random centred polytope Z ∈ P c with distribution Q is called typical cell of X.

For K ∈ K, we define its shape to be

s(K) = 1 Φ(K) (K -c(K)).
We have that s is translation and scale invariant, i.e. for any K ∈ K, t ∈ (0, ∞) and any x ∈ R d , we have s(tK + x) = s(K).

We want to point out that in this paper the shape is not rotation invariant. We call the set K c,Φ = s(K) the shape space. Similarly we call P c,Φ = s(P) the shape space of polytopes, and P n,c,Φ = s(P n ) the shape space of n-topes. Note that, K c,Φ , P c,Φ and P n,c,Φ are compact spaces.

We have the following natural homeomorphism

h : K → R d × (0, ∞) × K c,Φ K → (c(K), Φ(K), s(K)) .
Restricting the domain of h to P n or P n,c induces the homeomorphisms h n : P → (c(P ), Φ(P ), s(P )) , and h n,c : P → (Φ(P ), s(P )) .

The measure µ given in (2.3) is by definition homogeneous and translation invariant. It gives rise to the measure μ := µ ⊗ δ on the set of halfspaces H, where δ is the counting measure on {±1}. This in turn induces naturally the measure µ n on P n via

µ n (D) := 1 n! H n 1 n i=1 H ǫ i i ∈ D dμ n (H ǫ ) , (2.6)
where μn := μ ⊗ • • • ⊗ μ denotes the product measure and

H ǫ := (H ǫ 1 1 , . . . , H ǫn n ). Note that, since D ⊂ P n , the integrand 1 ( n i=1 H ǫ i i ∈ D)
above is equal to 0 as soon as the intersection n i=1 H ǫ i i is not a polytope with n facets. Let A ⊂ R d and C ⊂ P n,c,Φ be Borel sets and b > 0. Because the measure µ n is homogeneous of degree n and translation invariant we obtain

h n (µ n ) (A × (0, b) × C) = b n h n (µ n ) (b -1 A × (0, 1) × C) = λ d (b -1 A) b n h n (µ n ) ([0, 1] d × (0, 1) × C) = λ d (A) b n-d h n (µ n ) ([0, 1] d × (0, 1) × C).
For C = P n this immediately gives the following useful lemma. Here and in the following for abbreviation we put

P [n] = i∈I H ǫ i i for H ǫ := (H ǫ 1 1 , . . . , H ǫn n ) . Lemma 2.1.
For any b > 0 and any Borel set A ⊂ R d we have

H n 1 c(P [n] ) ∈ A 1 Φ(P [n] ) < b 1 P [n] ∈ P n dμ n (H ǫ ) = λ d (A)b n-d H n 1 c(P [n] ) ∈ [0, 1] d 1 Φ(P [n] ) < 1 1 P [n] ∈ P n dμ n (H ǫ ) .
To simplify our notation we introduce on P n,c,Φ the normalized push forward measure

µ n,c,Φ (•) = h n (µ n ) [0, 1] d × (0, 1) × • = µ n h -1 n [0, 1] d × (0, 1) × • and on R + the measure λ (n) 1 (•) = ∞ 0 1(t ∈ •) nt n-1 dt,
which is homogeneous of degree n. With these notations the pushforward measure h n (µ n ) splits into the following product of measures:

h n (µ n ) = λ d ⊗ λ (n-d) 1 ⊗ µ n,c,Φ . (2.7) Because µ n,c,Φ (P n,c,Φ ) is finite, µ n,c,Φ (•)/µ n,c,Φ (P n,c,Φ
) defines a probability measure on P n,c,Φ . That all the measures mentioned in this section are connected seems already obvious. This will be made precise in the next section.

Complementary Theorem

The essential backbone of our paper is the Complementary Theorem. Similar results have been proved before, see e.g. Miles [START_REF] Miles | Poisson flats in Euclidean spaces. II. Homogeneous Poisson flats and the complementary theorem[END_REF], Møller and Zuyev [START_REF] Møller | Gamma-type results and other related properties of Poisson processes[END_REF] and Cowan [START_REF] Cowan | A more comprehensive complementary theorem for the analysis of Poisson point processes[END_REF], but for our purposes we need a very detailed description which we could not find in the literature. Therefore and for the sake of completeness we state it here explicitly and give a proof. Theorem 2.2. Let n ≥ d + 1 be an integer.

1. For any Borel set S ∈ P n,c,Φ of shapes we have

P(f (Z) = n , s(Z) ∈ S) (2.8) = γ d γ (d) (n -d)! Pn 1 c(P ) ∈ [0, 1] d 1 (Φ(P ) < 1) 1 (s(P ) ∈ S) dµ n (P ).

Proof of Theorem 2.2

The number of cells of the mosaic X in a subset D ⊂ P n is

X(D) = 1 n! H 1 ,...,Hn∈η n = ǫ∈{±1} n 1 n i=1 H ǫ i i ∈ D 1 η ∩ n i=1 H ǫ i i o = ∅ ,
because there are n! possibilities of ordering a list of n different halfspaces. The Slivnyak-Mecke formula, see e.g. [SchneiderWeil08 p.68, Corollary 3.2.3] gives for

P [n] = n i=1 H ǫ i i that EX(D) = γ n n! H n 1 P [n] ∈ D P η ∩ P o [n] = ∅ dμ n (H ǫ ) = γ n Pn 1 (P ∈ D) P (η ∩ P o = ∅) dµ n (P )
by the definition of Θ n . Because η is a Poisson process we have

P (η ∩ P o = ∅) = e -γΦ(P ) .
In the following we are interested in the case where

D = h -1 n ([0, 1] d × B × C) with Borel sets B ⊂ [0, ∞) and C ⊂ P n,c,Φ . By (2.7) we obtain in this case EX(h -1 n ([0, 1] d × B × C)) = γ n Pn 1(P ∈ h -1 n ([0, 1] d × B × C))e -γΦ(P ) dµ n (P ) = γ n C B [0,1] d dλ d (c) e -γt dλ (n-d) 1 (t) dµ n,c,Φ (P ). (2.9)
For the first part of Theorem 2.2, observe that by the definition (2.5) of the intensity measure Q and using (2.9) we have

P(f (Z) = n, s(Z) ∈ C) = γ (d) γ (d) λ d ([0, 1] d ) Q(P n,c ∩ s -1 (C)) = 1 γ (d) EX({P ∈ P n , c(P ) ∈ [0, 1] d , s(P ) ∈ C}) = γ n γ (d) C ∞ 0 [0,1] d dλ d (c) e -γt dλ (n-d) 1 (t) dµ n,c,Φ (P ).
Because the integration with respect to t gives (nd)!γ -(n-d) λ

(n-d) 1

([0, 1]) by elementary computations, the right hand side equals

γ d γ (d) (n -d)! µ n ({P ∈ P n , c(P ) ∈ [0, 1] d , Φ(P ) < 1, s(P ) ∈ C}).
by the definition of µ n . This proves the first part of the theorem.

Analogously, for the second part we have

P(f (Z) = n, Φ(Z) ∈ B, s(Z) ∈ C) = γ n γ (d) C B [0,1] d dλ d (c) e -γt dλ (n-d) 1 (t) dµ n,c,Φ (P ) = γ n γ (d) (n -d)µ n,c,Φ (C) B e -γt t n-d-1 dt.
Thus, if we condition Z to have n facets, we have that s(Z) and Φ(Z) are independent random variables with distribution

P(s(Z) ∈ C | f (Z) = n) = µ n,c,Φ (C)/µ n,c,Φ (P n,c )
and

P(Φ(Z) ∈ B | f (Z) = n) = γ n-d (n -d -1)! B e -γt t n-d-1 dt.

Polytope approximation

In this section we provide the necessary geometric ingredients for our main results. The tools used here are from convex geometry, in particular approximation of polytopes by polytopes with fewer facets.

General approximation results for polytopes

The starting point of this subsection is [START_REF] Reisner | Dropping a vertex or a facet from a convex polytope[END_REF] from Reisner, Schütt and Werner. Our goal is to show that if a polytope P has many facets, then a good proportion of them have only a tiny influence. This will be a key ingredient to obtain a recurrence relation between the probabilities P(f (Z) = n) and P(f (Z) = n -1) in Theorem 4.1. More precisely, for I ⊂ N and a set of halfspaces H ǫ i i , i ∈ I, we define

P I := ∩ i∈I H ǫ i i .
Throughout the paper we use the notation

[n] = {1, . . . , n}.

For j ≤ n we have P [n] ⊂ P [n]\{j} . We will measure the distance between P [n] and P [n]\{i} , both with the Hausdorff distance and the difference of Φ-content. We will show in the crucial Lemma 3.3 that for a subset J ⊂ [n] of size at least n/4 we have good upper bounds of the distances between P [n] and P [n]\{j} for j ∈ J. We first present Lemmata 3.1 and 3.2 which are adaptations of results from [START_REF] Reisner | Dropping a vertex or a facet from a convex polytope[END_REF].

Lemma 3.1. There exists a constant c 6 > 1, independent of d, such that the following holds. For any integer m > c

(d-1)/2 6
and any K ⊂ K, there exists a polytope Q ⊃ K with m facets such that

d H (K, Q) < c 6 c Φ Φ(K)m -2 d-1 .
Proof. This is an immediate consequence of Corollary 2.8. of [START_REF] Reisner | Dropping a vertex or a facet from a convex polytope[END_REF] which says that

d H (K, Q) < c 6 R(K)m -2 d-1
where R(K) is the circumradius of K, i.e. the radius of the smallest ball containing the convex body K. The lemma follows from

V 1 (K) ≥ V 1 ([o, R(K)u]) = R(K)
and (2.4).

The next lemma shows that if the convex body itself is a polytope P [n] = ∩ n i=1 H - i , then Q can be taken as the intersection P I of suitable supporting halfspaces of P [n] . Its proof is similar to the proof of Lemma 4.3 in [START_REF] Reisner | Dropping a vertex or a facet from a convex polytope[END_REF]. Lemma 3.2. There exist constants c 7 and c 8 > 0, such that the following holds. For any integer k > c 7 and any simple polytope P [n] with n facets, there exists a subset

I ⊂ [n] with |I| ≤ k such that d H (P [n] , P I ) < c 8 c Φ Φ(P [n] )k -2 d-1 .
Proof. We set c 7 := d(c 6 + 1) where c 6 is the constant of Lemma 3.1. We apply Lemma 3.1 to P [n] and m = ⌊k/d⌋ > c

(d-1)/2 6
. We obtain a polytope Q ⊃ P [n] with ⌊k/d⌋ facets and

d H (P [n] , Q) < c 6 c Φ Φ(P [n] ) k d -2 d-1 < c 8 c Φ Φ(P [n] )k -2 d-1 .
By eventually shifting and rotating the facets of Q slightly, we can assume that each of the facets of Q meets exactly one vertex of P [n] in its interior. Let I be the set of indices of facets of P [n] with one vertex in a facet of Q. Since P [n] is simple, we have

|I| ≤ d f (Q) = d k d ≤ k.
Finally, we observe that

P [n] ⊂ P I ⊂ Q, which implies d H (P [n] , P I ) ≤ d H (P [n] , Q).
The crucial step is to prove that also the Φ-content between P [n] and P [n]\{j} is almost the same for j ∈ I. Lemma 3.3. There exist constants c 9 and c 10 such that the following holds. For any n > c 9 and any simple polytope P [n] = ∩ n i=1 H - i with n facets, there exists a subset J ⊂ [n] of cardinality at least n/4 such that for any j ∈ J we have

d H P [n] , P [n]\{j} < c 10 c Φ Φ(P [n] )n -2 d-1 , (3.1)
and Φ P [n]\{j} < exp c 10 c Φ n -d+1 d-1 Φ(P [n] ). (3.2)
Proof. The first part is just a suitable reformulation of Lemma 3.2. Set c 9 := 2c 7 +4, and put k = n -2⌈n/4⌉ which implies k ≥ c 7 . By Lemma 3.2 there is a set I ⊂ {1, . . . , n} of cardinality k such that

d H (P [n] , P I ) < c 8 c Φ Φ(P [n] )k -2 d-1 ≤ (4d) -1 c 10 c Φ Φ(P [n] )n -2 d-1
for a suitable constant c 10 by the definition of k. Hence for any j / ∈ I, )n -2/(d-1) and

d H P [n] , P [n]\{j} ≤ d H P [n] , P I < (4d) -1 c 10 c Φ Φ(P [n] )n -2 d-1 (3.
U j = cl{u ∈ S d-1 : h(P [n]\{j} , u) = h(P [n] , u)}.
Equation (3.3) implies that, for any j / ∈ I and u ∈ S d-1 , we have

0 ≤ h(P [n]\{j} , u) -h(P [n] , u) ≤ δ1(u ∈ U j ).
Therefore,

Φ(P [n]\{j} ) -Φ(P [n] ) = S d-1 h(P [n]\{j} , u) -h(P [n] , u) dϕ(u) < U j δ dϕ(u) = δϕ(U j ). (3.4)
We need to estimate the ϕ-measure of the set U j . Denote by v 1 , . . . v m the vertices of the polytope P . Since the polytope is simple, each vertex is the intersection of precisely d hyperplanes. Denote by N(v l ) the unit vectors in the normal cone of P at v l , i.e.

N(v l ) = {u ∈ S d-1 : h(P [n] , u) = v l • u}.
The essential observation is that

U j = v l ∈H j N(v l ).
Observe that the sets N(v l ) have pairwise disjoint interiors and cover S d-1 . Thus for almost all u ∈ S d-1 we have

n j=1 1(u ∈ U j ) = n j=1 m l=1 1(v l ∈ H j )1(u ∈ N(v l )) = m l=1 1(u ∈ N(v l )) =1 n j=1 1(v l ∈ H j ) =d = d
This yields n j=1 ϕ(U j ) = d and in particular

j / ∈I ϕ(U j ) ≤ d.
This implies that, for at least half of the j / ∈ I, we have

ϕ(U j ) ≤ d n -k 2 -1 = d n 4 -1 ≤ 4dn -1 .
Otherwise we would have at least half of the j / ∈ I with the reverse inequality and, because |I| = k = n -2⌈n/4⌉, that would imply

d ≥ n j / ∈I ϕ(U j ) > 1 2 (n -k) 2d n -k = d.
Combined with equation (3.4), it shows that there exists a set J ⊂ {1, . . . , n} \ I of cardinality (nk)/2 = ⌈n/4⌉ such that, for any j ∈ J, we have

Φ(P [n]\{j} ) -Φ(P [n] ) < 4dδn -1 = c 10 c Φ n -d+1 d-1 Φ(P [n] ).
This implies equation (3.2).

Approximation with elongation condition

The starting point of the following considerations is Theorem 1.1 of [START_REF] Bonnet | Polytopal approximation of elongated convex bodies[END_REF]. For 1 ≤ i < j ≤ d and ǫ > 0, we say that a convex body K is (ǫ : i, j)-elongated when

V j (K) 1/j V i (K) -1/i < ǫ.
When a convex body, or more specifically a polytope, is sufficiently elongated, the approximation results of the previous subsection can be improved.

Lemma 3.4. Assume that 1 ≤ i < j ≤ ⌈(d -1)/2⌉. There exist positive constants c 11 and c 12 , both depending on i, j and d, such that the following holds. For any ǫ > 0, any integer k ≥ ⌊c 11 ǫ -(d-2) ⌋ and any simple polytope

P [n] = ∩ n i=1 H ǫ i i ∈ P n with n ≥ k facets and V j (P [n] ) 1/j V i (P [n] ) -1/i < ǫ, there exists a subset J ⊂ [n] with |J| ≤ k, such that d H (P [n] , P J ) < c 12 ǫ 1 2d V 1 (P [n] )k -2 d-1 .
Proof. This is a useful application of a recent result by Bonnet [START_REF] Bonnet | Polytopal approximation of elongated convex bodies[END_REF]. Assume 1 ≤ i < j ≤ ⌈(d -1)/2⌉. Then there exist constants c i,j and n i,j (both depending on d), such that the following holds. For any ǫ > 0, any m ≥ n i,j ǫ -(d-2) , and any convex body K with V j (K)

1 j V i (K) 1 i < ǫ,
there exists a polytope Q ⊃ K with at most m facets satisfying 2) . Then there exists a polytope Q ⊃ P [n] with m + 1 facets and

d H (K, Q) < c i,j ǫ 1 2d V 1 (K) m -2 d-1 . Assume that P [n] is a simple polytope with isoperimetric ratio V j (P [n] ) 1/j V i (P [n] ) -1/i < ǫ and f (P [n] ) = n > k ≥ dm facets with m = ⌊k/d⌋ > n i,j ǫ -(d-
d H (P [n] , Q) < c i,j ǫ 1 2d V 1 (P [n] ) (m + 1) -2 d-1 ≤ d 2 d-1 c i,j ǫ 1 2d V 1 (P [n] ) k -2 d-1 .
We can assume that each of the facets of Q meets exactly one vertex of P [n] in its interior. Let J be the set of indices of facets of P [n] with one vertex in a facet of Q.

Since

P [n] is simple, we have |J| ≤ d f (Q) ≤ k.
And

P J ⊂ Q implies d H (P [n] , P J ) ≤ d H (P [n] , Q).
In the following lemma we prove the uniform continuity of the isoperimetric ratio. To our surprise we could not find any results in this direction, this seems to be an open problem. We state the partial solution to this problem which we need for our purposes. Lemma 3.5. Let 1 ≤ i < j ≤ d. There exists a constant c 13 such that for any δ ∈ (0, 1) and for any K, L ∈ K with K ⊂ L and d H (K, L) < δV 1 (K), we have 1) .

V j (L) 1 j V i (L) 1 i < V j (K) 1 j V i (K) 1 i + c 13 δ j-i ij(j-
Proof. A first easy bound is obtained using

V i (L) j-1 ≥ c ij V 1 (L) j-i V j (L) i-1
which is a consequence of the Alexandrov-Fenchel inequality, see [START_REF] Schneider | Convex Bodies: The Brunn-Minkowski Theory[END_REF], p.401, (7.66) therein.

V j (L)

1 j V i (L) 1 i ≤ c 14 V i (L) 1 i V 1 (L) j-i j(i-1) < V j (K) 1 j V i (K) 1 i + c 14 V i (L) 1 i V 1 (L) j-i j(i-1) (3.5)
A more precise bound uses Steiner's formula. Due to the isoperimetric inequality

(2.2), V i (K) 1/i ≤ c 1,i V 1 (K) with c 1,i := V i (B d ) 1/i V 1 (B d ). Since d H (K, L) < δV 1 (K),
we have that L ⊂ K + δV 1 (K)B d . The monotonicity of the intrinsic volumes and Steiner's formula (2.1) shows for δ ≤ 1

V j (L) < V j K + δV 1 (K)B d ≤ V j (K) + j i=1 d -j + i i κ d-j+i κ d-j c j-i 1,j-i V 1 (K) j-i (δV 1 (K)) i ≤ V j (K) + δV 1 (K) j j i=1 d -j + i i κ d-j+i κ d-j c j-i 1,j-i ≤ V j (K) + c 15 δV 1 (L) j .
Because a + b ≤ (a

1 j + b 1 j
) j for a, b > 0, and because of the monotonicity of the intrinsic volumes this yields

V j (L) 1 j V i (L) 1 i ≤ V j (K) 1 j V i (K) 1 i + c 1 j 15 δ 1 j V 1 (L) V i (L) 1 i . (3.6)
Note that min{x, x -(j-i)/(j(i-1)) } ≤ 1 for all x > 0. We define c 13 = max{c 14 , c

1/j 15 } and combine (3.5) and (3.6).

V j (L)

1 j V i (L) 1 i ≤ V j (K) 1 j V i (K) 1 i + δ j-i ij(j-1) min    c 1 j 15 δ i-1 i(j-1) V 1 (L) V i (L) 1 i , c 14 δ i-1 i(j-1) V 1 (L) V i (L) 1 i -j-i j(i-1)    ≤ V j (K) 1 j V i (K) 1 i + c 13 δ j-i ij(j-1)
Recall that we use the notation P I = ∩ i∈I H ǫ i i , for any set of integers I. For integers k ≤ n and a permutation σ ∈ S n we write σ

[k] = {σ(i) : i ∈ [k]}. In particular P σ[k] = ∩ i∈I H ǫ σ(i)
σ(i) . We call hyperplanes H i in generic position, if the intersection of any d + 2 of them is empty. The constants c 11 and c 12 have been defined in Lemma 3.4.

Lemma 3.6.

There is a constant c 16 depending on ϕ such that for all integers i < j ≤ ⌈(d -1)/2⌉ and any ǫ < c

2/(d-1) 11 c -1
12 (c Φ ) -1 the following holds. For any polytope P [n] ∈ P n with n > m = ⌊c 11 ǫ -(d-2) ⌋ facets in generic position and

V j (P [n] ) 1/j V i (P [n] ) -1/i < ǫ there exist at least 2 -n (n -2m)! permutations σ ∈ S n such that (1) d H (P σ[k] , P σ[k-1] ) < c 16 c Φ ǫ 1 2d 4 Φ(P σ[m] )k -2 d-1 for all k = 2m + 1, . . . , n, (2) c
(P σ[n] ) -c(P σ[m] ) < Φ(P σ[n] ), and (3)
Φ(P σ[m] ) < 2Φ(P σ[n] ).
Proof. We set m = ⌊c 11 ǫ -(d-2) ⌋.

By Lemma 3.4 there exists a subset I ⊂ [n] with |I| = m, such that for all subsets J with I ⊂ J ⊂ [n] we have

d H (P [n] , P J ) < c 12 ǫ 1 2d V 1 (P [n] )m -2 d-1 < c -2 d-1 11 c 12 ǫ V 1 (P [n] ).
By Lemma 3.5 this implies for all such sets J that V j (P J )

1 j V i (P J ) 1 i < ε + c 13 (c -2 d-1 11 c 12 ǫ) j-i ij(j-1) < c 17 ǫ 1 d 3 . (3.7)
We denote by S(P [n] ) ⊂ S n the set of those permutations σ such that (a) σ[m] = I, and

(b) d H (P σ[k] , P σ[k-1] ) < 2 2 d-1 c 12 c 1 2d 17 ǫ 1 2d 4 V 1 (P σ[k] )k -2 d-1 for all k = n, . . . , 2m + 1.
To estimate |S(P

= P σ[k] , the integer k ′ = k 2 ≥ m and ǫ ′ = c 17 ǫ 1 d 3 , there is a set J k ⊂ σ[k] of size |J k | ≤ k/2 such that d H (P σ[k] , P J k ) < c 12 c 1 2d 17 ǫ 1 2d 4 V 1 (P σ[k] ) k 2 -2 d-1
.

If we choose σ(k) / ∈ J k , Condition (b) is thus satisfied. Because we need in addition σ(k) / ∈ I there are at least k/2-m possibilities to choose σ(k), and thus to determine σ[k -1]. Continuing until k = 2m + 1 gives at least n 2m+1 (k/2m) possibilities to choose σ(n), . . . , σ(2m + 1). We obtain

|S(P [n] )| ≥ m! n k=2m+1 k 2 -m = m!2 -n+2m (n -2m)! > 2 -n (n -2m)! Using (2.
Φ(P σ[m] ) < Φ(P σ[n] + Φ(P σ[n] )B d ) < 2Φ(P σ[n]
).

Cells with many facets

The aim of this section is to show how Theorem 2.2, combined with the geometric arguments developed in Section 3, implies our main results, i.e. Theorems 1.1, 1.2 and 1.3. To do so, we start by presenting the three intermediary results that will play a key role in the proofs of these theorems. By seeing a polytope with n facets as a polytope with (n -1) facets cut 'a little bit' by one halfspace, we obtain the following recurrence relation.

> (c 18 c Φ ) d/2 , P(f (Z) = n) ≤ c 19 c Φ n -2 d-1 P(f (Z) = n -1) and c 19 c Φ n -2/(d-1) < 1, where c Φ is defined in (2.4).
The next theorem provides an upper-bound for the probability of the same event {f (Z) = n} intersected with the event of being (ǫ : i, j)-elongated. Let c 11 , c 12 , and c Φ be the constants used in Lemma 3.6. 12 (c Φ ) -1 we have

P f (Z) = n, V j (Z) 1 j V i (Z) 1 i < ǫ < γ d γ (d) e c 21 ǫ -2(d-1) (c 22 ǫ 1 2d 4 ) n n -2n d-1 for n > ⌊c 11 ǫ -(d-2) ⌋ 2 .
As we will see, the bound in Theorem 4.2, i.e. when we add the condition that the isoperimetric ratio is small, is close to the one that we will get when iterating Theorem 4.1 but with a constant in front of n -2n d-1 which is arbitrarily small. The last theorem deals with the lower-bound for P (f (Z) = n). This requires an extra-condition on the directional distribution ϕ. Recall that we call ϕ well spread if there exists a cap on the unit sphere where ϕ is bounded from below by a multiple of the surface area measure. We denote by H d-1 (•) the (d -1)-dimensional Hausdorff measure, the surface area. We will prove a slightly more precise form of Theorem 1.2 Theorem 4.3. There exist constants c 23 > 0, c 24 ∈ N, independent of ϕ, such that the following holds. Assume that ϕ is well spread. In particular assume that there exists a cap C ⊂ S d-1 of radius r ∈ (0, 1) and a constant c 25 with ϕ(•) > c 25 H d-1 (•) on C. Then, for n ≥ c 24 , we have

P(f (Z) = n) > γ d γ (d) (c 25 c 23 r d+2 ) n n -2n d-1 .
In the next subsection, we show how to deduce in a very small number of steps our main results from the three theorems above. The rest of Section 4 is devoted to the proof of Theorems 4.1, 4.2 and 4.3.

P(f (Z) = n) ≤ (c 19 c Φ ) n-n 0 n! n 0 ! -2 d-1
. Now Stirling's approximation n! > n n e -n implies for any n ≥ n 0 ,

P(f (Z) = n) < (c 19 c Φ ) -n 0 (n 0 !) 2 d-1 (e 2 d-1 c 19 c Φ ) n n -2n d-1
which implies Theorem 1.1.

Taking

c 2 = min(1, γ d γ (d) )
P V j (Z) 1 j V i (Z) 1 i < ǫ f (Z) = n ≤ c 28 (ǫ) (c 27 ǫ 1 2d

Proof of Theorem 4.1

We first need to state the following elementary but useful lemma. We denote by S n the set of permutations of [n]. For x = (x 1 , . . . , x n ) and σ ∈ S n , we write x σ := (x σ(1) , . . . , x σ(n) ). It is clear that the following holds.

Lemma 4.4. Let (X, Σ, ψ) be a measured space, m, n > 0 be integers, f : X n → [0, ∞) be a measurable function and S, T ⊂ X n measurable sets. Assume that

• f is symmetric: for any σ ∈ S n and any x ∈ X n , we have f (x σ ) = f (x);

• S is symmetric: for any σ ∈ S n , and any x ∈ X n we have 1(x σ ∈ S) = 1(x ∈ S);

• for any x ∈ S, there exist at least p permutations σ ∈ S n such that x σ ∈ T .

Then p n! X n 1(x ∈ S)f (x) dψ n (x) ≤ X n 1(x ∈ T )f (x) dψ n (x) .
The next lemma deals with the measure of those polytopes P [n] which are close to P [n-1] in the Hausdorff distance.

Lemma 4.5. For any ε > 0 and any measurable function f : H n-1 → (0, ∞), it holds that

H n 1 P [n] ∈ P n 1 d H (P [n] , P [n-1] ) < ε f (H ǫ 1 1 , . . . , H ǫ n-1 n-1 ) dμ n (H ǫ ) < ε H n-1 1 P [n-1] ∈ P n-1 f (H ǫ ) dμ n-1 (H ǫ ) . (4.1)
Proof. In this particular proof, we use the following representation of half-spaces: for any u ∈ S d-1 and t ∈ R, we denote by

H(u, t) = {x ∈ R d : x, u ≤ t} so that μ(•) = S d-1 R 1 H(u, t) ∈ • dt dϕ(u).
For any K ∈ K, we now proceed with the following calculation:

H 1 (K ∩ H n = ∅) 1 (d H (K, K ∩ H ǫn n ) < ε) dμ(H ǫn n ) = S d-1 R 1 (K ∩ H(u, t) = ∅) 1 d H (K, K ∩ H(u, t)) < ε) dt dϕ(u) ≤ S d-1 h(K,u) h(K,u)-ε dt dϕ(u) = ε. (4.2)
Let us fix now H ǫ ∈ H n-1 . We observe that for every H ǫ n ∈ H,

1 P [n] ∈ P n 1 d H (P [n] , P [n-1] ) < ε ≤ 1 P [n-1] ∈ P n-1 1 P [n-1] ∩ H n = ∅ 1 d H (P [n-1] , P [n-1] ∩ H ǫn n ) < ε . (4.3)
Integrating (4.3) over H ǫn n ∈ H and combining it with (4.2) applied to K = P [n-1] , we obtain

H 1 P [n] ∈ P n 1 d H (P [n] , P [n-1] ) < ε dμ(H ǫn n ) ≤ ε1 P [n-1] ∈ P n-1 .
We conclude by multiplicating the previous inequality by f (H ǫ 1 1 , . . . , H

ǫ n-1
n-1 ) and integrating it with respect to (H ǫ 1 1 , . . . , H

ǫ n-1 n-1 ) ∈ dμ n-1 (H ǫ ).
We are now in the position to prove Theorem 4.1. Set α = c 10 c Φ n -2/(d-1) , and set

I n = γ (d) γ d n! (n -d)! P(f (Z) = n).
By (2.6) and (2.8), we have

I n = H n 1 P [n] ∈ P n 1 c(P [n] ) ∈ [0, 1] d 1 Φ(P [n] ) < 1 dμ n (H ǫ ) ,
where

P [n] = ∩ n i=1 H ǫ i i .
We want to use now Lemma 3.3 which, roughly speaking, tells us that the variable H n has a 'small influence'. Set S = {(H, ǫ) ∈ H n : ∩ n i=1 H ǫ i i ∈ P n is a simple polytope}, and

T = {(H, ǫ) ∈ S : d H P [n] , P [n-1] < αΦ(P [n] ), Φ P [n-1] < exp αn -1 Φ(P [n] )}.
Lemma 3.3 tells us that, for any (H, ǫ) ∈ S, there exists at least n!/4 permutations σ ∈ S n such that (H, ǫ) σ ∈ T . Hence, Lemma 4.4 and the Lipschitz continuity of c imply

I n 4 ≤ H n 1 P [n] ∈ P n 1 c(P [n] ) ∈ [0, 1] d 1 d H P [n] , P [n-1] < α 1 Φ P [n-1] < exp αn -1 dμ n (H ǫ ) ≤ H n 1 P [n] ∈ P n 1 c(P [n-1] ) ∈ [-α, 1 + α] d 1 d H P [n] , P [n-1] < α 1 Φ P [n-1] < exp αn -1 dμ n (H ǫ ) .
Now, using consecutively Lemma 4.5 and Lemma 2.1 applied to an (n -1)-fold integral, we obtain that

I n 4 ≤ α H n-1 1 P [n-1] ∈ P n-1 1 c(P [n-1] ) ∈ [-α, 1 + α] d 1 Φ P [n-1] < exp αn -1 dμ n-1 (H ǫ ) ≤ α(1 + 2α) d exp α(n -1 -d)n -1 • H n-1 1 P [n-1] ∈ P n-1 1 c(P [n-1] ) ∈ [0, 1] d 1 Φ P [n-1] < 1 dμ n-1 (H ǫ ) ≤ α(1 + 2α) d exp α 1 - d + 1 n I n-1 .
Therefore,

P(f (Z) = n) ≤ 4α(1 + 2α) d exp α 1 - d + 1 n (n -d) n P(f (Z) = n -1) ≤ 4α exp 2dα + α 1 - d + 1 n P(f (Z) = n -1).
This proves that for n > c 9 , we have

P(f (Z) = n) < 4α exp{3dα}P(f (Z) = n -1).
Set c 19 := 4e 3d c 10 and recall that α = c 10 c Φ n -2/(d-1) . Theorem 4.1 follows for c 10 c Φ n -2/(d-1) < 1, since in that case 4αe 3dα ≤ 4αe 3d = c 19 c Φ n -2/(d-1) .

Proof of Theorem 4.2

We will proceed in a similar way as in the proof of Theorem 4.1 with one main difference: in order to take into account the elongation condition, we will use Lemma 3.6 instead of Lemma 3.3. In particular, Lemma 3.6 does not guarantee that there is a permutation σ such that the condition on the isoperimetric ratio

V j (P [n] ) 1 j V i (P [n] ) 1 i < ǫ
is satisfied by P σ[n-1] so there is no possibility to apply it more than once. This explains why we have directly a general upper bound but not a recurrence relation similar as the one of Theorem 4. Set

I n := γ (d) γ d n! (n -d)! P f (Z) = n, V j (Z) 1 j V i (Z) 1 i < ǫ .
By (2.8), we have

I n = H n 1 P [n] ∈ P n 1 c(P [n] ) ∈ [0, 1] d 1 Φ(P [n] ) < 1 1 V j (P [n] ) 1 j V i (P [n] ) 1 i < ǫ dμ n (H ǫ ) ,
where

P [n] = ∩ n i=1 H ǫ i i .
Roughly speaking, we will now use Lemmata 4.4 and 3.6 to order the halfspaces such that integrating step by step, starting by H ǫn n , the integrals can be well bounded. Set S = (H, ǫ) ∈ H n : P [n] ∈ P n with facets in generic position, V j (P [n] )

1 j V i (P [n] ) 1 i < ǫ , and
T = (H, ǫ) ∈ H n : P [n] ∈ P n , c(P [n] ) -c(P [m] ) < Φ(P [n] ), Φ(P [m] ) < 2Φ(P [n] ), d H (P [k] , P [k-1] ) < δΦ(P [m] )k -2 d-1 for 2m < k ≤ n .
Lemma 3.6 tells us that, for any (H, ǫ) ∈ S, there exist at least 2 -n (n -2m)! permutations σ ∈ S n such that (H, ǫ) σ ∈ T . Hence, Lemma 4.4 implies

2 -n (n -2m)! n! I n ≤ H n 1 P [n] ∈ P n 1 c(P [n] ) ∈ [0, 1] d 1 Φ(P [n] ) < 1 1 c(P [n] ) -c(P [m] ) < Φ(P [n] ) 1 Φ(P [m] ) < 2Φ(P [n] ) 1 d H (P [k] , P [k-1] ) < δΦ(P [m] )k -2 d-1 for 2m < k ≤ n dμ n (H ǫ ) ≤ H n 1 P [n] ∈ P n 1 c(P [m] ) ∈ [-1, 2] d 1 Φ(P [m] ) < 2 1 d H (P [k] , P [k-1] ) ∈ (0, 2δk -2 d-1 ) for 2m < k ≤ n dμ n (H ǫ ) .
Now, using n -2m times (4.1), we have

2 -n (n -2m)! n! I n < (2δ) n-2m n! (2m)! -2 d-1 c 20 ,
where c 20 = c 20 (m, d, ϕ) is defined by

c 20 := H 2m 1 P [2m] ∈ P 2m 1 c(P [m] ) ∈ [-1, 2] d 1 Φ(P [m] ) < 2 dμ 2m (H ǫ ) . This implies for n > m 2 P f (Z) = n, V j (Z) 1 j V i (Z) 1 i < ǫ < γ d γ (d) c 20 (2δ) -2m ((2m)!) 2 d-1 n 2m-d (4δ) n (n!) -2 d-1 ≤ γ d γ (d) c 20 g(ε)f (ε) n n -2n d-1 (4.4)
where we defined

g(ε) := exp 8c 2 11 d -1 + c 11 + 1 c 16 c Φ ǫ -2(d-1)
) , and f (ε) := 4e

4 e + 2 d-1 c 16 c Φ ǫ 1 2d 4 .
The estimates in (4.4) hold because using n! < n n , (2δ) -2m ((2m)!)

2 d-1 ≤ exp 2 d -1 2m ln(2m) -2m ln(2δ) ≤ exp 8m 2 d -1 + m δ ≤ g(ε)
and, with Stirling's approximation n! > n n e -n and the inequality ln m m ≤ 1 e , we have

n 2 d-1 n 2m-d (4δ) n (n!) -2 d-1 1/n ≤ n (2m-d)/n (4δe 2 d-1 ) ≤ exp 2m ln n n (4δe 2 d-1 ) ≤ e 4 e 4c 16 c Φ ǫ 1 2d 4 e 2 d-1 = f (ε)
for n > m 2 .

Proof of Theorem 4.3

The proof of Theorem 4.3 is based on the following strategy: we construct a set of polytopes with n facets and with bounded Φ-content which we obtain by slightly perturbating a deterministic polytope which is as regular as possible. We do so in a way which ensures that Z is one of these polytopes with a high enough probability. In Lemma 4.6, we proceed with the construction of the deterministic polytope and in Lemma 4.7, we estimate the probability that Z is a perturbation of this deterministic polytope.

The arguments rely on a particular assumption on the directional distribution ϕ. A set C ⊂ S d-1 is called a cap of radius r if it is the intersection of S d-1 with a ball of radius r having its center on the sphere S d-1 . In the following we assume that ϕ is well spread and thus there is a cap C of radius r < 1 on the unit sphere and a constant c 25 with ϕ(•) > c 25 H d-1 (•).

Without loss of generality we assume that the cap is centred at the point e d = (0, . . . , 0, 1). Observe that since ϕ is an even measure it is well spread on C ∪ (-C).

We start with two lemmata. The first one essentially ensures that all polyhedra occurring in this section are contained in a big ball and hence are bounded. The second lemma constructs sets S i ⊂ H such that the outer normals of the corresponding halfspaces are in C ∪ (-C), their measure is of order O(n -d+1 d-1 ), and their intersection forms a polytope with n facets in B d . In the following we write C(y, ρ) = B(y, ρ) ∩ S d-1 for caps on the sphere. Proof. We choose a saturated packing of caps C(y i , r/12) with y i ∈ C ∪ (-C), i = 1, . . . , m. Here we call a packing saturated if there is no possibility for adding another ball of radius r/12. Since the curvature of the sphere becomes negligible when r → 0, we have that m is of the same order as a saturated packing of (d -1)dimensional balls of radius r/12 in rB d-1 . Clearly this is independent from r and therefore m < c 24 for some constant c 24 depending only on d.

This implies first that C(y i , r/6) is a covering of C ∪ (-C). Second, each cap C(z, r/4), z ∈ C contains one of the caps C(y i , r/12), because z ∈ C(y i , r/6) for some i = 1, . . . , m.

The rest of the proof follows from explicit geometric calculations. Assume in the contrary that there are

v i ∈ C(y i , r/12) ∩ (C ∪ (-C)) such that m i=1 H(v i , 1) -B(o, 4r -1 ).
This in particular implies that either

e ⊥ d ∩ v i ∈C H(v i , 1) -B(o, 4r -1 ) or e ⊥ d ∩ v i ∈-C H(v i , 1) -B(o, 4r -1 ).
Recall that C is a cap with center e d . Without loss of generality assume that x = (4r -1 , 0, . . . , 0) is a point with x = 4r -1 which is contained in v i ∈C H(v i , 1) -. Let us define x 0 = (r/4, 0, . . . , 0, 1r 2 /16). By elementary trigonometric calculations the line through x and x 0 is tangent to the sphere at x 0 . Because x is contained in H(v i , 1) -, none of the points v i may be contained the cap C x = C(e 1 , e 1x 0 ). Next observe that the point x C = ( √ 1h 2 , 0, . . . , 0, h) with h = 1r 2 /2 is on the relative boundary of C and in C x , and

x C -x 0 ≥ √ 1 -h 2 - 1 4 r ≥ 3 4 r - 1 4 r ≥ 1 2 r.
Hence C ∩ C x contains a cap of radius r/4. Yet this cap must contain one of the caps C(y i , r/12) and thus one of the v i , a contradiction.

In the following lemma we assume that there exists a cap C of radius r ∈ (0, 1) of the sphere and a constant c 25 with ϕ(•) > c 25 H d-1 (•) on C. Proof. Consider the m < c 24 caps C(y i , r/12) which have been constructed in Lemma 4.6, and fix n > c 24 . In each of the sets C(y i , r/12) ∩ (C ∪ -C) we produce an optimal packing of ⌈n/m⌉ smaller caps C(z j , ρ) where we can choose ρ such that it satisfies c 30 n -1 d-1 r ≤ ρ ≤ r 12 with a constant c 30 independent of r, n and m. Observe that the number of caps constructed in this way is between n and n + m. We choose precisely n of these caps C(z i , ρ) in such a way that in each set C(y i , r/12) ∩ (C ∪ -C) there is at least one cap C(z i , ρ).

As already used above, a cap of radius t has height t 2 /2. Let v i be arbitrary points in C(z i , ρ/2), i = 1, . . . , n. Since each cap

C v i , ρ 2 = H v i , 1 - 1 2 ρ 2 2 + ∩ S d-1
is contained in the cap C(z i , ρ), it is disjoint from all other caps C(z j , ρ), and thus also disjoint from all other caps C(v j , ρ/2). Hence for arbitrary r i with 0 ≤ r i ≤ ρ/2, all points (1r 2 i /2) v i are on the boundary of ∩ n i=1 H(v i , 1r 2 i /2) -and thus this intersection has n facets.

Since each set C(y i , r/12) contains a cap C(z i , ρ), there are m points v i , v 1 , • • • , v m say, which belong to C(y 1 , r/12), • • , C(y m , r/12) respectively. Combining Lemma 4.6 applied to v 1 , • • • , v m and the considerations above, we obtain: there are pairwise disjoint sets

T i = H(v, t) : v ∈ C z i , ρ 2 , t ∈ 1 - 1 2 ρ 2 2 , 1 ⊂ H, i = 1, . . . , n,
such that for an arbitrary n-tuple H(v i , t i ) ∈ T i , i = 1, . . . , n, we have

n i=1 H(v i , t i ) -⊂ m i=1 H(v i , t i ) -⊂ B(o, 4r -1 ) and n i=1 H(v i , t i ) -∈ P n .
We normalize such that B(o, 4r -1 ) is replaced by the unit ball and define

S i = H(v, t) : v ∈ C z i , ρ 2 , t ∈ r 4 1 - 1 2 ρ 2 2 , 1 = r 4 T i ⊂ H for i = 1, . . . , n.. The sets S i have measure at least µ(S i ) ≥ c 25 H d-1 C z i , ρ 2
rρ 2 32 ≥ c 25 c 29 r d+2 n -d+1 d-1 since ρ ≥ c 30 n -1 d-1 r
, where c 29 is a constant depending only on d. This yields n sets S i with the desired properties.

We point out that because of Lemma 4.7 and condition (4.5) therein, having

H σ(1) ∈ S 1 , • • • , H σ(n) ∈ S n for some permutation σ ∈ S n implies that Φ(∩ n i=1 H - i ) < 1, c(∩ n i=1 H - i ) ∈ B d and ∩ n i=1 H - i ∈ P n .
Using this and (2.8) yields d+1) , this implies immediately the statement of Theorem 4.3.

P(f (Z) = n) = γ d γ (d) κ d (n -d)! n! H n 1 c(∩ n i=1 H ǫ i i ) ∈ B d 1 (Φ(∩ n i=1 H ǫ i i ) < 1) 1 (∩ n i=1 H ǫ i i ∈ P n ) dμ n (H ǫ ) , ≥ γ d γ (d) κ d (n -d)! H n 1 (H 1 ∈ S 1 ) • • • 1 (H n ∈ S n ) dµ n (H) = γ d γ (d) κ d (n -d)! µ(S 1 ) • • • µ(S n ) > γ d γ (d) κ d (n -d)! c 25 c 29 r d+2 n -1-2 d-1 n for n ≥ c 24 . Stirling's approximation n! > n n e -n implies (n -d)! n n > n! n n+d > e -(d+1)n With c 23 = min 1, 1 κ d c 29 e -(

Big Cells

In this section we are interested in the behaviour of the typical cell Z when Φ(Z) tends to infinity. In particular we aim at proving results on the asymptotic behaviour of P(Φ(Z) > a) (Theorem 1.4), on the shape of such big cells in the general case (Theorem 1.5) and on the existence of a limit shape in the particular case when ϕ is concentrated on a finite set of points (Theorem 1.6).

To get Theorem 1.5, we need a new upper-bound for the probability of the event {Φ(Z) > a} intersected with the event that the cell is (ε : i, j)-elongated, which is given below. Theorem 5.1. Assume 1 ≤ i < j ≤ ⌈(d -1)/2⌉. There exist constants c 31 and c 32 , such that for any ǫ < c 31 and for any a ≥ γ -1 ε -(2d+3) , P Φ(Z) > a, V j (Z)

1 j V i (Z) 1 i < ǫ ≤ exp -γa + c 32 ǫ 1 6d 4 (γa) d-1 d+1
.

Actually, the bound in Theorem 5.1 is close to the upper-bound from Theorem 1.4 but with a constant in front of (γa) d-1 d+1 which is arbitrarily small. In the next subsection, we show how to deduce easily Theorem 1.5 from Theorems 1.4 and 5.1. The rest of Section 5 is devoted to the proof of Theorems 1.4, 5.1 and 1.6.

Deducing Theorem 1.5 from Theorems 1.4 and 5.1

Let us assume that ϕ is well spread and that 1 ≤ i < j ≤ ⌈(d -1)/2⌉. Then the lower-bound from Theorem 1.4 together with Theorem 5.1 imply that for any ǫ < c 31 and for any a ≥ γ -1 max{c 5 , ε -(2d+3) }, we have

P V j (Z) 1 j V i (Z) 1 i < ǫ | Φ(Z) > a ≤ exp c 32 ǫ 1 6d 4 -c 4 (γa) d-1 d+1 . For ǫ < c 4 c 32 6d 4
, the conditional probability above goes to zero when a goes to ∞. This shows Theorem 1.5.

Proof of Theorem 1.4

We start with three intermediary lemmas: Lemma 5.2 builds upon the Complementary Theorem to get a rewriting of the distribution tail of Φ(Z) as a function of the distribution tail of f (Z). In Lemma 5.3, we deduce from Theorems 1.1 and 1.2 respectively upper and lower-bounds for the distribution tail of f (Z). Finally, Lemma 5.4 contains analytical estimates for some subexponential power series.

In the sequel, we use the abbreviations q n := P(f (Z) = n) and r n := k≥n q k for every n ≥ (d + 1).

In the following lemma, we rewrite the probability P(Φ(Z) > a) as a power series in a.

Lemma 5.2. For every a > 0, we have

P(Φ(Z) > a) = e -γa n≥0 r n+d+1 (γa) n n!
Proof. Because of the Complementary Theorem 2.2 we have for every a > 0

P(Φ(Z) > a) = n≥d+1 q n P(Φ(Z) > a | f (Z) = n) = n≥d+1 q n ∞ a e -γt γ n-d t n-d-1 (n -d -1)! dt.
Now we recall that iterated integrations by parts show that for every n ≥ (d + 1),

∞ a e -γt γ n-d t n-d-1 (n -d -1)! dt = e -γa n-d-1 m=0 (γa) m m! .
Consequently, we obtain that

P(Φ(Z) > a) = e -γa n≥d+1 n-d-1 m=0 q n (γa) m m! = e -γa m≥0 r m+d+1 (γa) m m! , which shows Lemma 5.2.
The relation from Lemma 5.2 indicates that in order to bound P(Φ(Z) > a), we need to find bounds for r n+d+1 . This is done in the next lemma. Lemma 5.3. There exists a constant c 33 depending on ϕ such that for n ≥ 0 we have r n+d+1 < c n 33 (n!) -2 d-1 . Assume that ϕ is well spread. Then there exists a constant c 34 > 0 depending on ϕ such that for n ≥ 0 we have

r n+d+1 ≥ c n 34 (n!) -2 d-1 .
Proof. The right hand side inequality follows immediately from the following simple computations. as long as the condition x 1/α -√ 2x 1/α ≥ d+1 is fulfilled. Observe that x ≥ (3d+5) α implies x 1/(2α) ≥ √ d + 2 + 1 which in turn implies x 1/α -2x 1/(2α) + 1 ≥ d + 2 which gives the required condition.

n≥d+1 x n (n!) α < n≥0 (x 1 α ) n n! α < n≥0 (x 1 α ) n n! α = exp αx
For t ≥ 3 we have 2 ln 8 + t ≤ 1 + t + t 2 /2 ≤ e t , or equivalently -α ln 8 -1 2 ln x ≥ -1 2 αx 1 α , i.e. 8 -α x -1 2 ≥ e -1 2 αx 1/α for x 1/α ≥ e 3 . The inequality 2(3d + 5) > e 3 concludes the proof.

We are now ready to prove Theorem 1.4. Combining Lemma 5. .

The proof of the lower-bound is nearly identical and we leave the details to the reader.

Proof of Theorem 5.1

Assume 1 ≤ i < j ≤ ⌈(d -1)/2⌉. In the sequel, we use the notation q ε n := P f (Z) = n, V j (Z)

1 j V i (Z) 1 i
< ǫ and r ε n := k≥n q ε k , for every n ≥ (d + 1) and ε > 0. The proof follows along the same lines as the upper bound of Theorem 1.4 with minor adaptations. Indeed, we need some analogues to the statements of Lemmas 5.2 and 5.3 when q n is replaced by q ε n , i.e. when the extra-condition that Z is (ε : i, j)-elongated is added.

The lemma below is a rewriting of the joint distribution of (s(Z), Φ(Z)) as a power series. The proof of this result is fully analogous to that of Lemma 5.2 and is therefore omitted.

As in Lemma 5.3, we require now an upper-bound for r ε n+d+1 . Lemma 5.6. Assume 1 ≤ i < j ≤ ⌈(d -1)/2⌉. There exist constants c 31 and c 35 depending on ϕ, such that for any ǫ < c 31 we have Let us now proceed with the proof of Theorem 5.1. Applying Lemma 5.5 to the set S = {K ∈ K c,Φ : V j (Z) 1/j V i (Z) -1/i < ǫ}, we get P Φ(Z) > a, V j (Z)

1 j
V i (Z) We combine this with Lemma 5.6 to deduce P Φ(Z) > a, V j (Z)

1 i < ǫ = e -γa
1 j V i (Z) 1 i < ǫ ≤ e -γa+c

Proof of Theorem 1.6

Assume ϕ is concentrated on a finite number n max of points. Thus f (Z) ≤ n max with probability one. We use again the notation q n = P(f (Z) = n), and fix some subset S ⊂ K c,Φ of the shape space such that P(s(Z) ∈ S, f (Z) = n max ) > 0. Because of Lemma 5. where in the last equation we used again the Complementary Theorem 2.2.

2 .

 2 (Complementary Theorem) If we condition the typical cell Z to have n facets, then (a) Φ(Z) and s(Z) are independent random variables, (b) Φ(Z) is Γ γ,n-d distributed, and (c) s(Z) has probability distribution µ n,c,Φ (•)/µ n,c,Φ (P n,c,Φ ).

3 )

 3 which gives(3.1). It remains to show that, for at least half of the j not in I, equation (3.2) holds as well. Set δ = (4d) -1 c 10 c Φ Φ(P[n]

  [n] )| note first that there are m! possibilities such that σ[m] = I. Second, assume that σ(n), . . . , σ(k + 1) ∈ [n] \ I are already chosen satisfying Condition (b). Then by (3.7) and by Lemma 3.4 applied to the polytope P ′

2 2d-1 c 12 c 1 2d 17 in 2 d- 1 11c 11 c

 2172111 4), we observe that Condition (1) of our lemma is satisfied by choosing c 16 = Condition (b). Condition (2) follows from the 1-Lipschitz property of c and d H (P [n] , P σ[m] ) < c -12 c Φ Φ(P [n] )ǫ < Φ(P [n] 12 c Φ ǫ < 1. Condition (3) follows from this and the fact that

Theorem 4 . 1 .

 41 There exist constants c 18 and c 19 , independent of ϕ, such that for n

Theorem 4 . 2 .

 42 Assume 1 ≤ i < j ≤ ⌈(d -1)/2⌉. There exist constants c 20 , c 21 and c 22 , such that for any ǫ < c

4. 1

 1 Deducing Theorems 1.1, 1.2 and 1.3 from Theorems 4.1, 4.3 and 4.2 Set n 0 := ⌈(c 18 c Φ ) d/2 ⌉ where c 18 is given by Theorem 4.1. Iterating Theorem 4.1, gives us that for any n ≥ n 0 ,

1 c 24 c 4 c

 1244 25 c 23 r d+2 where c 24 , c 25 , c 23 and r are given by Theorem 4.3, we obtain Theorem 1.2. Taking c 26 = c 2/(d-1) 11 c -1 12 (c Φ ) -1 , c 27 = c 22 ǫ 1 2d 25 c 23 r d+2 and c 28 (ǫ) = e c 21 ǫ -2(d-1) , we deduce from Theorem 4.3 and Theorem 4.2, when ϕ is well spread, that

  4 ) n for any ǫ < c 26 and n ≥ max c 24 , ⌊c 11 ǫ -(d-2) ⌋ 2 . Now, choose ǫ such that c 27 ǫ 1 2d 4 = δ/2. Theorem 1.3 follows from the fact that c 28 (ǫ) δ 2 n < δ n , for n > ln(c 28 (ǫ) )/ ln(2).

1 .

 1 Let c 11 , c 12 , c 16 and c Φ be the constants used in Lemma 3.6, assume ǫ < c 2/(d-1) 11 c -1 12 (c Φ ) -1 , and set m = ⌊c 11 ǫ -(d-2) ⌋ and δ = c 16 c Φ ǫ 1 2d 4 .

Lemma 4 . 6 .

 46 There exist a constant c 24 = c 24 (d) and m = m(d, r) < c 24 points y i ∈ C ∪ (-C), i = 1, . . . , m such that the caps C(y i , r/12) are pairwise disjoint and m i=1 H(v i , 1) -⊂ B(o, 4r -1 ) for any v i ∈ C(y i , r/12) ∩ (C ∪ (-C)), i = 1, . . . , m.

Lemma 4 . 7 .

 47 There exists a constant c 29 such that the following holds. For any n > c 24 , there are disjoint subsets S 1 , . . . , S n ⊂ H withµ(S i ) > c 25 c 29 r d+2 n -d+1 d-1and for H 1 ∈ S 1 , . . . , H n ∈ S n we have i

.For≥ 1 2 .I≥ 8 -α x - 1 2 e αx 1 α

 2811 For the left hand side inequality, Hölder's inequality gives for any finite I ⊂ N\[d+1] Y a Poisson distributed random variable with mean λ it is well known, and can be proved e.g. by Chebishev's inequality, that forI = (λ -√ 2λ, λ + √ 2λ) ∩ N, we have n∈I e -λ λ n n! = 1 -P |Y -λ| ≥ √ 2λ has at most 2 √ 2λ + 1 < 4 √ λ elements, when λ ≥ 1.Putting this for λ = x 1/α into (

1 .(

 1 2 and the upperbound of Lemma 5.3, we get P(Φ(Z) > a) < e -γa n≥0 Applying now Lemma 5.4 to x = c 33 γa and α = d+1 d-1 , we obtain that P(Φ(Z) > a) < e -γa n≥0

Lemma 5 . 5 .

 55 For any measurable set of shapes S ⊂ K c,Φ and a > 0, we haveP(s(Z) ∈ S, Φ(Z) > a) = e -γa k≥d+1 P(s(Z) ∈ S, f (Z) = k) k-d-1 l=0 (γa) l l! = e -γa l≥0 P(s(Z) ∈ S, f (Z) ≥ l + d + 1) (γa) l l! .

1 2d 4 1 2d 4 ) 1 .For ǫ < c 31 we have r ε n+d+1 ≤ γ d γ (d) e c 21 ǫ - 2 e c 21 ǫ - 2 (d- 1 ) (c 22 ǫ 1 2d 4 ) n n -2n d- 1 k≥d+1

 14141221141 r ε n+d+1 < e c 21 ǫ -2(d-1) (c 35 ǫ ) n (n!) -2 d-1for n ≥ 0.Proof. Theorem 4.2 implies that for any ǫ < c2/(d-1) 11 c -1 12 (c Φ ) -1 and n > ⌊c 11 ǫ -(d-2) ⌋ 2 , q ε n < γ d γ (d) e c 21 ǫ -2(d-1) (c 22 ǫ n n -2n d-We use n -n ≤ (n!) -1 , and observe that the remaining sum is convergent and independent of n. Hence it suffices to set c 35 := c 22 max 1,

1 . 1 (c 35 ǫ 1 2d 4 1 6d 4 1 2d 4

 11141414 Lemma 5.4 ends the proof:P Φ(Z) > a, V j (Z) 1 j V i (Z) 1 i < ǫ ≤ exp -γa + d + 1 d -γa) d-1 d+1 + c 21 ǫ -2(d-1)≤ exp -γa + c 32 ǫ (γa)d-1 d+1for ε -(2d+3) ≤ γa because this implies ε -2(d+1) ≤ εγa ≤ ε γa and thus ε -2(d-1)

  [START_REF] Cowan | A more comprehensive complementary theorem for the analysis of Poisson point processes[END_REF], we haveP(s(Z) ∈ S, Φ(Z) > a) = e -γa k≤nmax P(s(Z) ∈ S, f (Z) = k) k-d-1 l=0 (γa) l l! = e -γa P(s(Z) ∈ S, f (Z) = n max ) nmax-d-1 l=0 (γa) l l! (1 + O((γa) -1 )) = P(s(Z) ∈ S, Φ(Z) ≥ a, f (Z) = n max )(1 + O((γa) -1 ))This impliesP(s(Z) ∈ S|Φ(Z) ≥ a) = P(s(Z) ∈ S, Φ(Z) ≥ a) P(Φ(Z) ≥ a) = P(s(Z) ∈ S, Φ(Z) ≥ a, f (Z) = n max )(1 + O(γa -1 )) P(Φ(Z) ≥ a, f (Z) = n max )(1 + O((γa) -1 )) = P(s(Z) ∈ S, Φ(Z) ≥ a | f (Z) = n max ) P(Φ(Z) ≥ a | f (Z) = n max ) (1 + O((γa) -1)) = P(s(Z) ∈ S|f (Z) = n max )(1 + O((γa) -1 ))

Proof. We start with the upper-bound. By Theorem 1.1 we have for n ≥ d + 1,

(5.1)

with some constant c 1 > 0 depending on ϕ. By (5.1) we have,

We use n -n ≤ (n!) -1 , and observe that the remaining sum is convergent and independent of n. Hence in order to get the upper-bound, it suffices to set

.

We assume now that ϕ is well spread and prove the lower-bound for r n+d+1 . Theorem 1.2 tells us that when ϕ is well spread, for every n ≥ 0,

Consequently, using Stirling's approximation n -n > e -n (n!) -1 and the simple inequality r n+d+1 > q n+d+1 , we get

) d+1 ), we get the required result.

The combination of the two previous lemmas implies that P(Φ(Z) > a) is well approximated by subexponential power series of type n≥0

x n (n!) α . The next lemma, which is purely analytical, investigates the behaviour of such power series. where the first inequality holds for x ≥ (2(3d + 5)) α and the second for all x > 0.


Luigi Vigneri

Thrasyvoulos Spyropoulos

Chadi Barakat

Streaming Content from a Vehicular Cloud

Keywords: Caching, Opportunistic networks, Vehicular networks, Mobile data offloading, Multimedia Streaming, Optimization

Network densification via small cells is considered as a key step to cope with the data tsunami. Caching data at small cells or even user devices is also considered as a promising way to alleviate the backhaul congestion this densification might cause. However, the former suffers from high deployment and maintenance costs, and the latter from limited resources and privacy issues with user devices. We argue that an architecture with (public or private) vehicles acting as mobile caches and communication relays might be a promising middle ground. In this paper, we assume such a vehicular cloud is in place to provide video streaming to users, and that the operator can decide which content to store in the vehicle caches. Users can then greedily fill their playout buffer with video pieces of the streamed content from encountered vehicles, and turn to the infrastructure immediately when the playout buffer is empty, to ensure uninterrupted streaming. Our main contribution is to model the playout buffer in the user device with a queuing approach, and to provide a mathematical formulation for the idle periods of this buffer, which relate to the bytes downloaded from the cellular infrastructure. We also solve the resulting content allocation problem, and perform trace-based simulations to finally show that up to 50% of the original traffic could be offloaded from the main infrastructure.

INTRODUCTION

The diffusion of low-cost handheld devices has led to a large increase in the mobile traffic demand in the past few years. Specifically, the vast majority of the traffic concerns videos, and new streaming services have been recently introduced in the market (e.g., Netflix, Amazon Prime). In practice, current and near-future architectures (e.g., 3G, LTE) cannot keep up with such increase which is already overloading the cellular infrastructure [START_REF]Cisco. Cisco visual networking index: Global mobile data traffic forecast update[END_REF]. Small cell densification has been proposed to improve the data rates and Quality of Experience (QoE) for users. While this solution decreases the load on the backbone, it actually provokes two problems: (i) small cells (SCs) require high CAPEX/OPEX costs to provide a dense enough radio access and backhaul transport network; (ii) SC deployments move the traffic overload from the core of the network to the backhaul. In order to solve (ii), several studies propose to cache popular content at the edge of the network (e.g., femtocells, picocells) [START_REF] Golrezaei | Wireless device-to-device communications with distributed caching[END_REF][START_REF] Poularakis | Video delivery over heterogeneous cellular networks: Optimizing cost and performance[END_REF]. While caching in femtocells is useful to alleviate the backhaul congestion, it requires additional installation and maintenance costs. Other studies consider using mobile user equipment (UE) as relays and storage points [START_REF] Bao | Dataspotting: Exploiting naturally clustered mobile devices to offload cellular traffic[END_REF][START_REF] Han | Mobile data offloading through opportunistic communications and social participation[END_REF]; while more affordable for an operator, this solution faces significant technology adoption concerns, as mobile devices have limited storage capacity and strict battery constraints.

In this work, we propose to use public or private transportation means (e.g., buses, cars) as data caches and mobile relays, directly accessible by nearby UE. Vehicles create a vehicular cloud controlled by mobile network operators (MNOs). End users requesting to stream a content, can download chunks of it from nearby vehicles when available, filling up their playout buffer while watching, or, alternatively, stream the video directly from the cellular infrastructure when their buffer is empty and no vehicle is in reach. We focus on streaming content because of its major contribution to Internet traffic according to recent measurement studies [START_REF]Cisco. Cisco visual networking index: Global mobile data traffic forecast update[END_REF]. Also, while the number of content in the Internet is large, content popularity is known to exhibit strong Zipfian characteristics, suggesting that reasonable hit ratios for the cloud can be achieved with moderate storage capacity per vehicle. Vehicles bring mobility for free, allowing UE to quickly browse the caches of many different encountered vehicles (while consuming the content chunks already available in their buffer, at a slower rate), thus virtually increasing the size of accessible caches.

We believe that the current infrastructure can be easily turned into a working vehicular cloud in a cost-efficient way: vehicles of all types are usually widespread in urban locations even in developing countries, and a subset of them could be readily equipped with storage capacity, wireless communication capabilities and basic computational power [START_REF]Your Car Is About To Get Smarter Than You[END_REF] at a much lower cost than SC deployments [START_REF] Nikolikj | A Cost Modeling of High-capacity LTE-advanced and IEEE 802.11ac based Heterogeneous Networks[END_REF][START_REF] Fili | The economics of small cells and wi-fi offload[END_REF]. Our solution brings a twofold benefit: on the one hand, it reduces the number of potential interruptions during playback, as future content chunks are prefetched from the cloud, when available, leading to improved QoE for the user; on the other hand, it promotes existing and new MNOs to operate in emerging markets enabling them to offer users a 3G/4G-like experience at a much lower cost.

To summarize, our main contributions in this paper are:

• We model the buffer dynamics as a queueing system, and analyse the characteristics of its idle periods (during which access to the cellular infrastructure is required). • Based on this model, we formulate the problem of optimal allocation of content in vehicles, in order to minimize the total load on the cellular infrastructure, assuming a fixed catalogue and a content popularity distribution. • We provide closed-form expressions for the optimal allocation for two interesting regimes of vehicular traffic densities, assuming a relatively generic setting. • We validate our theoretical results, using real traces for content popularity and vehicle mobility, and show that our system can offload up to 50% of streamed data in realistic scenarios, even with modest technology penetration.

The rest of the paper is organized as follows: first, in Section 2 we present the network model and the system assumptions; next, we provide closed-form expressions for optimal allocation of content in different traffic regimes in Section 3; then, we show the results of the real-trace based simulations in Section 4; finally, we list related work in Section 5, and we conclude our paper in Section 6.

SYSTEM MODEL

Architecture

In our architecture, we consider three types of nodes:

• Infrastructure Nodes (I), e.g., cellular base stations or macro-cells. These nodes are directly connected to the Internet and they can obtain any content. Their task is to fill the cloud caches with popular content, and serve requests for content not found in the cloud. • Helper Nodes (H), e.g., cars, buses, taxis, where |H| = α.

These nodes cache popular content, and have storage capacity limitations. Furthermore, we assume for simplicity that the H nodes cannot communicate with each other1 . • End Users (U), e.g., smartphones, tablets, netbooks. A content requested by a user is streamed using a playout buffer for that content in her device. Content chunks inside the playout buffer are consumed at the viewing (playout) rate rP . In parallel, whenever an H node with the watched content is encountered (referred to as a contact), subsequent chunks not already in the device buffer can be downloaded at low cost, for the duration of that contact. This download takes place at rate rV . If the buffer is (almost) empty, the U node immediately switches to the cellular interface and downloads content at a rate rC , until another vehicle storing the content is encountered. Finally, during a contact, simultaneous connections are not allowed, i.e., a U node can download from one and only one H node at a time.

Previous work has confirmed the feasibility of opportunistic connections between vehicles and UE [START_REF] Bychkovsky | A measurement study of vehicular internet access using in situ wi-fi networks[END_REF]. IEEE 802.11p [START_REF]IEEE Draft Standard for Amendment to Standard for Information Technology -Amendment 6: Wireless Access in Vehicular Environments[END_REF], which has been developed for the specific context of vehicular networks, is considered as the de facto standard. This standard actually covers simplicity (uncoordinated access mechanism, no authentication) and low delay (few hundreds ms in crowded areas). What is more, it is possible to implement a low battery consumption version in modern UEs without compromising performance [START_REF] Choi | A case for leveraging 802.11p for direct phone-to-phone communications[END_REF]. Recently, there was an increasing interest in adopting LTE to support vehicular network applications [START_REF] Araniti | Lte for vehicular networking: a survey[END_REF]. Differently from IEEE 802.11p, LTE improves performance throughput, reliability Figure 1: Sequence of contacts with three vehicles (above), and amount of data in end user buffer over time (below). When the buffer empties, the red region indicates that data are downloaded from the cellular infrastructure. and scalability at the cost of higher latency. Still, [START_REF] Kim | A Performance Evaluation of Cellular Network Suitability for VANET[END_REF] shows that LTE is capable of satisfying delay requirements for most of the vehicular applications.

In Fig. 1 we sketch the basic communication protocol: during a contact, the user can fill her buffer while streaming the video (e.g., between t1 and t2 it will download from vehicle 1); when the buffer empties (red region), the user is redirected to the cellular infrastructure. Since we assume that a U node can download content from only a single H node at a time, the user will switch to vehicle 3 only at t4, i.e., after she has finished downloading from vehicle 2.

Assumptions

We make the following system assumptions: A.1 (Download rate) -We assume rV and rC to be larger than rP in order to guarantee uninterrupted streaming2 . We assume rC is equal to rP + (where > 0 is small), in order to limit the access to the cellular infrastructure to the minimum required to ensure smooth playout (for simplicity, we will assume in our analysis that = 0). A.2 (Content popularity) -Let K be the set of content that can be requested by U nodes, such that |K| = k. Each content i ∈ K is characterized by known size si and popularity φi, namely the expected number of requests during a given time window. Similar to a number of works on edge caching [START_REF] Golrezaei | Wireless device-to-device communications with distributed caching[END_REF][START_REF] Poularakis | Video delivery over heterogeneous cellular networks: Optimizing cost and performance[END_REF], we assume this time window is a system parameter chosen by the MNO, during which estimates for the expected popularity per content are available. Every time period, the cellular operator updates its caches according to the new estimated popularity. Several studies have shown that it is possible to predict the popularity with good accuracy over relatively short periods (until few weeks for YouTube videos) [START_REF] Szabo | Predicting the popularity of online content[END_REF]. Without loss of generality, we assume content is sorted by popularity as φ1

≥ φ2 ≥ • • • ≥ φ k .
A.3 (Buffer capacity) -Each H node can store at most β bytes. While this assumption might seem to oversimplify the problem, we will show that our results can be applied to any buffer size. Moreover, we assume end user buffers to be large enough to store entirely any requested content. A.4 (Inter-contact times) -Unless otherwise stated, pairwise inter-contact times between H and U nodes are drawn from a generic distribution with rate λ, and the contact duration is drawn from a generic distribution with mean E[S].

Given the above assumptions, the result of the policy is that (i) the user's video is never interrupted provided the infrastructure can guarantee at least the playout rate (if that thus offloading some of it from the infrastructure. As long as the playout buffer remains non-empty, the infrastructure does not need to be accessed. And when it does, we ensure that the minimum necessary amount of bytes is downloaded from the infrastructure (rC = rP + ). The notation used in the paper is summarized in Table 1.

Problem formulation

Definition 1. The number of bytes downloaded from I is given by

k i=1 φ i j=1 Xij,
where Xij is a random variable corresponding to the bytes of the j th request for content i.

Conditionally on the characteristics of the content (i.e., size and popularity) Xij are IID random variables depending only on the mobility statistics (e.g., meeting rate with vehicles, contact duration). Thus, its expected value

E[Xij] is equal to E[Xij|φi, si] = E[Xi], ∀j ∈ [1, φi].
The goal of this paper is to find the optimal number of copies to allocate in H nodes in order to minimize the number of bytes downloaded from the cellular infrastructure. From Definition 1, we can derive the following theorem: Theorem 2.1 (Optimization problem). The optimal number of copies for content i (Ni ∈ N) is given by the solution of the following optimization problem: minimize

N i k i=1 φi • E[Xi], (1)
subject to 0 ≤ Ni ≤ α, i ∈ K, (2)
k i=1 siNi ≤ αβ, (3)
where the objective function is the total number of bytes downloaded from the cellular infrastructure in a given period of time. The objective function is subject to two constraints: (i) the number of replicas is limited by the number of vehicles participating in the cloud and cannot be negative (Eq. ( 2));

(ii) the buffer capacity is limited as shown in Assumption A.3 (Eq. ( 3)). Due to space limitations, all proofs can be found in a tech report, available at [START_REF] Vigneri | List of proofs for "Streaming Content from a Vehicular Cloud[END_REF], and we will provide instead only a proof sketch for a subset of results.

ANALYTICAL MODEL

In this section, we derive E[Xi] according to the vehicle density, i.e., the rate of vehicles met by U nodes, and we solve the respective optimization problem of Theorem 2.1 to find the optimal content allocation. We model the playout buffer at U nodes with a queue, where its number of "jobs" corresponds to the amount of bytes available in the playout buffer, i.e., the number of bytes prefetched from the cloud, but not yet consumed; thus, when the queue empties (idle period ), the user will switch to the cellular interface.

Low Traffic (LT)

Let us assume first that contacts with vehicles are sparse, and do not overlap with each other, i.e., a U node meets one and only one vehicle with the requested content at a time. Assume that U node is streaming content i. We can model the playout buffer for content i as a bulk G Y /D/1 queue (as shown in Fig. 2). A contact between U and a vehicle storing content i corresponds to a new (bulk) arrival in the buffer. Since there are Ni such vehicles, the total arrival rate into the queue is λNi (while the actual inter-arrival distribution is generic, G). Each arrival brings a random amount of Y new bytes to be consumed (that depends on the random contact duration with the vehicle). Finally, bytes in the buffer are served (i.e., viewed by the user) at the constant playout rate rP . We are interested in the idle periods of the queue, i.e., when the buffer is empty and the user is redirected to the cellular infrastructure. We can enunciate the following theorem:

Theorem 3.1 (Low Traffic). If λE[S]•α
1 (Low Traffic), the optimal content allocation replicates the most popular content in any vehicle, until the buffer space is filled up:

N * i = α, if 1 ≤ i ≤ γ, 0, otherwise,
where γ max{γ ∈ N| γ i=1 si ≤ β}. Sketch of proof. Since the video length is much larger than the mean contact duration, namely si/rP E[S] ∀i ∈ K, the playout queue sees several idle/busy cycles. For this reason, we can apply stationary regime analysis to the proposed queue. Specifically, the fraction of time that the G Y /D/1 queue is idle is 1 -λE[S] • rV /rP • Ni. Then, the objective function of the optimization problem is equivalent to:

min N i k i=1 φi •si(1-λE[S]•rV /rP •Ni) ≡ max N i k i=1 φi •siNi. (4)
We distinguish two cases according to the value of β: large β, when all content fits in a vehicle buffer (i.e., β ≥ k i=1 si); and small β, otherwise: • Large β: since the RHS of Eq. ( 4) is a strictly monotonic increasing function according to Ni, then N * i = α ∀i ∈ K, due to the constraint in Eq. ( 2).

• Small β: let yi siNi be the total number of bytes to allocate per content. Here, we solve a continuous relaxation for Ni. We rewrite the optimization problem as:

max y i k i=1 φiyi s.t. k i=1 yi ≤ αβ. (5)
Additionally, from Eq. ( 2) we know that yi ranges between 0 and siα. The optimization problem can be read as if we had a budget of bytes (until αβ) to use in order to maximize the objective function. We can proceed iteratively in order to find the optimal value of yi. Let > 0 be a small number of bytes ( αβ) to assign to one of the content. Initially, let further assume that yi = 0 ∀i ∈ K. An optimal solution assigns the bytes to content 1 (y1 = ), since φ1 is maximum. We iterate this step by summing the marginal budget , until one of the two following sub cases arises:

(i) y1 = siα: due to Eq. ( 2), no more bytes can be assigned to y1. In this case, the additional bytes will be assigned to y2, and so on;

(ii) k i=1 yi = αβ: there is not available space in the cloud. Then, N * i is equal to yi/si. As stated in Theorem 3.1, the optimal solution allocates copies to the content with the largest popularity.

Corollary 1. An optimal policy stores α copies for the (approximately) β/E[si] most popular content.

Corollary 2. Let βj denote the buffer capacity for vehicle j. Then, for Low Traffic, the optimal content allocation replicates the most popular content, until the buffer space is filled up. Specifically, N * i = α j=1 1A(βj), where A = {n ∈ N|n ≥ i}. If βj = β ∀j ∈ H, then the optimal allocation corresponds to Theorem 3.1.

Generic Traffic (GT)

In busy urban environments, a user might be within range of many vehicles at the same time, a number of which storing the content of interest. If a user is downloading video i from car A, and the connection is lost (e.g., car A moves away), the user could just keep downloading from another car B storing i, also in range. Hence, as long as there is at least one vehicle with a copy within range for a duration T , then the user will be downloading content i at rate rV for all of T . We are now thus interested in modelling the duration of periods with at least one vehicle with a copy in range.

Unfortunately, we cannot use the previous model here, as it assumes the absence of overlaps. In fact, an encountered car does not necessarily bring an amount of content E[S] • rV now. Consider the example above with car A and car B. When the user switches to downloading from car B, the contact with car B was already ongoing and thus does not have the same statistics as in Low Traffic regime. We choose to model these contact periods (with potential overlaps) with the busy periods of a queue with infinite servers. However, to derive the mean busy period, we have to assume that pairwise inter-contact times between users and vehicles are exponentially distributed with mean λ. While this is still subject of debate, several studies have shown that this exponential assumption is reasonable, especially in the tail of the distribution [START_REF] Conan | Characterizing pairwise inter-contact patterns in delay tolerant networks[END_REF][START_REF] Karagiannis | Power law and exponential decay of intercontact times between mobile devices[END_REF]. Thus, we model the queue as an M/G/∞ (Fig. 2), whose output is feeding arrivals into the playout buffer as described in Section 3.1. The number of vehicles simultaneously inside the end user communication range, as a function of time, corresponds to the number of jobs in the M/G/∞ queue. Specifically, arrivals describe the vehicles met by a U node, and the service time is the contact duration. We will test the model in Section 4 against a trace with non-exponential contacts. Lemma 3.2 (Busy period). Consider an M/G/∞ queue, with arrival rate λNi and mean service time E[S]. The mean busy period length is given by:

E[B] = e λE[S]•N i -1 λNi . ( 6
)
Proof. Consider the M/G/∞ queue previously described. Then, let Bn (resp. In) be the length of the n th busy (resp. idle) period. Note that (Bn, In) forms an Alternating Renewal process. We can associate to each renewal a reward which corresponds to the duration of busy periods (i.e., the time during which there is at least one job in the queue).

From the Renewal-Reward theorem [START_REF] Harchol-Balter | Performance Modeling and Design of Computer Systems: Queueing Theory in Action[END_REF], in the stationary regime, the average rate at which we earn reward is equal to the expected reward earned during a cycle, divided by the expected cycle length. It follows that, if p(t) is the probability that the server is busy at time t, then:

p(t) = E[B] E[B] + E[I] . (7)
In such M/G/∞ queue, the fraction of time that the system is busy (i.e., p(t)) is equal to 1 -e -λN i •E [S] ; this result is directly derived from the stationary probabilities of an M/M/∞, a known insensitivity result [START_REF] Newell | The M/G/∞ Queue[END_REF]. Moreover, by the Markov property of arrivals, E[I] = 1/λNi. Then, from Eq. ( 7), we deduce that As in the Low Traffic regime, we model the playout buffer with an G Y /D/1 queue. Arrivals represent the beginning of a busy period of duration given by the M/G/∞ queue. We use Corollary 3 to define the arrival rate, and E[B] • rV as mean bulk size. We introduce the following result: Theorem 3.3 (Generic Traffic). In the Generic Traffic regime, the optimal number of replicas splits content in three slots depending on the content popularity. Specifically:

E[B] = (e λN i • E[S] -1)/λNi.
N * i =      0, if φi < L (λE[S]) -1 • ln λE[S]•φ i m C , if L ≤ φi ≤ U α, if φi > U where L mC • (λE[S]) -1 and U mC • (λE[S]) -1 • e α λE[S]
, and mC is an appropriate Lagrangian multiplier. Sketch of proof. According to Lemma 3.2 and Corollary 3, we can rewrite the optimization problem as follows:

min N i k i=1 φi • sie -λE[S]•N i . ( 8
)
The problem is convex since the objective function is sum of convex functions, the constraints are linear and the domain of feasible solutions is convex. Thus, it can be solved with the method of Lagrangian multipliers [START_REF] Antoniou | Practical optimizationalgorithms and engineering applications[END_REF].

SIMULATIONS

To validate our results, we perform simulations based on real traces for (i) mobility and (ii) content popularity:

• Mobility: We use the Cabspotting trace [START_REF] Piorkowski | DAD data set epfl/mobility[END_REF] to simulate the vehicle behaviour; this trace records the GPS coordinates for 531 taxis in San Francisco for more than 3 weeks with granularity of 1 minute. In order to improve the accuracy of our simulations, we increase the granularity to 5 seconds by linear interpolation. • Content popularity: We infer the number of requests per day from a database with statistics for 100.000 YouTube videos [START_REF]YouStatAnalyzer database[END_REF]. The database includes static (e.g., title, description, author, duration) and dynamic information (e.g., daily and cumulative views, shares, comments). Data is worldwide, and we scale it linearly according to the estimated population of the centre of San Francisco.

In our simulations, we assume that end users can contact the vehicular cloud with either short (100m) or long (200m) range communications. We vary video qualities from 240p (which requires rP = 400kbps) to 1080p (rP = 4Mbps). What is more, current and near future vehicles can be equipped with 801.11 b/g/n mobile access points for wireless devices [START_REF]Sierra wireless[END_REF]. While these devices can provide much faster download rates, we set rV to 5Mbps as a pessimistic scenario. Finally, we extrapolate the mobility statistics (λ and E[S]) from the analysis of the Cabspotting trace to compute the optimal allocation. These values 3 are summarized in Table 2.

We build a MATLAB simulator as follows: first, we generate a set of requests, and we associate a random location (in GPS coordinates) to each one. The number of requests per content per day is given by the YouTube trace. Then, we store content in vehicles according to the policies shown in Section 3.1 and 3.2. For each request, we simulate the playout of the video; the end user buffer will be opportunistically filled when the vehicular cloud can be contacted, according to the mobility provided by the Cabspotting trace. In order to increase the number of simulations and to provide sensitivity analysis for content size and buffer capacity, we limit the number of content to 5000. We scale down the vehicle storage capacity β to ensure that 0,05%-1% of the total catalogue can be fit in each cache, which is an assumption that has also been used in [START_REF] Golrezaei | Wireless device-to-device communications with distributed caching[END_REF][START_REF] Maddah-Ali | Fundamental limits of caching[END_REF][START_REF] Poularakis | Video delivery over heterogeneous cellular networks: Optimizing cost and performance[END_REF]. Finally, content requests are generated over a period of 5 days. Fig. 3 shows the fraction of bytes downloaded from the vehicular cloud according to different video qualities with Low Traffic regime. The plot reveals that long range communications can reduce the mobile traffic from 30% (full HD content) to 45% (low resolution content). What is more, short range communications can also provide gains between 15% and 35%. While in this simulation we are only storing the 0,2% of the total catalogue per vehicle, considerable gains can still be achieved. Not less important is that the number of vehicles participating in the cloud is small (α = 531), 3 The values of λB and E[B] consider Ni = α. approximately less than the 1% of estimated number of vehicles in the center of San Francisco. This provides some evidence on the advantages of offloading based on a vehicular cloud, compared to offloading using small cells or WiFi with deadlines, as for example in [START_REF] Balasubramanian | Augmenting mobile 3g using wifi[END_REF] or [START_REF] Lee | An approach to model and predict the popularity of online contents with explanatory factors[END_REF]. Fig. 4 depicts the fraction of data offloaded by the vehicular cloud for two video qualities (360p and 720p) according to different values of β for GT regime. On the one hand, small vehicle caches (≤ 0, 1% of the catalogue) can provide interesting gains even for high quality videos (15-30%); on the other hand, using larger caches allows significant higher gains, up to 60% with long range communications.

Stationary regime is reasonable when the number of busy + idle periods is large enough such that the transitory phase becomes negligible. To have a high number of these periods, the average content size and the number of requests need to be large. Fig. 5 shows the fraction of data offloaded by our vehicular cloud for content of same size (with video quality 360p). We can note that when file size is larger than 100MB (≈ 15 minutes), the number of bytes downloaded from the infrastructure becomes more stable, validating the stationary regime assumption. Furthermore, with short range communications, LT and GT policies provide almost the same gain: in fact, from Table 2 we can note that the value of λB (resp. E[B]) is similar to λ (resp. E[S]), revealing a limited number of contact overlaps. Differently, for long range communications the result in the GT regime can increase the offloaded traffic up to 5% more than LT regime, confirming the validity of the exponential assumption for the mobility.

RELATED WORK

The rapid increase in the mobile traffic demand has led to a large number of proposals to alleviate the load on the backbone. Related work can be split in caching at the edge and offloading on mobile devices. In the context of caching at the edge, traditional solutions concern adding storage capacity to small cells [START_REF] Golrezaei | Wireless device-to-device communications with distributed caching[END_REF][START_REF] Poularakis | Video delivery over heterogeneous cellular networks: Optimizing cost and performance[END_REF] and/or to WiFi Access Points [START_REF] Dandapat | Sprinkler: Distributed content storage for just-in-time streaming[END_REF][START_REF] Zhang | Caching and prefetching content at the edge in the MobilityFirst future internet architecture[END_REF]. However, a large number of small cells is required for an extensive coverage, which comes at a high cost [START_REF] Alliance | NGMN 5G White Paper[END_REF]. By con- trast, in an urban environment, the same area will contain thousands of vehicles. To alleviate this situation at a low cost, a number of works introduce delayed access [START_REF] Balasubramanian | Augmenting mobile 3g using wifi[END_REF][START_REF] Lee | An approach to model and predict the popularity of online contents with explanatory factors[END_REF][START_REF] Mehmeti | Is it worth to be patient? analysis and optimization of delayed mobile data offloading[END_REF]. Differently, in our work we guarantee QoE (since we provide uninterrupted streaming) with similar or better gains in terms of data offloaded than the aforementioned works.

Apart from small cells, researchers also proposed to use mobile devices to offload content through opportunistic communications [START_REF] Bao | Dataspotting: Exploiting naturally clustered mobile devices to offload cellular traffic[END_REF][START_REF] Han | Mobile data offloading through opportunistic communications and social participation[END_REF]. These works exploit the possibility of serving user requests from other nearby mobile devices. Moreover, a few works have also suggested to exploit vehicular networks to store content [START_REF] Zhang | Roadcast: A popularity aware content sharing scheme in VANETs[END_REF][START_REF] Zhao | VADD: Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks[END_REF]. Despite the obvious limited constraints in terms of resources (e.g., battery, storage), the majority of these works does not consider a common cloud maintained by the ISP for video streaming.

CONCLUSION

In this work, we have provided a low-cost alternative to decrease the load on the cellular network. Specifically, we have proposed to cache popular multimedia content in vehicles. Users can opportunistically fill up their buffer from nearby vehicles, in a transparent way, while streaming the requested content. We have modelled the user playout buffer with a queueing approach, and provided closed-form expressions for different vehicle densities. Finally, we have validated our results with real-trace based simulations. As future work, we will evaluate how the mobility patterns affect the system and if they can be used to improve performance. We also plan to study the transient phase of our queuing system.

Figure 2 :

 2 Figure 2: Queuing model proposed for generic traffic regime.

Corollary 3 .

 3 Consider the M/G/∞ queue of Lemma 3.2. Then, its busy periods are generic distributed with mean λB • Ni, where λB λ • e -λE[S]•N i .

Figure 3 :

 3 Figure 3: Data offloaded for different video quality (β = 0, 2%) for LT regime.

Figure 4 :

 4 Figure 4: Data offloading gain with short (left) and long (right) range communications for GT regime.

Figure 5 :

 5 Figure 5: Data offloaded vs content size (video quality 360p).

Table 1 :

 1 Notation used in the paper.

	α	Number of vehicles
	β	Buffer size per vehicle
	si	Size of content i
	φi	Number of requests for content i
	Ni	Number of copies stored for content i
	k	Number of content in the catalogue
	λ	Pairwise inter-meeting rate between H and U
	E[S]	Mean contact duration
	rP	Playout rate
	rV	Download rate from H nodes
	is not the case, then this is an issue of the infrastructure and
	not of the vehicular storage cloud); (ii) while the video plays
	out at the user, future parts of it are actually downloaded
	from locally encountered vehicles (in principle pre-fetched)

Table 2 :

 2 Mobility statistics (λ and λB are in day -1 ).

	Range	λ	E[S]	λB	E[B]
	Short range	1,680	29,53 s	1,238	34,53 s
	Long range	4,391	57,77 s	0,924	139,11 s

While such communication could help fetch content over multiple hops, MANET-like schemes are known to considerably increase the complexity of the approach, while bringing incremental benefits. We defer their study to future work.

Without this assumption, the streaming would require initial buffering in order to avoid interruptions, which are known to significantly degrade QoE[START_REF] Hossfeld | Initial delay vs. interruptions: Between the devil and the deep blue sea[END_REF]. While our framework could be extended to include initial buffering, due to space limitations we defer it to future work.