{'fraction_non_alphanumeric': 0.061197718631178705, 'fraction_numerical': 0.0217680608365019, 'mean_word_length': 3.447911381701336, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 56, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the number and size of Markov equivalence classes of random directed acyclic graphs

In causal inference on directed acyclic graphs, the orientation of edges is in general only recovered up to Markov equivalence classes. We study Markov equivalence classes of uniformly random directed acyclic graphs. Using a tower decomposition, we show that the ratio between the number of Markov equivalence classes and directed acyclic graphs approaches a positive constant when the number of sites goes to infinity. For a typical directed acyclic graph, the expected number of elements in its Markov equivalence class remains bounded. More precisely, we prove that for a uniformly chosen directed acyclic graph, the size of its Markov equivalence class has super-polynomial tails.


Introduction
For a graphical model on a directed acyclic graph, the conditional independence information which can be extracted from the model, is encoded by its v-structures, a collection of v-shaped subgraphs. Given the underlying undirected graph, and the v-structures, is it possible to reconstruct all edge orientations? In general, having only access to the conditional independence between sites, and the set of undirected edges, is not sufficient to uniquely determine a directed acyclic graph (DAG). We refer to its Markov equivalence class (MEC) as the set of all DAGs with the same undirected graph, and the same v-structures. Markov equivalence classes are a central object in causality theory with applications in machine learning, economics and social sciences [6,8,9,10,24].
While the size of a Markov equivalence class of a DAG on n sites can be as large as n!, for example when the graph is a clique, simulations suggest that the ratio between Markov equivalence classes and directed acyclic graphs on n sites remains uniformly bounded from below when n goes to infinity [28]. Similarly, the ratio between essential directed acyclic graphs, which are the unique elements in their Markov equivalence class, and the total number of DAGs seems also to be uniformly bounded in n. Over the past decades, exact recursive descriptions for counting the number of DAGs, as well as the number of essential DAGs, were found [27,28,29]. However, there are no simple exact formulas available to give a precise asymptotic control on the above ratios. In this paper, we show that the ratio between MECs and DAGs on n sites, as well as the ratio between essential directed acyclic graphs and DAGs, both converge to some positive constants c MEC and c Ess , respectively, when n goes to infinity. In particular, with positive probability, a DAG chosen uniformly at random on n sites is the unique element in its Markov equivalence class. To our best knowledge, these are the first rigorous results on the above ratios for this model.
In recent years, the question of counting of the number of Markov equivalence classes for various families of DAGs, including DAGs on trees and complete graphs with a few missing edges, is studied in the machine learning community [6,8,10,18,30]. We show that the expected size of a Markov equivalence class for a directed acyclic graph, chosen uniformly at random on n sites, is bounded uniformly in n. In contrast to counting the number of MECs on a given underlying graph, the challenge for a uniform sampled DAG is that we do not have access to a simple recursive sampling procedure, and thus have to directly study its typical structure in order to get bounds on its Markov equivalence class.
1.1. Model and results. Let G be a directed acyclic graph with (labeled) vertex set V , with V = [n] := {1, . . . , n} for some n ∈ N, and directed edge set E. We denote by D n the set of all labeled DAGs on n vertices. For any triplet of vertices (a, b, c) ∈ V 3 , we say that c is a collider if (a, c), (b, c) ∈ E, while (a, b), (b, a) / ∈ E. In this case, we call (a, b, c) a v-structure, also called intervention or immorality, at c. For a fixed DAG G ∈ D n , we denote by M (G) the set of all DAGs which have the same edge set when forgetting the edge directions, also called the skeleton of G, and the same v-structures as G. We refer to M (G) as the Markov equivalence class of G; see also Figure 1. In the following, our main focus is to estimate the number and size of Markov equivalence classes for directed acyclic graphs sampled uniformly at random on a given number of sites.
For a uniformly sampled DAG G on n sites, let P n and E n be the corresponding law and expectation. We have the following main result on the tails of the size of a Markov equivalence class for a DAG G sampled according to P n . Theorem 1.1. For all n ∈ N and t ≥ 0 sufficiently large, we have that for some constant C > 0 and α = 1 20 . Thus, for every k ∈ N, there exists some constant c k > 0 such that for all n ∈ N (1.2) E n |M (G)| k ≤ c k .
In particular, the expected size of a MEC for a uniform DAG on n sites is finite.
The constant α in (1.1) is not optimized, but can be at most 1, e.g. when we set t = n! and consider the event that the underlying skeleton is a clique. It remains an open question whether the parameter α in (1.1) can be chosen arbitrarily close to 1. Next, we consider the set of non-collider edges C(G), i.e. the edges which are not part of any v-structure, and show that the number of non-collider edges |C(G)| converges to some random quantity.  i.e. with positive probability, a DAG according to P n is the unique element in its MEC. When a given DAG is the unique element in its Markov equivalence class, we refer to it as an essential directed acyclic graph. We have the following bounds on the number of Markov equivalence classes, and the number of essential directed acyclic graphs on n sites. Simulations suggest that c −1 Ess ≈ 13.65, while the ration between the number of Markov equivalence class to DAGs satisfies c −1 MEC ≈ 3.94; see [28,29], and [5] for a heuristic explanation using linear extensions of the reachablity poset of a DAG. Remark 1.4. Let us stress that the above results are proven with respect to labeled directed acyclic graphs. In [4], it is shown that a DAG drawn according to P n has only trivial automorphisms with probability tending to 1 when n goes to infinity. Thus, Theorem 1.2 and Theorem 1.3 extend to sampling an unlabeled DAG uniformly at random.

Related work.
Directed acyclic graphs and their Markov equivalence classes are central objects in causality theory. In a more general context, the concept of d-separation is used for graphical models to describe conditional independence; see [24] for a classical introduction to causality theory, and [21] for an exhaustive treatment of graphical models. In our setup, the special case of a Bayesian network, where the underlying graph is directed and acyclic, conditional independence is described by v-structures. Reconstructing a DAG from its skeleton and v-structure, respectively estimating the size of its Markov equivalence class, has a variety of applications in machine learning and related disciplines; see [6,8,9,10].
Over the last decades, various results on describing and counting directed acyclic graphs are achieved, see for example [28,29] for recursive formulas on counting labeled (essential) DAGs, as well as [3,4,27] for enumerations when the number of edges is fixed, or the DAGs are unlabeled. These formulas allowed also for counting certain statistics of DAGs, see for example [22] on the number of sources of a DAG chosen uniformly at random on a given number of sites. However, no explicit formulas to express the number of elements in the Markov equivalence class of general directed acyclic graphs are currently known.
An alternative characterization of Markov equivalence classes is given by Andersson et al. using partially directed acyclic graphs, i.e. where some edges in the DAG can be undirected [1]. Each Markov equivalence class corresponds to some partially directed acyclic graph -see Section 6 -and Andersson et al. provide necessary and sufficient conditions for a partially directed acyclic graphs to correspond to a Markov equivalence class.
In recent years, there is progress on computing the number of Markov equivalence classes for a fixed underlying skeleton, e.g. when the underlying graph is a tree or the complete graph with a few missing edges, see [2,13,15,16,18,20,25,26] for a nonexhaustive list of results in this direction. Moreover, sampling the number and size of Markov equivalence classes, in particular using Markov chains, is a main question of interest; see [5,11,14,17,30], and also [12,31] for very recent results on exact polynomial-time sampling of Markov equivalence classes on general DAGs. The above results have in common that they rely on knowledge about the structure on the directed acyclic graph, either in terms of its skeleton, or a recursive decomposition technique such as clique trees.
When estimating the number and size of Markov equivalence classes for a directed acyclic graphs chosen uniformly at random on a given number of sites, the set of applicable techniques is more restricted. Exact recursive formulas for counting and a decomposition via clique trees are available, but difficult to control. In [5], a heuristic on the number of MECs and essential DAGs is given using the reachability poset of a directed acyclic graph. In this paper, we rely on a similar so-called tower decomposition, which can be found for example in [4] and [23] to study the structure of a typical DAGs, i.e. when removing the assumption of labeled sites, or when conditioning on a fixed number of edges in the graph. These structural results rely crucially on generating functions, and we will use them as a starting point for more probabilistic arguments to study Markov equivalence classes.
1.3. Outline of the paper. In order to show our main results, we pursue the following strategy. We start in Section 2 by recalling the reachability poset and the tower decomposition for directed acyclic graphs. In Section 3, we give precise bounds on the number of direct acyclic graphs corresponding to a given tower vector. In particular, we introduce the notion of regeneration points, which allows us in Section 4 to refine previously known results on the shape of towers. With this at hand, we prove convergence of the law of the last layers in a tower decomposition. In return, this allows us to establish Theorems 1.2 and 1.3 in Section 5 on the convergence of the number of non-collider edges. In Section 6, we collect basic estimates on the number of elements in a Markov equivalence class, and we present a refined counting method for Markov equivalence classes; see Proposition 6.4.
Using estimates on the tower decomposition from Section 3, we then partition the sites of a given DAG according to their potential to create non-collider edges. Bounding the number of sites in each such partition, as well as the number of non-collider edges between them, this allows us to conclude Theorem 1.1 in Section 7.

Poset and tower decomposition of DAGs
In the following, we provide two ways of forming equivalence classes for labeled DAGs, apart from the Markov equivalence relation given in the introduction. We start with a poset decomposition, which can be found for example in Section 3 of [5].
2.1. A poset decomposition for DAGs. For a given DAG G, we define a partial order on its vertex set V as follows. We let v w for v, w ∈ V if and only if there exists a directed path in G from w to v. We call the resulting poset (V, ) the reachability poset of G. We say that v covers w if v w, and there is no u ∈ V such that v u w. For each v ∈ V , let dom(v) be the number of sites below v according to , and let cov(v) be the number of sites covered by v. For a given poset (V, ), we set and we partition the DAGs according to their reachability posets; see Proposition 16 in [5]. A similar relation is given in Proposition 17 of [5] to count the number of essential DAGs. We call a vertex v a source, respectively a sink, if it is a minimal, respectively a maximal, element in the reachability poset.

2.2.
A tower decomposition for DAGs. In the decomposition of DAGs according to their reachability posets, it is in general difficult to estimate the total number of noncollider edges of the DAGs in a given equivalence class. Instead, we rely on a different partitioning of directed acyclic graphs according to their vertex heights, i.e. the length of the longest directed path from some source in the DAG to a given site v. A version of this construction can be found in Section 4 of [3].
For a given DAG G, we define its tower decomposition as follows. We let H 1 = H 1 (G) be the set of all sinks in G, i.e. the set of sites with no outgoing edges. In a next step, given H 1 , we consider the reduced graph G 1 := G \ H 1 , where we remove all sites in H 1 from G, as well as the corresponding edges to a site in H 1 . In the reduced graph G 1 , let H 2 be the set of all sinks, and set G 2 := G 1 \ H 2 . Continuing in the same way, we recursively obtain a partition of V (G) into disjoint sets H i for i = 1, . . . , T with some T = T (G); see Figure 2. We call T (G) the height of the graph G, and refer to (H i ) i∈[T (G)] as the layers of G. Using the tower decomposition of G, we obtain a vector H = (H 1 , H 2 , . . . , H T (G) ) and set  When keeping only the edges between sets h i and h i+1 , we call the resulting graph the tower σ(G) of G, and we refer to h = h(G) as the corresponding tower vector. With a slight abuse of notation, we write h(σ) for the tower vector of a DAG with tower σ, and set as the size of G. Note that the uniform measure P n is supported on the set D n of DAGs of size n. The following is a simple observation on this construction, so we omit the proof.
Lemma 2.2. Each DAG G belongs to a unique tower σ(G), respectively a unique tower vector h(G). For each n ∈ N, the set of towers Σ n , and the set of tower vectors Ω n , partition the set of all DAGs D n on n sites.
We are interested in counting of the number of DAGs associated to a given tower σ. For each tower σ, let D(σ) be the set of all DAGs associated to σ. For each site v ∈ V , we let d(v) denote the number of sites in σ, which can be reached by some directed path. Moreover, we let c(v) correspond to the out-degree of v in the tower σ. Lemma 2.3. For each labeled tower σ, we have that Proof. Recall that we consider the set of labeled DAGs on a given number of sites, and thus all sites are distinguishable. Fix some tower σ. Then each edge in the skeleton which connects two sites in adjacent layers is present for all graphs in D(σ). Between any two sites v and w in different layers which are not adjacent, adding or removing the edge between v and w does not change the underlying tower. This justifies the above formula.
Remark 2.4. Note that above tower decomposition has the key property that when we condition on the underlying tower σ in P n , each edge between two sites in layers of distance at least 2 in the tower σ is present independently with probability 1 2 .

Computation of the tower weights
In the following, our goal is to estimate the size of the tower for a DAG on n sites, drawn according to P n for some n ∈ N. We define the weight w(σ) of a tower σ as Similarly, with a slight abuse of notation, let w(h ′ ) be the weight of a tower vector h ′ with counting the number of DAGs associated to a given tower vector suitably renormalized. The next characterization is immediate from the tower construction together with Remark 2.4, and can be found for example in the proof of Theorem 4.1 in [3].
Furthermore, we have that where we recall that |D n | is the number of DAGs on n sites, and the second factor denotes the multinomial in the coefficients of h.
Note that the number of DAGs corresponding to a given tower vector consisting of n sites is maximized for a simple path The following is a consequence of the above computations. We use the convention Proposition 3.2. There exists some universal constant C > 0 such that for any distinct i 1 , i 2 , . . . , i j ∈ N, for all x k ≥ 5, and all n ∈ N sufficiently large, we have that Proof. In the following, we identify each fixed height vector h = (h 1 , . . . , h ℓ ) with h i = x for some fixed x ∈ N with a unique height vectorh. More precisely, for fixed i ∈ [ℓ], we consider the set of DAGs, with respect to the vector with |h| = |h|, i.e. we replace h i by |h i | many ones, and shift the remaining components. We claim that for all x ≥ 3, this new vector satisfies holds for all x ≥ 3. Thus, we obtain that recalling the convention that h i+1 = 0 for all i > ℓ. Using (3.9), we proceed by induction over x ≥ 5, and show that For all x ≥ n, the inequality (3.11) trivially holds. Suppose that (3.11) holds for all y ∈ {x + 1, x + 2, . . . }. Then we see by (3.9) that for all x ≥ 5. This yields (3.5) by a union bound.
Next, we bound the probability of having a single element in a given layer.
Lemma 3.3. For any i ∈ N and for all n ∈ N sufficiently large, we have with P n -probability at least 1 64 that h i ≤ 1 holds. Proof. Without loss of generality, assume that the event {T (G) ≥ i} holds with P nprobability at least 1 2 , as the claim is trivial, otherwise. Fix some G drawn according to P n . When i = T (G), the claim follows from [22], where the law of the number of sources and sinks in a DAG is studied. For i < T (G), observe that by Proposition 3.2, we have that with P n -probability at least 1 2 , it holds that max(h i , h i+1 ) ≤ 4 for all n sufficiently large. In other words, for each such n ∈ N (3.12) Note that for each such tower vector h which satisfies (3.12), we can define a corresponding vectorh as in (3.6) by replacing the layer H i by h i many consecutive ones. Since each such vectorh has at most 16 tower vectors mapping onto it, we conclude from (3.8) in Proposition 3.2 that Thus, using Lemma 3.1, this finishes the proof.
Remark 3.4. The same arguments as in Lemma 3.3 show that for any k ≥ 1, there is a strictly positive probability p k > 0 to see exactly k sites in a fixed layer i, provided that n is sufficiently large.
Note that previously exact asymptotic bounds -in terms of Gaussian tails -were only known for the last layer using generating functions; see [22]. Lemma 3.3 yields Gaussian tails for any generation. Next, we consider the vertical distance until we reach a layer containing only a single element. We say that H j is a regeneration layer if and only if h j = 1. Moreover, we let τ i be the i th regeneration point, i.e. we set (3.14) and recursively whenever there are at least i + 1 many regeneration points in the tower for some i ∈ N.
Recall that Ω n denotes the space of tower vectors of size n. In the following, it will be convenient to write Ω r for the space of tower vectors with r regeneration points, and we set (3.16) Ω r n := Ω n ∩ Ω r as the space of tower vectors of size n with exactly r regeneration points. Moreover, we set as the space of all tower vectors. The following result, which is a consequence of Theorem 3.3 in [23], gives a bound on the total number of regeneration points R(h) of a tower vector h.
where X is a standard normal random variable.
We use the conventions that τ 0 = 0, and τ i = T (G) + 1 if h contains less than i regeneration points. Let A n be the event that the tower of a DAG according to P n has at least 1 2 c 1 n many regeneration points, and note that by Lemma 3.5 (3.19) lim n→∞ P n (A n ) = 1 .
We conclude this section with the following consequence of the above results on the distance between regeneration points, which is of independent interest.
Corollary 3.6. There exists some universal constant c > 0 such that for all n ∈ N sufficiently large, and all s ∈ N, we have that Proof. Fix some n ∈ N large enough. We claim that it suffices to show that for any fixed sequence of integers (

A Decomposition of tower vectors
In the following, our goal is to use the tower decomposition in order to study the structure of non-collider edges. Fix some tower vector h, and recall that R(h) is the number of regeneration points in h. We denote by (G i ) i∈[R(σ)]∪{0} the collection of layers between regeneration points τ i and τ i+1 , with the convention that τ 0 = 0. We call G i the i th feature in h; see Figure 3. Whenever G i is non-empty, we write In the following, we change our perspective and construct a tower vector out of a family of i.i.d. features. With a slight abuse of notation, for a given feature G = (g 1 , . . . , g m ), we let denote the weight of G, with the convention that g 0 = g m+1 = 1. Let Γ denote the set of all features, including also the empty set ∅ with weight w(∅) := 1, and |G i | = 0 if i > R(h). Intuitively, we obtain the above weight of a feature G by comparing the weight of the sequence (g 1 , g 2 , . . . , g m ) inside a tower vector between two regeneration points to the weight of a tower vector when replacing the corresponding part G by a path of length |G|.
We show in Lemma 4.3 that the weight of a feature is compatible with the weight of a tower vector defined in (3.4). However, the above weight in (4.2) is adjusted for wired boundaries, i.e. we are using the convention g 0 = g m+1 = 1. We will require slightly different weights to model the free boundaries in the features to the left of the first regeneration point and to the right of the last regeneration point. More precisely, we denote by the weight of a feature G with free left boundary as well as by with weight of a feature G with free right boundary. Again, in both of the above cases, we use the convention that the weight is set to 1 whenever G is the empty feature. Moreover, for a feature G and some θ ∈ R, we set and similarly for ← − w θ (G) and − → w θ (G), as its tilted weight. We obtain the following estimate on the tilted weights of all possible features.
Lemma 4.1. There exists some θ 0 < 0 such that for all θ > θ 0 , we have that Moreover, for all θ > θ 0 , there exists some ε 0 = ε 0 (θ) > 0 such that for all ε < ε 0 Proof. Using that Z θ is monotone decreasing in θ, it suffices to show that (4.6) holds for some fixed θ < 0. Using the facts that and that g i ≥ 2 for all i ∈ [m] whenever G is non-empty, we get for all G = ∅ that Summing now over all G with |G| = k for some fixed k ≥ 2, we get that (4.10) A computation now shows that the right-hand side of (4.10) is less than 8 · ( 3 4 ) k for all k ≥ 2, allowing us to conclude (4.6). Moreover, for all ε = ε(θ) > 0 sufficiently small which yields the statement in (4.7).
Corollary 4.2. For all θ > θ 0 with θ 0 from Lemma 4.1, it holds that Proof. Observe that we have for all features G = (g 1 , . . . , g j ) ∈ Γ with j ∈ N Since the weights w θ (G) are super-exponentially decaying in the size of the first component g 1 , this bounds the first sum in (4.12). A similar argument holds with respect to − → w θ (G).
The above construction of features has the advantage that we can define for all θ ≥ 0 the law µ θ on Γ by (4.14) µ θ (G) := Z −1 θ w θ (G) , and similarly the laws ← − µ θ and − → µ θ . We compose now the above features in order to describe a corresponding tower vector. More precisely, we define a tower vector X with a given number of regeneration points r = R(X ) using a collection of (potentially empty) features G 0 , G 1 , . . . , G r−1 , G r according to µ θ for G i with i ∈ [r − 1], according to ← − µ θ for G 0 , and according to − → µ θ for G r . We denote by Q r θ the corresponding law of a tower vector X on the space Ω r under this construction. We have the following key result on the sampling of features for a given total size and a given number of regeneration points. Lemma 4.3. Fix some tower vectorh with r regeneration points and size n, i.e. the corresponding tower vector belongs to Ω r n . Then for any θ such that Q r θ is well-defined (4.15) P n (h =h | R(h) = r) = Q r θ X =h |X | = n . Proof. Observe that the measure (4.16) Q r θ X ∈ · |X | = n is supported on Ω r n and does not depend on θ. Fix some θ > θ 0 with θ 0 from Lemma 4.1. The probability to see X according to Q r θ with features (G i ) i∈{0}∪[r] is proportional to Recall the weight w(X ) from (3.4) for a tower vector X ∈ Ω r n . A direct computation shows that on the space Ω n for some fixed n ∈ N , comparing the feature weights in (4.2), (4.3), and (4.4) to the number of DAGs for a given tower in (3.4). Hereby, we let h n 1 be the all one vector of length n, and note that h n 1 does not depend on r. In other words, we have that (4.19) P n X ∈ A R(X ) = r = 1 Z r,n σ∈A W r (σ) for some suitable normalizing constantZ r,n , and all subsets A ⊆ Ω r n . Since P n · | R(X ) = r is supported on Ω r n , this finishes the proof.
In the following, we use this change of measure together with Lemma 4.1 in order to analyze the tower decomposition. We require the following lemma which allows us to apply Lemma 4.1 for some suitable choice of θ > 0. We denote byQ r 0 the measure where we sample a vectorX = (X i ) i∈[r] on the space Γ r of r features, each of them independently according to the measure µ 0 . is continuous and strictly decreasing for all θ ≥ 0, and there exists some θ * > 0 such that Proof. The first part (4.20) is immediate from Lemma 4.1. In the following, we argue that for some d 1 < c 1 . Since the right-hand side in (4.20) goes to 0 for θ → ∞, this yields (4.21) using the continuity and strict monotonicity in (4.20). Using the notation |X | : with Z 0 from (4.6). Thus, by a law of large number for the random variables (|X i |) and Lemma 3.5, it suffices now for d 1 < c 1 -and thus (4.22) -to show that for some ε > 0 (4.24) holds with some constant c = c(ε) > 0, and all n sufficiently large. We distinguish two cases. First, we consider all r ≤ (1 − ε)d 1 n. Then since Z 0 > 1, using a large deviation principle for (|X i |) i∈[r] , and a central limit theorem in the second line, we have that for some constants C 1 , C 2 > 0, and n sufficiently large. Next, using again that the random variables (|X i |) i∈[r] have some finite exponential moment by Lemma 4.1, a moderate deviation estimate shows that for all δ > 0 sufficiently small and n large enough for some constant C 3 > 0; see [7] for a reference on moderate deviations. As Z 0 > 1, we use (4.25) for r = ⌊(1 + δ)d 1 n⌋ in the sum on the right-hand side of (4.24) for sufficiently small δ > 0, and choose ε = δ/2 on the left-hand side of (4.24) to conclude.
We have now all tools to show the convergence of the last entries in the tower vector.
Lemma 4.5. We have for any fixed k ∈ N and for some almost surely finite random variables (Y i ) i∈[k] with full support on N ∪ {0}.
Proof. Note that by Proposition 3.2 and Remark 3.4, it remains to show that the above limit in (4.26) exists. To do so, we argue that for every fixed length k, the law of the last k entries in the tower vector converges as the total number of sites goes to infinity. We strongly rely on Lemma 4.3 in order to work with the law Q r θ instead of P n , allowing for some additional flexibility in the choice of the parameter θ.
In order to formalize the above ideas, fix some k ≥ 1 and x = (x 0 , x 1 , . . . , x k ) with x j ∈ Γ for all such j, i.e. x is a family of features. We denote by |x| = x 0 + x 1 + · · · + x k−1 + x k the total of number of sites in these features. Let X with features (G i ) i∈{0}∪[r] be sampled according to Q r θ on the space Ω r for some fixed r, and for some θ ≥ 0. We define A x n,r := X ∈ Ω r n and G 0 = x 0 and G i = x i+r−k for all i ∈ [k] and as the event that the first feature, as well as the k last features, agree with the collection of features x, and that the sample X , counting features and regeneration points, has total size n. Similarly, we let be the event that the last k features in the sampled tower vector correspond to the last k features in x, and the first feature agrees with x 0 . Note that B x is also naturally defined as an event on the space Ω, requiring at least k regeneration points. Recall µ θ from (4.14).
To simplify notation, we set Next, recall from Lemma 3.5 that the number of regeneration points R(·) according to P n converges in the leading order to c 1 n for some universal constant c 1 ∈ (0, 1). When the event A n from (3.19) holds, note that in order to prove (4.26), it suffices to show that for any x = (x 0 , x 1 , x 2 , . . . , x k ) with x i ∈ Γ for all such i, we have that for the constant θ * from Lemma 4.4. Fix ε > 0 and let I n := [c 1 n − n 2/3 , c 1 n + n 2/3 ]. Then for all n sufficiently large, we get by Lemma 3.5 that Moreover, by Lemma 4.3, we have for any θ ≥ 0 Next, we claim that for all n ∈ N sufficiently large, and every r ∈ I n , there exists some θ = θ(n, r) ≥ 0 such that (4.32) Moreover, it holds that  This follows directly by inserting (4.34) into (4.31). We prove (4.34) by showing that for any two vectors x and y of length k. In the following, to show (4.35), it is helpful to interpret the measures Q r θ ( · | |h| = n) and µ θ * as probability measures on the space Γ k+1 , summing over all possible choices for a given x ∈ Γ k+1 for the first, and the last k features. Recall the event A x n,r , and note that (4.36) Q r θ h ∈ B x |h| = n = Q r θ (A x n,r )/Q r θ (|h| = n) . From the definition of A x n,r and the construction of Q r θ , we see that for the above θ = θ(n, r) A similar decomposition holds with respect to y. Recall Lemma 4.1 to bound the first and second moment of |G j |, and that |G j | has full support on N ∪ {0} by Remark 3.4. A local central limit theorem for the random variables (|G j |) j∈[r−k] ensures that for any ε > 0, there exists some N = N (ε, x, y) such that for all n ≥ N , we see that Moreover, by (4.33), the feature distribution µ θ with θ = θ(n, r) satisfies for fixed x and y Combining (4.38) and (4.39), this gives (4.35), and thus finishes the proof.

Counting the number of colliders in a uniformly sampled DAG
We now show that the number of non-collider edges |C(G)|, as well as the ratio between essential DAGs and MECs with respect to the total number of DAGs on n sites converges as n goes to infinity. Recall the tower decomposition from Section 2.2, and set to be the last tower generation containing a site of a non-collider edge. Here, we use the convention L(G) = −1 if each edge in G is part of a collider.
Lemma 5.1. There exists some non-negative, almost surely finite random variable X such that for all s ≥ 0 Moreover, we fine a non-negative, almost surely finite random variable Y where for all s ≥ 0 Proof. Recall that we assign for each DAG G a unique tower vector h = (h 1 , h 2 , . . . , h T (G) ). For all ε > 0, we define the event with the convention that h j = 0 for all j < 1. By Proposition 3.2, we get that Thus, we get the lower bound and let B c ε be the corresponding event in the probability on the left-hand side of (5.6). Conditioning on the event B c ε , recall that we have for each pair of sites v i ∈ H i and v j ∈ H j with i ≥ j + 2 that the edge e = (v i , v j ) is present independently with probability 1 2 . Thus, for each v ∈ H T (G)−k for some k ≥ 3, we have that We obtain that for all j ∈ N and ε > 0 using a union bound. Choosing now j = j(ε) sufficiently large, this gives the first bound (5.2). For the second bound (5.3), note that which, when combined with (5.2) and (5.6), allows us to conclude.
Next, we show that with positive P n -probability, uniformly in n, we see in fact only collider edges in the sampled DAG.
Lemma 5.2. It holds that Proof. Recall that D n denotes the set of all labeled DAGs on n sites. By Lemma 5.1, there exists some J > 0 such that D J n := G ∈ D n : L(G) < J and |h T (G)−k | ≤ J for all k ∈ [J] satisfies |D J n | ≥ 1 2 |D n | for all n sufficiently large. Consider now the mapping f : D J n → D n where each DAG G gets mapped to a DAG G ′ , which we obtain from G by removing all edges e = (v, w) with v ∈ h T (G)−i and w ∈ h T (G)−j for some i, j ≤ J. We claim that for each graph G ∈ D J n , the corresponding graph G ′ = f (G) has only collider edges. To see this, note that we remove all non-collider edges in G in this way, while in this construction no new non-collider edges are created. Since |f −1 (G ′ )| ≤ J J for all G ′ ∈ D n , the P n -probability to have C(G) = 0 is at least 1 2 J −J for all n sufficiently large. We have now all tools to show Theorem 1.  5) and (1.6) exist. Fix some ε > 0, and recall that by Lemma 5.1, there exists some J = J(ε) such that P n (L(G) ≥ J) < ε for all n sufficiently large. Further, recall from Lemma 4.5 that the law of the last J features under P n converges when n goes to infinity. As a consequence, we see that the law of the edges between all sites in the last J layers on the tower converges to some law ν J . Let C * be the number of non-collider edges according to ν J . Notice that on the event {L(G) < J}, we have that C(G) depends only on the edges between sites in the last J layers of the tower. Thus, for each s ≥ 0 Since ε > 0 was arbitrary, this gives Theorem 1.2. As a special case of (5.10), we obtain that for any ε > 0, we can choose J = J(ε) sufficiently large such that

Representations of Markov equivalence classes
In this section, we collect facts and estimates on the size of Markov equivalence classes. It is well-known that every MEC can be represented as a partially directed acyclic graph (PDAC), i.e. the edges may be either directed or undirected such that the graph contains no directed cycles. For a given DAG G, we obtain its corresponding PDAG by keeping the order of an edge if and only if it has the same orientation in each element of M (G), and let it be undirected, otherwise. While we always obtain a PDAG in this construction, Andersson et  Figure 4. Decomposition of an essential graph G into its chain graphs C 1 G and C 2 G drawn in red.
al. provide necessary and sufficient conditions for a given partially directed acyclic graph to yield a Markov equivalence class; see [1]. These PDAGs leading to a Markov equivalence class are also called essential graphs. The following lemma is a simple observation between non-collider edges and Markov equivalence classes using essential graphs.
Lemma 6.1. Let e be an undirected edge in an essential graph. Then for all DAGs in the corresponding Markov equivalence class, we have that e is a non-collider edge.
Proof. This follows immediately from the construction of the essential graph since every edge which is part of a v-structure has the same orientation in every DAG of its Markov equivalence class.
It will be convenient to use a decomposition for essential graphs when estimating the expected size of a Markov equivalence class. For a given DAG G, we define its chain graph C G by removing all directed edges in the essential graph of its Markov equivalence class M (G). We denote the connected components of size at least 2 of the chain graph as C 1 G , C 2 G , . . . , C ℓ G for some ℓ ∈ N. A visualization of this construction can be found in Figure 4. We make the following observation, which can be found in [17]. Lemma 6.2. For a given DAG G, we have that where |M (C i G )| is the number of ways to orient the edges within C i G such that they agree with the edge orientation of some DAG in M (G).
As a simple consequence of Lemma 6.1 and Lemma 6.2, we obtain the following statement.  Proof. Consider the representation of a MEC of a given DAG G as a partially directed acyclic graph, where the directed edges have the same orientation as in G. Let (C i G ) i∈[ℓ] for some ℓ ∈ N denote the connected (undirected) components of its chain graph, and |C i G | the number of sites in C i G . Note that by the poset decomposition in Lemma 2.1, for each C i G , there are at most |C i G |! ways to orient the edges. Together with Lemma 6.2, this yields Since every site in a component C i G must be an element of N (G) by Lemma 6.1, and the connected components (C i G ) i∈[ℓ] are vertex disjoint by construction, we conclude. Lemma 6.3 gives good bounds when the number of non-collider edges is large compared to the number of sites. However, we will require a refined estimate on the number of Markov equivalence classes when the chain graph takes the form of a core graph, where only a small number of its sites are connected to other sites outside of the core graph using non-collider edges. To do so, we fix in the following unique labels ℓ(v) ∈ [n] for all sites v ∈ V (G), which are consistent with the tower structure, i.e. such that ℓ(v) ≥ ℓ(w) holds if and only if v ∈ H i and w ∈ H j with i ≤ j in the tower H(G).
Proposition 6.4. For a given partially undirected graph G, let C = (V (C), E(C)) denote its chain graph. Suppose that V (C) can be partition as (V 1 , V 2 ) such that the following four properties hold for some a, b > 0.
1. Each layer of the tower of G with a site in V (C) consists of at most a sites.

2.
There are at most b many sites in V 1 which are adjacent to a site in V 2 using E(C).

It holds that
For each pair of sites v, w ∈ V 2 with ℓ(w) ≥ ℓ(v) + 5a, there exists a directed path in G from v to w.
Then we have that the number |M (G)| of MECs with respect to G satisfies Proof. LetṼ be the set of sites in V 1 that are connected to some site in V 2 via an undirected edge, and note that |Ṽ | ≤ b by our second assumption. By Lemma 6.3, there are at most |V 1 |! many ways to order the sites in V 1 . For each such ordering, we claim that there are at most (|V 2 |(10a)!) b ways to assign the directions of the remaining edges.
Our key observation is that for each v ∈Ṽ , there is a transition point in the direction of the outgoing edges to V 2 . More precisely, fix an ordering of the edges leading to a DAG. Let O(v) be the smallest label such that an edge from v to V 2 is outgoing, and let I(v) be the largest label such that an edge is ingoing to v, with the conventions I(v) = 0 and O(v) = n+1 if there are no such edges. We claim that |I(v)−O(v)| ≤ 10a. To see this, note that by the forth assumption, each pair of edges (x, v) and (v, y) with x for ℓ(x) ≤ ℓ(v) − 5a and with y for ℓ(y) ≥ ℓ(v) + 5a would create a directed cycle.
For every v ∈Ṽ , note that there are at most |V 2 | many ways to choose I(v), and there are at most 10a many sites in V 2 to which the ordering of edges betweenṼ and V 2 is not determined from knowing I(v). Thus, since there are at most b many sites inṼ , and each element in the MEC can be associated with a unique total ordering of edges to the remaining at most 10a many vertices for each choice of I(v), this gives the claim.

Counting the number of MECs of a uniformly sampled DAG
We now investigate the set of vertices N (G) of a DAG G sampled according to P n , which are adjacent to some non-collider edge in C(G). Recall from Lemma 6.3 that the size of a MEC for n non-collider sites is at most n!. Note that this bound is tight when the underlying graph is a clique, but can in general be quite rough, for example for tree-like graphs. Therefore, we use a decomposition of the sites N (G) in order to obtain an improved bound on the size of the MEC of G, applying Proposition 6.4.
We give now the setup for the proof of Theorem 1.1. Our main idea is to partition the sites N (G) according to their position within the tower and their connection properties. We have the following bound on the size of the Markov equivalence class. . Proof of Theorem 1.1 using Proposition 7.1. Note that |M (G)| ≤ n! holds P n -almost surely. Since for t = m! with m ∈ N large enough, we have the claimed bound on the tail of |M (G)| follows from Proposition 7.1.
In the remainder, our goal is to show Proposition 7.1. We achieve this in four steps. First, we consider the tower decomposition and bound the probability that we see a non-collider edge, which reaches a site with a large label. We then identify bad vertices, which have undesirable connection properties, and show that with sufficiently large probability, their number is not too large. In a next step, we bound the total number of bad sites which are connected by non-collider edges to some good site. In a last step, we combine the above estimates with Proposition 6.4 to conclude. 7.1. On the total number of non-collider edges deep in the tower. We estimate the number of non-collider edges with both endpoints deep in the tower. Recall the tower decomposition H(G) with a tower vector h(G). Further, recall the labeling ℓ before Proposition 6.4, which is consistent with the tower decomposition, i.e. ℓ(v) ≥ ℓ(w) holds if and only if v ∈ H i and w ∈ H j for some i ≤ j. We give a bound on the number of such edges where the lower endpoint has a label between k/3 and k 7/6 , and show that with sufficiently large probability, there are no such non-collider edges to a site with label at least k 7/6 . Before doing so, we start with a bound on the number of sites in each layer in the tower decomposition. We define the event Here, we use the convention that h(i) = 0 if i > T (h), where T (h) is the length of h.
Lemma 7.2. There exist constants c, N > 0 such that for all n ≥ N and k ∈ [n], we have that B 1 = B 1 (k) holds with P n -probability at least 1 − exp(−ck 5/4 ) for all k > 0 sufficiently large.
Proof. This follows from a simple computation using Lemma 3.2, and summing over all possible values of the entries in h.
In the following, we first sample the tower vector h, and then the respective DAG accordingly. We conclude this subsection showing that with sufficiently high probability, we see only collider edges deep in the tower. Proof. Condition on the event B 1 and consider the events A i that there is a non-collider edge between sites with labels between k 7i/6 and k 7(i+1)/6 , i.e. we set for all i ∈ N. We claim that A i has P n -probability at most exp(−c 0 k 7i/6 ) for some universal constant c 0 > 0. Since we condition on B 1 , and there are at most k 7(i+1)/3 edges e = (v, w) which we have to consider for A i . Note that with probability at least 1 − exp(−c 1 k 7i/6 ) for some constant c 1 > 0, there are at least k 7i/6 /9 sites in U v = {u : ℓ(u) ≤ k 7i/6 /4} which are connected to w. All edges from a site in U v to the site v must be present in order to have e as a non-collider. Recalling Remark 2.4, this shows that for all n and k large enough for some constant c 2 > 0. We obtain (7.5) by a union bound over all admissible edges. Using another union bound on the events A i over i ∈ N, this finishes the proof. For k ∈ N, we say that v ∈ V with ℓ(v) ∈ [k/3, k 7/6 ] is k-good if the following holds: (1) For all i ∈ [4k 4/5 , k/3] ∩ Z, and j ∈ [4k 4/5 , k/3] ∩ [n − ℓ(v)], we have that The relative ordering of the site v is fully determined for all sufficiently distant sites, i.e. for all w with ℓ(w) ≥ ℓ(v) + 5k Similarly when (w, v) ∈ C(G) and ℓ(w) ≤ ℓ(v) − 5k i.e. a path of length two of collider edges from w to v. k-bad sites V 1 k-good sites V 2 Figure 5. Visualization of the decomposition into k-good and k-bad sites. We only draw the non-collider edges between k-good and k-bad sites. In order to apply Proposition 6.4, a main task is to bound the number of k-bad sites, drawn in red, which have a least one edge to some k-good site.
(4) The number of connections to the sites with label between k/5 and k/4 is typical, i.e.
All sites v with ℓ(v) ∈ [k/3, k 7/6 ], which are not k-good are called k-bad. In the sequel, we bound in the total number of k-bad sites, and the number of connections using non-collider edges to some k-good site; see also  Proof. Observe that on B 1 from (7.3), we have that a fixed site v with ℓ(v) ∈ [k/30, n−k 4/5 ] that each edge to a site w with ℓ(w) < ℓ(v) − k 2/3 or ℓ(w) > ℓ(v) + k 2/3 is present independently with probability 1 2 . Thus we see that for n and k sufficiently large the events ) for some universal constant c 0 , using the exponential Markov inequality. In total, let B 2 be the event that at most 2k 4/5 sites with ℓ(v) ∈ [k/3, k 11/10 ] do not satisfy property (1) in the definition of k-bad sites, and note that for all n and k sufficiently large for some constant c 1 > 0.
Next, in order to estimate the number of vertices which violate property (2), we condition on the event B 1 ∪ B 2 to hold. Let E 2 be a fixed set of k 1/2 many edges between sites v, w, which satisfy property (1). We claim that for all n and k sufficiently large (7.12) P n (e does not satisfy (2) for all e ∈ E 2 ) ≤ 1 5 exp(−c 2 k 11 10 ) holds for some universal constant c 2 > 0. With a union bound over at most k 2 k 1/2 choices of E 2 , this yields that there are with P n -probability at least 1 − exp(−c 3 k 11/10 ) for some universal constant c 3 > 0 at most 2k 1/2 sites which do not satisfy property (2). To see that (7.12) holds, we distinguish three cases. Suppose that there exists some site v and a set of sites W v with |W v | ≥ k 1/4 such that (w, v) ∈ E 2 for all w ∈ W v . Then by property (1), there are at least k 4/5 sitesW v with ℓ(u) ≥ ℓ(v) − 4k 4/5 for all u ∈W v adjacent to v. Whenever the event in (7.12) holds, all edges of the form (w, u) for w ∈ W v and u ∈W v must be absent, giving us the desired bound. The same argument applies when there exists some site v and a set of sites W ′ v with |W ′ v | ≥ k 1/4 such that (v, w) ∈ E 2 for all w ∈ W ′ v . In the remaining case, we have at least k 1/4 disjoint edges in E 2 , and again use that the edge endpoints satisfy property (1) to conclude (7.12).
Next, we turn to estimating the number of vertices which do not satisfy properties (3) and (4) in the definition of k-bad sites. We will only give a bound on the number of sites which do not satsify property (3), as the argument will be similar for property (4). Note that on the event B 1 , all edges between a site w with ℓ(w) ≤ k/16 and some v with ℓ(v) ≥ k/3 are present independently with probability 1 2 . Let B v 3 be the event that Observe that the events (B v 3 ) are independent, have the same probability, and thus for some constant c 3 > 0. Taking a union bound over the above events, we conclude. 7.4. Non-collider edges between good sites. We now give a bound on set S of noncollider edges with both endpoints being k-good and labels between k/3 and k 7/6 . Set (7.13) S k,G := (v, w) ∈ C(G) : ℓ(v), ℓ(w) ∈ {k/3, . . . , k 7/6 } and v, w are k-good for all k > 0. The non-collider edges between k-good and k-bad sites will be handled separately in the upcoming section.
Proof. In order to control the total number of non-collider edges with both endpoints of labels between k/3 and k 7/6 , fix some set S with (7.15) S = {a, b} : a, b ∈ V (G) and ℓ(a), ℓ(b) ∈ {k/3, . . . , k 7/6 } and |S| = k 4/5 . In order to show (7.14), it suffices prove for n and k large that (7.16) P n {v, w} ∈ C(E) : ℓ(v) = i and ℓ(w) = j for all (i, j) ∈ S ≤ exp(−ck 11/10 ) for any such fixed subset S, taking a union bound over the at most k 7/6 k 4/5 choices for such sets S. In the following, for each k-good site u, we denote by U 1 (u) the set of sites according to property (3), which have an edge to u, and by U c 1 (u) the set of sites v with ℓ(v) ∈ [k/20] such that v / ∈ U 1 (u), i.e. there is no edge between v and u.
Depending on the structure of the set S, we distinguish three cases. First, assume there exists some site s and a set of sites W (s) with |W (s)| ≥ k 2/3 such that {s, u} ∈ S and ℓ(u) ≥ ℓ(s) for all u ∈ W (s). Since s is k-good, we see that all edge of the form (v, u) for some v ∈ U c 1 (s) and u ∈ W (s) must be absent in order to have S as a set of non-collider edges. Since |U c 1 (u)| ≥ k/80 and |W (s)| ≥ k 2/3 , this allows us to conclude (7.16) for this choice of S. Next, suppose that there exists some site s and a set of sites W ′ (s) with |W ′ (s)| ≥ k 2/3 such that {u, s} ∈ S and ℓ(u) ≤ ℓ(s) for all u ∈ W ′ (s). In order to have S as a set of non-collider edges, all edges (u, w) for sites w ∈ W ′ (s) and u ∈ U 1 (s) must be present, allowing us to conclude (7.16) for this choice of S. Finally, if none of the above two cases holds, there exists a subset W ⊆ S of disjoint edges with |W | ≥ k 1/10 . For each of these edges (v, w), we must have that all edges of the form (v, u) for some u ∈ U 1 (w) are present. Since |U 1 (w)| ≥ k/80, and there are at at least k 1/10 choices for v, this allows us to conclude (7.16) for this choice of S, and thus finishes the proof. 7.5. Non-collider edges connecting to good sites. It remains to control the number of sites v which connect to some k-good site by a non-collider edge.
Lemma 7.6. There exists some universal constant c > 0 such that for all k ∈ N, with probability at least 1 − exp(−ck 11 10 ), there are at most k 1/10 sites v which are connected to some k-good site by a non-collider edge.
Proof. Observe that the property of being k-good does not depend on the edges having their lower endpoint in the bottom k/6 sites, and their upper endpoint between k/6 and k/3. In the following, we partition the sites v as For each k-good site w, recall that U 1 (w) denotes the set of sites according to property (3), which have an edge to w, and that U c 1 (w) is the set of sites v with ℓ(v) ∈ [k/20] such that v / ∈ U 1 (w). Similarly, we let U 2 (w) be the set of sites according to property (4), which have an edge to w, and U c 2 (w) the set of sites v with ℓ(v) ∈ [k/5, k/4] such that v / ∈ U 2 (w). We argue in the following for the sites in S i separately for each i ∈ [3].
For each site v ∈ S 1 , we define the event A 1 v := {∃ k-good w : (v, w) ∈ E and (u, v) ∈ E for all u ∈ U 1 (w) } . Note that A 1 v is a necessary condition to have a non-collider edge (v, w) for some k-good site w. Recall that |U 1 (w)| ≥ k/80 when w is k-good. Conditioning on the event B 1 , using the independence of the presence of these edges and a union bound over the sites w, we get P n (A 1 v | B 1 ) ≤ k 2 2 −k/80 for all n ∈ N sufficiently large. Since for a fixed set of k-good sites, the events A 1 v are independent, we see that for all n ∈ N sufficiently large, and all k ∈ [n 19/20 ] P n |v ∈ S 1 : (v, w) non-collider for some k-good w| ≥ 1 4 k 1 10 ≤ exp(−c 1 k 11/10 ) for some suitable constant c 1 > 0. Next, we define for each site v ∈ S 2 the event A 2 v := {∃ k-good w : (v, w) ∈ E and (v, u) ∈ E for all u ∈ U 2 (w) } . Similarly, we get that P n (A 2 v | B 1 ) ≤ k 2 2 −k/80 . for all n ∈ N sufficiently large, and all k ∈ [n 19/20 ]. Since the events A 2 v are independent, and a necessary condition to have a non-collider edge (v, w) for some k-good w, we obtain P n |v ∈ S 2 : (v, w) non-collider for some k-good w| ≥ 1 4 k 1 10 ≤ exp(−c 2 k 11/10 ) for some suitable constant c 2 > 0. It remains to consider the case where v ∈ S 3 . We define A 3 v := {∃ k-good w : ℓ(w) > ℓ(v) and (v, w) ∈ E and (u, v) ∈ E for all u ∈ U 1 (w) } , and obtain that for some constant c 3 > 0, all n ∈ N sufficiently large, and all k ∈ [n 19/20 ] P n |v ∈ S 3 : (v, w) non-collider for some k-good w with ℓ(w) ≥ ℓ(v)| ≥ 1 4 k 1 10 ≤ exp(−c 3 k 11/10 ) , using a similar argument as in the previous two cases. For the connection between k-bad sites in S 3 with respect to the remaining k-good sites below them, we define A 4 v := {∃ k-good w : ℓ(w) < ℓ(v) and (v, w) ∈ E and (u, v) / ∈ E for all u ∈ U c 1 (w) } . Note that the events A 4 v are independent for all v ∈ S 3 , and a necessary condition for having a non-collider edge, using property (3) of the k-good vertices. Since |U c 1 | ≥ k/80 for all k-good sites, we get that for all n ∈ N sufficiently large P n (A 4 v | B 1 ) ≤ k 2 2 −k/80 . Hence, we obtain that for some suitable constant c 4 > 0 and for all n ∈ N large enough P n |v ∈ S 3 : (v, w) non-collider for some k-good w with ℓ(w) < ℓ(v)| ≥ 1 4 k 1 10 ≤ exp(−c 4 k 11/10 ) .
Combining the above bound on the sites in S 1 , S 2 , and S 3 finishes the proof. Note that on the event B 1 , which holds with probability at least 1 − exp(−c 1 k 11 10 ) by Lemma 7.2 for some c 1 > 0, we get the first property in Proposition 6.4 with respect to a in (7.17). The second property in Proposition 7.1 holds with probability at least 1 − exp(−c 2 k 11 10 ) for some c 2 > 0 using Lemma 7.6 for b from (7.17). The third and forth property hold with probability at least 1 − exp(−c 3 k 11 10 ) for some c 3 > 0, using the construction of k-bad sites and Lemma 7.5. Combining Lemma 7.4 and Lemma 7.5. we have with probability at least 1 − exp(−c 4 k 11 10 ) for some c 4 > 0 that |V 1 | ≤ k/2. In total, we get (7.18) |M (G)| ≤ (k/2)! k 7/6 10k 4/5 ! k 1/10 ≤ k! with probability at least 1 − exp(−ck 11 10 ) for all k > 0 sufficiently large, and some constant c > 0. This finishes the proof.