Project Topics
Get Complete Project Material File(s) Now! »
An explanation for the phase transition
In this section, we explain heuristically why a phase transition may occur in the asymptotics of Hn,j but not in those of Hn,n, Gn,j and Gn,n. To do so, we rephrase the setting in terms of interval-fragmentations. One can easily construct a family (F(k), k ∈ Z+) of random open subsets of (0, 1) with F(0) = (0, 1), which is nested in the sense that F(k′) ⊆ F(k) for all k ≤ k′, and such that the set of the lengths of the interval components of F(k) is {pi : |i| = k} for all integers k. The boxes correspond to the interval components and the balls to a sequence (Ui)i∈N of independent random variables uniformly distributed on (0, 1) and independent of the fragmentation F. The height Hn,j corresponds to the least integer k such that all interval components of F(k) contain less than j elements of the set {U1, . . . , Un}, and the saturation level Gn,j to the least integer k such that there exists an interval component of F(k) containing less than j elements of the set {U1, . . . , Un}. Roughly speaking, the height Hn,j depends crucially on the minimal length mn,j of the intervals [ˆUi, ˆUi+j−1] for 1 ≤ i ≤ n − j + 1, where 0 < ˆU1 < · · · < ˆUn < 1 are the ordered statistics of the family (U1, . . . , Un), whereas the saturation level Gn,j is related to the maximal length mn,j of the intervals [ˆUi, ˆUi+j ] for 0 ≤ i ≤ n−j+1, where ˆU0 = 0 and ˆUn+1 = 1. Indeed, the height Hn,j is the first time k when no cluster [ˆUi, ˆUi+j−1], 1 ≤ i ≤ n−j +1, of size j (in particular the smallest one) is included in an interval component of F(k), and the saturation level Gn,j is the first time k when there exists a cluster [ˆUi, ˆUi+j ], 0 ≤ i ≤ n − j + 1, of size j + 1 (possibly the largest one) containing an interval component of F(k). It is easy to show from Lemma 2.3 that if we used equidistributed points { j n+1 : 1 ≤ j ≤ n} instead of i.i.d. uniform points, then no phase transition would occur. More precisely, all the heights Hn,j would be equivalent to C∗ ln n a.s. Further, the heights Hn,n would be equivalent to (1 − )C∗ ln n a.s. and the saturation levels Gn,jn to (1 − )C∗ ln n a.s.
We first explain why the clusters of size n behave as if the points Ui, 1 ≤ i ≤ n, were equidistributed on (0, 1). It will follow that no phase transition occurs in the asymptotics of Hn,n and Gn,n. To do so, let us first prove that mn,n ≥ n−1++o(1) a.s. Let » > 0. We have: P(mn,n ≤ n−1+−2″) ≤ nP(ˆUn − ˆU1 ≤ n−1+−2″).
Notation and first properties
In order to apply probabilistic techniques, we first introduce a continuous-time version of the quadtree: the points P1, . . . , Pn are replaced by the arrival points of a Poisson point process over R+ ×[0, 1]2 with intensity dt⊗dxdy. All the results obtained in this model can easily be translated into results for the discrete-time model.
The continuous-time model
Let be a Poisson point process on R+ × [0, 1]2 with intensity dt ⊗ dxdy. Let ((i, xi, yi), i ≥ 1) be the atoms of ranked in the increasing order of their -component. We define a process (Q(t))t≥0 with values in finite covering of [0, 1]2 by closed rectangles with disjoint interiors as follows. We first introduce the operation SPLIT: for every subset R of [0, 1]2 and for every (x, y) ∈ [0, 1]2, SPLIT(R, x, y) = R∩[0, x]×[0, y],R∩[0, x]×[y, 1],R∩[x, 1]×[0, y],R∩[x, 1]×[y, 1].
In other words, if R is a rectangle with sides parallel to the x and y axes, then SPLIT(R, x, y) is the set of the four quadrants in R determined by the point (x, y).
We may now recursively define the process (Q(t))t≥0. Let 0 = 0. For every t ∈ [0, 1), define Q(t) = {[0, 1]2}, and for every t ∈ [i, i+1), denoting by R the only element (if any) of Q(i−1) such that (xi, yi) is in the interior of the rectangle R, let Q(t) = SPLIT(R, xi, yi) ∪ Q(i−1) \ {R}.
Observe that a.s., for every i ∈ Z+, there indeed exists a unique rectangle of Q(i) such that (xi+1, yi+1) is in its interior, hence the process (Q(t))t≥0 is well defined up to an event of zero probability. In the sequel we shall assume that the points of always fall in the interior of some rectangle of (Q(t))t≥0. As explained in the introduction, we are interested in the number of rectangles of Q(t) intersecting the segment Sx, specifically we set: Nt(x) = # R ∈ Q(t) : R ∩ Sx 6= ∅ − 1.
Particular cases and fragmentation theory
We give below the definition of a particular case of fragmentation process. For more details, we refer the reader to [Ber06, pages 6-65]. Let be a probability measure on {(s1, s2) : s1 ≥ s2 > 0 and s1 + s2 ≤ 1}. A self-similar fragmentation (Ft)t≥0 with dislocation measure and index of self-similarity 1 is a Markov process with values in the set S↓ = {(s1, s2, . . . ) : s1 ≥ s2 ≥ · · · ≥ 0 and P i si ≤ 1} describing the evolution of the masses of particles that undergo fragmentation. The process is informally characterized as follows: if at time t we have F(t) = (s1(t), s2(t), . . . ), then for every i ≥ 1, the i-th “particle” of mass si(t) lives an exponential time with parameter si(t) before splitting into two particles of masses r1si(t) and r2si(t), where (r1, r2) has been sampled from independently of the past and of the other particles. In other words, each particle undergoes a self-similar fragmentation with time rescaled by its mass. In the next section we establish a link between fragmentation theory and the process Nt(U), where U is a r.v. uniformly distributed over [0, 1] and independent of (Q(t))t≥0. This connection will provide a new proof of a result of [FGCR93] and [CH03]. See also [CLG11] for another recent application of fragmentation theory to a combinatorial problem where the exponent √17−3 2 appears.
The convergence at fixed x ∈ (0, 1)
We prove in this section that when x ∈ [0, 1] is fixed, t−∗ E[Nt(x)] admits a finite limit as t → ∞. The results of the preceding section do not directly apply since the place X0(x) of x in the rectangle R0(x) highly depends on x. Recall notation zk for the word composed of k zeros 0 . . . 0 ∈ A. The guiding idea is that the splittings tend to make Xzk(x) uniform and independent of Mzk(x).
A key Markov chain
Fix x ∈ (0, 1). To simplify notation, for every k ≥ 1, we write Xk for Xzk(x) and Mk for Mzk(x). We shall focus on the process (Xk,Mk)k≥0, which is obviously a homogeneous Markov chain starting from (x, 1) whose transition probability is given by (3.4) or (3.5). Let k ≥ 1. We denote by Fk the filtration generated by (Xi,Mi)1≤i≤k. It is easy to see that the transition probability only depends on Xk, that is E (Xk+i,Mk+i)i≥1|Fk = E (Xk+i,Mk+i)i≥1|Xk .
Quadtree as a model of random geometry
On top of its numerous applications in theoretical computer science, the model of random quadtree may be considered as a model of random geometry. More precisely one can view, for t ≥ 0, the set of rectangles Q(t) as a random graph, assigning length 1 to each edge of the rectangles. We denote this graph by ˜Q(t). A natural question would be to understand the metric behavior of ˜Q(t) as t → ∞. The study of the graph distance Lt in ˜Q(t) between the upper-left and upper-right corners would be a first step in understanding the global geometry of ˜Qt. Observe that Theorem 3.2 already shows that Lt is less than the order t √2−1.
Table of contents :
1 Introduction
1.1 Chaînes de fragmentation
1.2 Résultats généraux sur les fragmentations
1.3 Les arbres de fragmentation
1.4 Le quadtree
1.5 Graphes aléatoires
1.6 Les tailles des composantes d’un graphe aléatoire critique
2 A phase transition for the heights of a fragmentation tree
2.1 Introduction
2.2 Formulation of the main results
2.3 Preliminaries
2.4 Study of the heights
2.5 Study of the saturation levels
2.6 An explanation for the phase transition
3 Partial match queries in two-dimensional quadtrees
3.1 Introduction
3.2 Notation and first properties
3.3 Particular cases and fragmentation theory
3.4 The convergence at fixed x ∈ (0, 1)
3.5 Identifying the limit
3.6 Extensions and comments
4 The component sizes of a critical random graph
4.1 Introduction
4.2 Formulation of the results
4.3 The depth-first search
4.4 Convergence of the walk sn
4.5 Study of the cycle half-edges
4.6 Study of the random simple graph SGn
4.7 The power law distribution setting
Bibliographie
