Joint Degree Distributions Of Preferential Attachment -Books Pdf

JOINT DEGREE DISTRIBUTIONS OF PREFERENTIAL ATTACHMENT
17 Feb 2020 | 18 views | 0 downloads | 20 Pages | 227.73 KB

Share Pdf : Joint Degree Distributions Of Preferential Attachment

Download and Preview : Joint Degree Distributions Of Preferential Attachment


Report CopyRight/DMCA Form For : Joint Degree Distributions Of Preferential Attachment



Transcription

Joint degree distributions of preferential attachment random graphs 369. this distribution roughly decays proportional to k for some 0 this is the so called power. law behavior, In this paper we study the joint degree distribution for a linear preferential attachment model. where each entering node initially attaches to exactly 1 nodes In the 2 case we study. two mechanisms for attaching edges a sequential update rule and the lumping rule mentioned. above and note our results are strikingly different for the two rules We show weak convergence. with respect to p norm topology of the scaled degrees for the process started from any initial. seed graph to a limiting distribution that has a simple representation and provide an optimal. rate of convergence for the nite dimensional distributions. To state our results in greater detail we rst precisely de ne the random rules governing the. evolution of the models we study We distinguish between two cases one that allows for loops. and the other that does not in fact the two can be related see Lemma 1 below but we present. the results separately for the sake of clarity, Our results are stated in terms of weights of vertices but our weights can be thought of as. in degree plus one since in the models vertices are born with weight 1 and each time a vertex. receives a new edge from another vertex its weight increases by 1 Fix 1 and let dk n. denote the weight of vertex k in the graph G n Assume that the seed graph G 0 has s vertices. with labels 1 s and with initial weights d1 ds note that di di 0 We construct. the graph G n with n vertices from G n 1 having n 1 edges in two possible ways. 1 0 1 Model N Given the graph G n 1 having s n 1 vertices G n is formed by. adding a vertex labelled s n and sequentially attaching edges between it and the vertices of. G n 1 according to the following rules The rst edge attaches to vertex k with probability. s n 1 1 k n 1,i 1 di n 1, denote by K1 the vertex which received that rst edge The weight of K1 is updated immediately. so that the second edge attaches to vertex k with probability. dk n 1 1 k K1,i 1 di n 1, where 1 is the indicator function The procedure continues this way edges attach with. probability proportional to weights at that moment and additional received edges add one to. the weight of a vertex until vertex n has outgoing edges Finally we set ds n n 1 and. let G n be the resulting graph Note that multiple edges between vertices are possible. 1 0 2 Model L Given the graph G n 1 having s n 1 vertices G n is formed by adding. a vertex labelled s n having weight ds n n 1 1 and attaching edges between it and. the vertices labelled 1 s n so loops are possible The rst edge attaches to vertex k. with probability,i 1 di n 1, denote by K1 the vertex which received that rst edge As in model N the weight of K1 is.
updated immediately and the procedure continues in this way until edges are added and we. call G n the resulting graph, Note that if 1 then the weights can be interpreted as the total degree since each additional. vertex has out degree 1 and in this case the N1 model is just the usual Barab si Albert. preferential attachment tree, Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5. 370 E PEK Z ET AL, In the next section we state our nite dimensional results process level statements are in. Section 1 2,1 1 Finite dimensional degree distributions. Key to both understanding and obtaining our results is to focus on the joint cumulative degree. counts rather than the joint degree counts Write X GG a b with a 0 and b 0 for. a random variable X having the generalized gamma distribution with density proportional to. x a 1 e x on x 0 and Y beta a b for a 0 and b 0 if Y has density proportional to. x 1 x b 1 on 0 x 1, 1 Fix a seed graph G 0 having s vertices and weight sequence d1 ds and let.
mk ki 1 di for 1 k s Assume that either, i G n follows model N in which case let ak ms 1 k s for k s or. ii G n follows model L in which case let ak ms 1 k s for k s. Fix r s and let B1 Br 1 and Zr be independent random variables with distributions. beta mk dk 1 if 1 k s,beta ak 1 if s k r,and Zr GG ar 1 De ne the products. Zk Bk Br 1 Zr 1 k r, and let Z Z1 Zr and Y Z1 Z2 Z1 Zr Zr 1 Denote the scaled weight. sequence of the rst r vertices of G n by,D n D1 n Dr n d1 n dr n. Then there is a positive constant C C r ms such that. sup P D n K P Y K 1 for all n 1, where the supremum ranges over all convex subsets K Rr.
Remark 1 The error rate n 1 is the best possible since the rate of convergence of a. scaled integer valued random variable to a limiting distribution with nice density is bounded. from below by the scaling nice means uniformly bounded away from 0 on some interval see. 19 Lemma 4 1 Also a bound on the constant C r ms could in principle be made explicit. with our methods but with much added technicality Such a constant would increase in each. of its arguments We emphasize that obtaining optimal rates in multidimensional distributional. limit theorems for the metric we are using is in general neither easy nor common. Since the sets x1 xr max x1 xr t are convex in Rr we immediately obtain. the following corollary to the theorem, Corollary 1 Let D and Y be as in Theorem 1 under either i or ii Then there is a positive. constant C C r ms such that,sup P max Dk n t P max Yk t 1 for all n 1. t 0 1 k r 1 k r n, Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5. Joint degree distributions of preferential attachment random graphs 371. The representation of the limits appearing in Theorem 1 is a sort of backward construction. started from Zr Our next result is an alternative forward construction that is useful for des. cribing the in nite limit L Z1 Z2 compare to the forthcoming process level discussion. Denote by gamma r a gamma distribution with shape parameter r 0 and rate parameter. 0 having density proportional to x r 1 e x x 0, Proposition 1 Let B1 Bs 1 and as be as in Theorem 1 and let X1 X2 be independent. with X1 gamma as 1 1 and Xk gamma 1 1 k 2 Then the random vector Z. in Theorem 1 has the representation Z Z where,Bk Bs 1 X1 if 1 k s.
X1 Xk s 1 1 1 if k s, Proof We need to check that the representation above has the same distribution as that of. Theorem 1 The two representations are identical for k 1 s 1 For k s that the. joint distributions continue to agree is an easy consequence of induction and the beta gamma. algebra which implies that for k s,X1 Xk s 1 1,X1 Xk s 1 1 1. where V beta as 1 k s 1 1 is independent of Zk A simple calculation. shows that V 1 1 beta as 1 k s 1 1 which is the same distribution as. Bk 1 Continuing in this way yields the proposition. Remark 2 Proposition 1 leads to rather clean representations of the limits appearing in The. orem 1 for particular choices of a seed graph If the seed graph G 0 has one vertex with. d1 1 and G n is formed according to model L alternatively the seed graph has two. vertices with d1 1 and d2 1 following model N then Proposition 1 implies that. 0 Z1 Z2 are the points of an inhomogeneous Poisson point process on the positive. line with intensity 1 t dt, 1 2 Process level convergence and order statistics. Using Kolmogorov s extension theorem for any choice of seed graph and generative mech. anism the distribution of the vector Y in Theorem 1 can be uniquely extended to obtain an. in nite vector Y Y1 Y2 which we can take to be of the form Yi Zi Zi 1 for. 0 Z1 Z2 given explicitly by the forward construction of Proposition 1 It is. immediate from Theorem 1 that D n D1 n Dn n 0 viewed as an in nite. sequence by appending zeros converges weakly to Y with respect to the product topology. However weak convergence with respect to this topology does not yield much at the process. level for example restricting to bounded sequences it does not imply convergence of the. sequence of maximums to the maximum of the limit and so we show weak convergence with. respect to a topology that is strong enough to imply weak convergence of order statistics. For 1 p let lp be the usual sequence space endowed with the norm. p Moreover, denote by lp lp the subspace of sequences having nonnegative entries along with the topology. inherited from lp Clearly D n lp for all n 1 For x lp denote by x the sequence. with the entries of x appearing in decreasing order clearly x lp. Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5. 372 E PEK Z ET AL, We have the following result which greatly generalizes the convergence of the maximum of.
the rst r coordinates of D n in Corollary 1 to the order statistics of the entire sequence D n. Theorem 2 Let Y and D n be the in nite extensions of the random vectors Y and D n of. Theorem 1 as just described Then Y lp almost surely for any p 1 Moreover for. 1 and any p 4 or 2 and any p 1 the sequences L D n and L D n. converge weakly to L Y and L Y with respect to the lp topology. 1 3 Idea of the proofs of Theorem 1 and Theorem 2, The representation of the limit vector in Theorem 1 is integral to our approach It says. that in the limit for k s conditional on coordinate Zk 1 the previous coordinate Zk is an. independent beta variable multiplied by Zk 1 On the other hand for k s conditional on. the sum of the weights of the rst k 1 vertices say Sk 1 n it is not too dif cult to see that. the sum of the weights of the rst k vertices Sk n will be distributed as a classical P lya. urn run for a number of steps of the order Sk 1 n see Lemma 2 below Furthermore P lya. urns limit to beta variables so L Sk n L Bk Sk 1 n where Bk is an appropriate beta. variable independent of Sk 1 n see Lemma 3 below an extension of 21 Lemma 4 4 which. gives a new bound on the Wasserstein distance between P lya urns and beta distributions The. limits satisfy this approximate identity exactly that is Zk Bk Zk 1 Once we take care of. the error made in swapping out P lya urns for betas done via a telescoping sum argument. all that is left is to show that Zr is close to Sr n which follows by the results of Pek z et. al 21 For Theorem 2 we establish weak convergence of the distribution of the sequence. D n to the distribution of Y with respect to lp topology by verifying a tightness criterion for. probability measures on lp and then applying Theorem 1 to show the convergence of nite. dimensional distributions The convergence of the distribution of D n follows from the. continuous mapping theorem applied to the ordering function. 1 4 Related work, To the best of the authors knowledge all of the results above for 2 are new The. sequential edge model was studied by Berger et al 5 where they gave a beautiful description. of the limiting structure of the graph started from a random vertex and performing a depth rst. search That work is complementary to ours as the number of vertices n the depth rst. search started from a uniformly chosen vertex only sees vertices of order n and these do not. appear in our limits, For 1 the limiting marginal distribution of the degree of the ith vertex are described. in different ways in 13 after relating these variables to an appropriate triangular urn model. and 19 Theorem 1 1 Proposition 2 3 In the latter paper models 1 and 2 are our models N1. with s 2 and d 1 d2 1 and L1 with s 1 and d1 2 respectively and their scaling is. a constant times n For model N1 they identify the distributional limit of Di n for i 2. note that vertices 1 and 2 have the same distribution in this model as 1 B1 2 i 3 2 1 2 where. 1 gamma 1 1 is independent of B1 2 i 3 2 beta 21 i 23 In model L1 the analogous. limit can be written as 1 B1 2 i 1 1 2 interpreting B1 2 0 1 Using our description of. these limits given by Proposition 1 we nd that for X1 2 gamma 21 1 independent of. X1 X2 independent and identically distributed i i d random variables with distribution. X1 2 X1 Xi 1 X1 2 X1 Xi 2 1 B1 2 i 3 2,X1 X2 Xi X1 X2 Xi 1 1 B1 2 i 1. Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5. Joint degree distributions of preferential attachment random graphs 373. These intriguing distributional identities are not easily interpretable but they can be directly. veri ed by comparing Mellin transforms It would be of interest to obtain a representation of. the joint distributions similar in appearance to the right hand side of these identities. Still assuming that 1 there are some existing results about properties and characteri. zations of limits of the joint degrees of xed vertices and maximums of such but only started. from certain seed graphs Especially close to our work in this special case is M ri 16 who. used martingale arguments to show that 2D n n 1 in model N1 with s 2 and d1 d2 1. has an almost sure limit denoted by 1 2 which must have the same distribution as 2Y. though the description of the limiting i previously given is not so explicit moment formula. are given and can be checked to agree with those of 2Y and some other properties are derived. For example M ri 16 Lemma 3 4 with 0 showed that the variables. are beta 2j 1 1 and that 1 r 1 r are independent This coincides with. our description of the limits in Theorem 1 See also 12 Section 2 for a discussion of these. representations in this and related models Again using martingales M ri 16 Theorem 3 1. showed that maxi 1 Di n n 1 converges almost surely and in Lp for p 1 to maxi 1 i. Thus we can identify the distribution of this limit as that of 2 maxi 1 Yi. Our work generalizes and extends these existing results for the 1 case in several. directions The rates of convergence in Theorem 1 and Corollary 1 are new as are the. descriptions of the limiting joint degrees even for simple seed graphs where existing results are. available At the process level our lp convergence complements the almost sure convergence. of the sequence and maximum given by M ri 16 for the basic seed graph as well as covering. much more allowing different seed graphs and giving convergence of the order statistics. 1 4 1 A different multiedge preferential attachment graph An alternative way to de ne a. preferential attachment model where each new node attaches to 1 nodes was given by. Bollob s et al 6 The model begins by generating a random graph according to model L1. or N1 with n nodes denoted G n and then for each of i 1 n collapsing nodes. i 1 1 i into one node keeping all of the edges so there may be loops in both. models But with this de nition the degree of the ith node is just the sum of the degrees of. nodes i 1 1 i in G n and so the nite dimensional limits can be read from. Theorems 1 Moreover since a linear transformation of a convex set is convex the analogous. error rates of the theorem in this more general setting also hold An important remark is that this. multiedge preferential attachment graph is fundamentally different than that introduced above. in this model the degree of a xed vertex grows like n for any where as in models N. and L the degree grows like n 1 Also note that using the representation of Proposition 1. summing the limiting distributions of the degrees of adjacent vertices has a particularly simple. form due to telescoping For example for model L1 started from a single loop so s 1 and. d1 2 the joint distributional limits of the scaled degrees of nodes i 1 r in G n. are given by,X1 X i X1 X i 1, where X1 X2 are i i d and have distribution gamma 1 1.
Similarly at the process level the lumping operation maps lp to lp since by H lder s. inequality for numbers x1 x,x1 x p p 1 x1 p x p, Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5. 374 E PEK Z ET AL, The lumping is also Lipschitz continuous since for x y in lp. x y x i 1 j y i 1 j p,i 1 j i 1 j,i 1 j 1 j 1 i 1 j 1. So by the continuous mapping theorem we can easily read the limits of the degrees for the. lumped graph from those of the original graph given in Theorem 2 We do not provide a formal. statement of our results for this case because it is a straightforward derivative of the 1 case. 1 4 2 Connection to the Brownian continuum random tree Consider model L1 started from. a loop so s 1 and d1 2 If we write Si n ij 1 Dj n then Proposition 1 and the. results of M ri 16 discussed above imply that for r 1 the scaled sums of degree counts. S1 n Sr n X1 X1 X2 X1 Xr, where the Xi are i i d and have distribution gamma 1 1 These are the points of an inho. mogeneous Poisson point process with intensity 2t dt which also arises in Aldous continuum. random tree CRT construction see 1 and 2 and is described by Pitman 24 around. Theorem 7 9 The explicit connection is that if we consider G n plus the not yet attached. half edge of vertex n 1 then there are 2n 1 degrees which can be bijectively mapped to a. binary tree with n 1 leaves The bijection is de ned through R my s algorithm for generating. uniformly chosen binary plane trees see the discussion in 21 Remark 2 6 The algorithm. begins with a binary tree with two leaves and a root corresponding to the two starting degrees. of the loop and the half edge of the second vertex in model L1 In R my s algorithm leaves. are added to the tree by selecting a possibly internal vertex uniformly at random and inserting. a cherry at this vertex that is insert a graph with three vertices and two edges with the elbow. oriented towards the root of the binary tree so two vertices one of which is a leaf are added. at each step and these correspond to the two degrees of each edge added in the preferential. attachment model The number of vertices in the spanning tree of the rst k leaves added in. R my s algorithm is exactly the sum of the degrees of the rst k vertices in model L1 started. from a loop If the leaves are labelled in the order they appear the initial two leaves labelled. 1 and 2 then this leaf labelling is uniform which implies that if we rst choose a uniform. random binary plane tree with n 2 leaves and then k n leaves uniformly at random and. x a labelling 1 k then for Tj n de ned to be the number of vertices in the spanning tree. containing the root and the leaves labelled 1 j we have. S1 n Sk n T1 n Tk n, Theorem 1 provides a rate of convergence of this random vector to its limit.
We can now clearly see the connection to the CRT since according to Aldous 2 uniform. random binary plane trees converge to Brownian CRT and the number of vertices in the spanning. tree of k randomly chosen leaves in a uniform binary tree of n leaves converges to the length. of the tree induced by Brownian excursion sampled at k uniform times as per Pitman 23 24. Theorem 7 9 and it is known that these trees are formed by combining branches with lengths. given by a Poisson point process on the positive line with intensity proportional to t dt. 1 4 3 A statistical application Is it possible with probability greater than 21 to tell the difference. between two preferential attachment graphs started from nonisomorphic seeds and run for a. Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5. Joint degree distributions of preferential attachment random graphs 375. long time This question is posed in the 1 case by Bubeck et al 7 where the answer was. determined to be yes as long as the degree sequences of the seeds are different The crucial. step is to separate the two graphs based on the maximum degree which relies on a careful. understanding of the maximum degree along the lines of Corollary 1 In fact by exploiting the. connection to the Brownian CRT just mentioned along with other results the answer to the. question can be strengthened to yes as long as the two seed graphs are nonisomorphic see 9. 1 4 4 Organization of the paper To show Theorems 1 and 2 we relate the weight distributions. of both models N and L to a single in nite color urn model that generalizes the single. color models considered in 13 19 and 21 urn models frequently appear when studying. preferential attachment see for example 3 5 19 20 22 and 25 In the next. section we de ne the relevant in nite color urn model and make explicit the equivalence to. the preferential attachment models under study In Section 2 we state and prove a general. approximation result from which Theorem 1 follows Section 3 contains the proof of Theorem 2. 1 5 An in nite color urn model, Consider the following in nite color urn model At step 0 there are s 1 distinct colors. present in the urn and we assume that these colors are labelled from 1 to s Fix an integer. 1 At the nth step a ball is picked at random from the urn and returned along with an. additional ball of the same color Additionally if n is a multiple of a ball of the new color. s n is added after the nth draw, We are interested in the cumulative color counts that is for each k 1 let Mk n be the. number of balls of colors 1 to k in the urn after the nth draw and possible immigration has. been completed Let mk be the number of balls of colours 1 to k at time 0 so that Mk 0 mk. In order to avoid degeneracies we will assume that at time 0 at least one ball of each color. from 1 to s is present that is m1 1 and mk 1 mk 1 for 1 k s. The following result makes explicit the connection between the urn model just described and. the preferential attachment models under study It follows from straightforward considerations. Lemma 1 Fix a seed graph G 0 with s vertices and let d1 ds be the initial weight. sequence Let 1 and consider either the situation of. i model N for the graph sequence and an in nite color urn model having initially dk balls. of color k where 1 k s or, ii model L for the graph sequence and an in nite color urn model having initially dk balls. of color k where 1 k s and one ball of color s 1,Then for any r and n r. d1 n d1 n d2 n d1 n dr n M1 n Mr n,2 Proof of Theorem 1.
Theorem 1 easily follows from the next result proved immediately after its statement the. fact that linear transformations of convex sets are convex and Lemma 1. Proposition 2 Fix r s Let B1 Br 1 and Zr be independent random variables such. beta mk mk 1 mk if 1 k s,beta ms 1 k s 1 if s k r, Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5. 376 E PEK Z ET AL,and Zr GG ms 1 r s 1 De ne,Zk Bk Br 1 Zr 1 k r Z Z1 Zr. W n W1 n Wr n M1 n Mr n, Then there is a positive constant C C r ms independent of n such that. sup P W n K P Z K for all n 1, where the supremum ranges over all convex sets K Rr. We need some intermediate lemmas to prove Proposition 2 Denote by P wb m the. distribution of white balls in a classical P lya urn after m completed draws starting with b. black and w white balls Denote by PIm b m the number of white balls after m completed. steps in the following P lya urn with immigration starting with b black and w white balls at. the nth step a ball is picked at random from the urn and returned along with an additional ball. of the same color additionally if n is a multiple of then a black ball is added after the nth. draw and return,Lemma 2 Let p k s 1 If k s we have.
Furthermore conditionally on Mk 1 n we have,P M n m if 1 k s. P Mk 1 n ms 1 p if k s, Proof To prove 2 rst note that the number of balls having a color from the set 1 k. is deterministic up to the point where the rst ball of color k 1 appears in the urn this is the case. after p k s 1 completed draws At that time we have Mk p 1 ms 1 p. so that Mk p ms p k s After that consider all balls of colors 1 k as white. balls and all balls of colors k 1 as black balls The number of white balls for the. remaining n p steps now behaves exactly like PIm b m with b 1 w m p k s. To prove the second line of 3 consider all balls of colors 1 k as white balls and balls. of color k 1 as black balls After time p the number of white balls now behaves exactly. like P wb m with b 1 w Mk p and m being the number of times a ball among colors. 1 k 1 was picked after time p which is just Mk 1 n ms 1 p. The argument to prove the rst line of 3 is similar and therefore omitted. We will need the following coupling of P lya urns and beta variables that is a generalization. from the b 1 case of 21 Lemma 4 4 for related distributional approximation results. Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5. Joint degree distributions of preferential attachment random graphs 377. Lemma 3 Fix positive integers b w and n There is a coupling X Y with X P wb n. and Y beta w b such that almost surely, Proof We use induction over b and start with the base case b 1 Let V0 Vw 1 be. independent and uniformly distributed on the interval 0 1 By a well known representation. of the distribution beta w 1 we can choose,Y max V0 Vw 1. To construct X rst note that for P w1 m A denoting the probability the relevant P lya urn. law puts on the set A Z we have, for all m 0 and for w t w m see for example 10 Equation 2 4 p 121 For each.
N m max k m w k Vk, It is easy to see that the cumulative distribution function of N m is that of P w1 m for each m. N m mY w 1 for all m 0 5, Letting X N n 4 follows for the b 1 case As a side remark note that although. N m P w1 m for each m the joint distribution of N 0 N 1 is not that of a P lya. urn process, To prove the inductive step assume we have constructed Nb 1 0 Nb 1 1 and Yb 1. such that Nb 1 m P b 1,w m for all m 0 Yb 1 beta w b 1 and. Nb 1 m mYb 1 for all m 0, Now let Yb beta w 1 be independent of all else and N 0 N 1 be de ned and.
coupled to Y as in the base case that is N m P w1 m such that N m mY w 1. Nb m N Nb 1 m w b 1, It is not dif cult to see that Nb m P wb m Also it is not dif cult to see that Yb. Yb 1 Y beta w b Noting from 5 that for any y 0,N m yY N m mY m y Y w 1 m y. Nb m mYb N Nb 1 m w b 1 mYb 1 Y,w 1 Nb 1 m w b 1 mYb 1. This concludes the inductive step where 4 is just the m n case. Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5. 378 E PEK Z ET AL, The last ingredient we need to prove Proposition 2 is some moment information. Lemma 4 For any k s and q 1 2 we have,EMk n q nq 1 6.
and for w ms 1 k s and t n k s 1,E Mk n Mk n 1 Mk n. w 1 t 1 t w 1 t 1 t,w 1 1 t 1 7,ms 1 k s n 1 O n 1. Furthermore 1,lim sup E 8, Proof The asymptotic 6 follows from 21 Lemma 4 1 From that lemma we also have. for Y PIm w,E Y Y 1 Y w j 1, Setting T t 1 using careful bookkeeping and a telescoping argument we obtain. w 1 i k 1 w 1 m T,j 0 k 0 i 0 m T,w w 1 i 1 T 1,w w 1 i 1 T 1.
w w 1 i 1 T w 1 m 1 T 1,w w 1 i T t w 1 m T t,i 0 m T t 1. w 1 T t w 1 T t, Setting w ms 1 k s and t n k s 1 as per 2 yields 7. Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5. Joint degree distributions of preferential attachment random graphs 379. In order to prove 8 let,t and Y PIm, where w ms 1 k s 1 From 2 and 21 Lemma 4 2 we have. for any bounded function f in particular for the function f x 1 x bounded when x 1. By 6 EY n 1 from which 8 easily follows, Note that the Landau O notation of the lemma contains a constant that depends on k. and both of ms s But here and below we ignore the dependence of constants on s when also. depending on ms through the inequalities 1 s ms, Proof of Proposition 2 To ease notation we x n and drop it in our variable notation and.
write for example Wk instead of Wk n For k l let,Kk l Bk Bl Vk l Kk l 1 Wl Vl l Wl. We may assume that B1 Br 1 are all independent of W W n Fix a convex subset. K Rr assuming without loss of generality that K is closed and let h be the indicator function. of K We proceed in two major steps by writing,P W K P Z K Eh W Eh Z. E h W h V1 r Vr r E h V1 r Vr r h Z, In order to bound R1 rst write it as the telescoping sum. R1 h V1 1 Vr r h V1 r V2 r Vr r,h V1 k Vk 1 k Vk k Vk 1 k 1 Vr r. h V1 k 1 Vk 1 k 1 Vk k 1 Vk 1 k 1 Vr r, Fix k and de ne bk and wk to be the parameters of the P lya urn in Lemma 2 that is.
mk 1 mk if 1 k s,mk if 1 k s,ms k s 1 k s if k s, Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5. 380 E PEK Z ET AL, Conditioning on Mk 1 we can use Lemmas 2 and 3 to conclude that there is a coupling Xk Yk. Xk P Mk 1 ck Yk beta wk bk,such that almost surely. bk 4wk bk 1,Xk Mk 1 ck Yk,mk 1 if 1 k s,ms 1 k s 1 if k s. Hence there is a constant C k ms and a random variable Ek with Ek C k ms almost. surely such that,Vj k Kj k 1 Xk Kj k 1 Wk 1 for 1 j k.
1 n 1 Mk 1,Vj k 1 Kj k 1 Yk Mk 1 Kj k 1 Yk Wk 1 for 1 j k 1. Vj j Vj j for j k Vj j Vj j for j k 1,Note that by Lemma 2. L Vj k L Vj k and,L Vj k 1 L Vj k 1 hence we have,R1 k h V1 k Vk 1 k Vk k Vk 1 k 1 Vr r. h V1 k 1 Vk 1 k 1 Vk k 1 Vk 1 k 1 Vr r, where we de ne in notation anticipating future conditioning. g x h K1 k 1 xWk 1 Kk 1 k 1 xWk 1 Wk 1 Wr, Let Fk be the algebra generated by B1 Bk 1 Ek and W hence also Mj rj 1 Since.
h is the indicator function of a convex set and since linear transformations of convex sets result. again in convex sets conditional on Fk it follows that g is of the form g x 1 a x b. for a b which are random but Fk measurable Hence,E R1 k Fk P a Yk a Fk. P b Yk b Fk,2 sup P x Yk x Fk,x R Mk 1 Mk 1, Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5. Joint degree distributions of preferential attachment random graphs 381. for some constant C C k ms and where the last inequality follows from basic properties. of the beta distribution Hence by 8 of Lemma 4,E R1 k E 1 9. for some constant C C k ms,In order to bound R2 write. R2 h K1 r 1 Kr 1 r 1 1 Wr h K1 r 1 Kr 1 r 1 1 Zr,g x h K1 r 1 Kr 1 r 1 1 x.
Given K1 r 1 Kr 1 r 1 the function g is again of the same form as in the rst part of the. proof so that,E R2 2 dKol L Wr L Zr 10, where dKol denotes the Kolmogorov distance i e the supremum distance between distribution. functions De ne the scaling constants,1 n 1 1 EMr n 1. 1 ms 1 r s,Since the Kolmogorov distance is scale invariant. dKol L Wr L Zr dKol L L,dKol L L Zr dKol L Zr L,R2 1 R2 2 11. From 21 Theorem 1 2 we have R2 1 O n 1 and noting that the density of Zr is. bounded standard arguments yield R2 2 O 1 n n To bound 1 n n use 6. and 7 to nd,EMr n 1 E Mr n Mr n O n 1,1 O n 1 O n 1.
ms 1 r s n,ms 1 r s n O n 1,Using this last expression we easily nd. 1 O n 1 1 1, Now using the fact that for 0 x 1 1 x 1 1 1 x 1 we nd n n. 1 O n 1 and so R2 2 O n 1 Now collecting the bounds 9 11 we are. able to prove 1, Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5. 382 E PEK Z ET AL,3 Proof of Theorem 2, Since Theorem 1 establishes convergence of nite dimensional distributions to prove the. claimed convergence of D n n 1 we need to show tightness in lp for the relevant p In the. next section we state and prove an lp tightness criteria in terms of moment conditions and then. in Section 3 2 we bound the relevant moments appropriately In Section 3 3 we establish the. continuity of the ordering function on lp and put everything together to prove Theorem 2 in. Section 3 4,3 1 Tightness in lp, The following result is essentially Suquet s 27 Section 6 Theorem 16 but we give a.
self contained proof, Lemma 5 Let X n X1 n X2 n n 1 be a sequence of lp valued random. elements where 1 p If,i supn 1 i 1 E Xi n p and,ii limk supn 1 i k E Xi n p 0. then the sequence of probability measures P X n n 1 is tight in the lp topology. Proof By the Fr chet Kolmogorov theorem B lp is relatively compact if it is bounded. lim sup xi p 0, Thus for any C 0 and any strictly increasing sequence of numbers 1 k1 k2 the. K C km m 1 x lp xi C and,for all m 1,is lp compact. Now x 0 From i we conclude that there is C such that. P Xi n p C E Xi n p for all n 1, From ii we conclude that there is a sequence 1 k1 k2 such that for all m 1.
P Xi n p m E Xi n p m 1 for all n 1, For this C and km m 1 we conclude that for all n 1. P X n K C km m 1 P Xi n p C P Xi n p,i 1 m 1 i km, Downloaded from https www cambridge org core Boston University Pappas Law Library on 09 Nov 2017 at 20 04 00 subject to the Cambridge Core terms of. use available at https www cambridge org core terms https doi org 10 1017 apr 2017 5.


Related Books

Chapter 13 - Gases

Chapter 13 Gases

190 Study Guide for An Introduction to Chemistry Section Goals and Introductions Section 13.1 Gases and Their Properties Goals To describe the particle nature of both real and ideal gases. To describe the properties of gases that can be used to explain their characteristics: volume, number of particles, temperature, and pressure.

National curriculum tests Key stage 1 - gov.uk

National curriculum tests Key stage 1 gov uk

Assessment framework for the development of the Year 1 phonics screening check For test developers National curriculum tests Key stage 1

GETTING STARTED GUIDE - Accela Developer Portal

GETTING STARTED GUIDE Accela Developer Portal

software. All other company names, product names, and designs mentioned herein ... version 3.0 of Accela ... The /Library folder is hidden by default in Mac OS X ...

Radiation Safety Information Computational Center

Radiation Safety Information Computational Center

standardized method of analysis for the evaluation of nuclear fuel facility and package designs ... Intel Mac OSX and personal ... RASCAL Version 3.0.5 with ...

Multinational Business Finance - Pearson Education

Multinational Business Finance Pearson Education

Multinational Business Finance, Fifteenth Edition, is aimed at university level courses in international financial management, international business finance, international finance, and similar titles. It can be used at either the graduate level or in executive education and corporate learning courses.

What is a Cover Letter?

What is a Cover Letter

Emailing a Cover Letter Communicating professionally is essential when exchanging emails with potential employers. You can save your cover letter as a PDF and attach it with your resume separately in the same email -OR-you could make the body of your email your cover letter.

Adafruit Hallowing M4

Adafruit Hallowing M4

rearranged. We've got both Arduino and CircuitPython build support for it so you can pick your favorite development language! The extra 8 MB of SPI Flash is great for sound effects projects where you want to play up to 3 minutes of WAV files. On each side of the Hallowing are JST-PH plugs for connecting external devices. The 3-pin JSTs connect ...

Making the most of technology in education - Nesta

Making the most of technology in education Nesta

excitement surrounding a technology-enabled school-system of the future and the reality of technology in most classrooms today. This report examines nine examples - three in Italy, three in the rest of . Europe, and three in the rest of the world - of inspiring practice where technology is impacting on large numbers of teachers and learners.

Reimagining the Role of Technology in Higher Education

Reimagining the Role of Technology in Higher Education

This document is an outgrowth of the 2016 National Education Technology Plan (NETP). The NETP presents a shared vision and call to action for transformational learning enabled by technology at all levels of our education system. Building on the work of leading educa-