Abstract Abstract-We investigate the secure connectivity of wireless sensor networks under the pairwise key distribution scheme of Chan et al.. Unlike recent work which was carried out under the assumption of full visibility, here we assume a (simplified) communication model where unreliable wireless links are represented as on/off channels. We present conditions on how to scale the model parameters so that the network i) has no secure node which is isolated and ii) is securely connected, both with high probability when the number of sensor nodes becomes large. The results are given in the form of zero-one laws, and exhibit significant differences with corresponding results in the full visibility case. Through simulations these zero-one laws are shown to be valid also under a more realistic communication model, i.e., the disk model. I. INTRODUCTION Wireless sensor networks (WSNs) are distributed collections of sensors with limited capabilities for computations and wireless communications. It is envisioned [1] that WSNs will be used in a wide range of applications areas such as healthcare (e.g. patient monitoring), military operations (e.g., battlefield surveillance) and homes (e.g., home automation and monitoring). These WSNs will often be deployed in hostile environments where communications can be monitored, and nodes are subject to capture and surreptitious use by an adversary. Under such circumstances, cryptographic protection will be needed to ensure secure communications, and to support functions such as sensor-capture detection, key revocation and sensor disabling. I. INTRODUCTION Unfortunately, many security schemes developed for general network environments do not take into account the unique features of WSNs: Public key cryptography is not feasible computationally because of the severe limitations imposed on the physical memory and power consumption of the individual sensors. Traditional key exchange and distribution protocols are based on trusting third parties, and this makes them inadequate for large-scale WSNs whose topologies are unknown prior to deployment. We refer the reader to the papers [6] , [11] , [20] for discussions of the security challenges in WSN settings. I. INTRODUCTION Random key predistribution schemes were introduced to address some of these difficulties. The idea of randomly assigning secure keys to sensor nodes prior to network deployment was first introduced by Eschenauer and Gligor [11] . Since then, many competing alternatives to the Eschenauer and Gligor (EG) scheme have been proposed; see [6] for a detailed survey of various key distribution schemes for WSNs. With so many schemes available, a basic question arises as to how they compare with each other. Answering this question passes through a good understanding of the properties and performance of the schemes under consideration, and this can be achieved in a number of ways. The approach we use here considers random graph models naturally induced by a given scheme, and then develops the scaling laws corresponding to desirable network properties, e.g., absence of secure nodes which are isolated, secure connectivity, etc. This is done with the aim of deriving guidelines to dimension the scheme, namely adjust its parameters so that these properties occur with high probability as the number of nodes becomes large. I. INTRODUCTION To date, most of the efforts along these lines have been carried out under the assumption of full visibility according to which sensor nodes are all within communication range of each other; more on this later: Under this assumption, the EG scheme gives rise to a class of random graphs known as random key graphs; relevant results are available in the references [3] , [8] , [11] , [18] , [24] . The q-composite scheme [7] , a simple variation of the EG scheme, was investigated by Bloznelis et al. [4] through an appropriate extension of the random key graph model. Recently, Yagan and Makowski have analyzed various random graphs induced by the random pairwise key predistribution scheme of Chan et al. [7] ; see the conference papers [25] , [26] . I. INTRODUCTION To be sure, the full visibility assumption does away with the wireless nature of the communication medium supporting WSNs. In return, this simplification makes it possible to focus on how randomization of the key distribution mechanism alone affects the establishment of a secure network in the best of circumstances, i..e., when there are no link failures. A common criticism of this line of work is that by disregarding the unreliability of the wireless links, the resulting dimensioning guidelines are likely to be too optimistic: In practice nodes will have fewer neighbors since some of the communication links may be impaired. As a result, the desired connectivity properties may not be achieved if dimensioning is done according to results derived under full visibility. I. INTRODUCTION In this paper, in an attempt to go beyond full visibility, we revisit the pairwise key predistribution scheme of Chan et al. [7] under more realistic assumptions that account for the possibility that communication links between nodes may not be available -This could occur due to the presence of physical barriers between nodes or because of harsh environmental conditions severely impairing transmission. To study such situations, we introduce a simple communication model where channels are mutually independent, and are either on or off. An overall system model is then constructed by intersecting the random graph model of the pairwise key distribution scheme (under full visibility), with an Erdős-Rényi (ER) graph model [5] . For this new random graph structure, we establish zeroone laws for two basic (and related) graph properties, namely graph connectivity and the absence of isolated nodes, as the model parameters are scaled with the number of users -We identify the critical thresholds and show that they coincide. To the best of our knowledge, these full zero-one laws constitute the first complete analysis of a key distribution scheme under non-full visibility -Contrast this with the partial results by Yi et al. [28] for the absence of isolated nodes (under additional conditions) when the communication model is the disk model. Although the communication model considered here may be deemed simplistic, it does permit a complete analysis of the issues of interest, with the results already yielding a number of interesting observations: The obtained zero-one laws differ significantly from the corresponding results in the full visibility case [25] . Thus, the communication model may have a significant impact on the dimensioning of the pairwise distribution algorithm, and this points to the need of possibly reevaluating guidelines developed under the full visibility assumption. Furthermore, simulations suggest that the zero-one laws obtained here for the on/off channel model may still be useful in dimensioning the pairwise scheme under the popular, and more realistic, disk model [12] . I. INTRODUCTION We also compare the results established here with wellknown zero-one laws for ER graphs [5] . In particular, we show that the connectivity behavior of the model studied here does not in general resemble that of the ER graphs. The picture is somewhat more subtle for the results also imply that if the channel is very poor, the model studied here indeed behaves like an ER graph as far as connectivity is concerned. The comparison with ER graphs is particularly relevant to the analysis of key distribution schemes for WSNs: Indeed, connectivity results for ER graphs have often been used in the dimensioning and evaluation of key distribution schemes, e.g., see the papers by Eschenauer and Gligor [11] , Chan et al. [7] and Hwang and Kim [13] . There it is a common practice to assume that the random graph induced by the particular key distribution scheme behaves like an ER graph (although it is not strictly speaking an ER graph). As pointed out by Di Pietro et al. [8] such an assumption is made without any formal justification, and subsequent efforts to confirm its validity have remained limited to this date: The EG scheme has been analyzed by a number of authors [3] , [8] , [18] , [24] , and as a result of these efforts it is now known that the ER assumption does yield the correct results for both the absence of isolated nodes and connectivity under the assumption of full visibility. On the other hand the recent paper [25] shows that the ER assumption is not valid for the pairwise key distribution of Chan et al. [7] ; see Section V-A for details. I. INTRODUCTION The rest of the paper is organized as follows: In Section II, we give precise definitions and implementation details of the pairwise scheme of Chan et al. while Section III is devoted to describing the model of interest. The main results of the paper, namely Theorem 4.1 and Theorem 4.2, are presented in Section IV with an extensive discussion given in Section V. The remaining sections, namely Sections VI through XIII, are devoted to establishing the main results of the paper. I. INTRODUCTION A word on notation and conventions in use: All limiting statements, including asymptotic equivalences, are understood with n going to infinity. The random variables (rvs) under consideration are all defined on the same probability triple (Ω, F , P). Probabilistic statements are made with respect to this probability measure P, and we denote the corresponding expectation operator by E. Also, we use the notation = st to indicate distributional equality. The indicator function of an event E is denoted by 1 [E]. For any discrete set S we write |S| for its cardinality. Also, for any pair of events E and F we have II. IMPLEMENTING PAIRWISE KEY DISTRIBUTION SCHEMES Interest in the random pairwise key predistribution scheme of Chan et al. [7] stems from the following advantages over the EG scheme: (i) Even if some nodes are captured, the secrecy of the remaining nodes is perfectly preserved; (ii) Unlike earlier schemes, this pairwise scheme enables both node-to-node authentication and quorum-based revocation. SCHEMES As in the conference papers [25] , [26] , we parametrize the pairwise key distribution scheme by two positive integers n and K such that K < n. There are n nodes, labelled i = 1, . . . , n, with unique ids Id 1 , . . . , Id n . Write N := {1, . . . n} and set N −i := N − {i} for each i = 1, . . . , n. With node i we associate a subset Γ n,i of nodes selected at random from N −i -We say that each of the nodes in Γ n,i is paired to node i. Thus, for any subset A ⊆ N −i , we require SCHEMES The selection of Γ n,i is done uniformly amongst all subsets of N −i which are of size exactly K. The rvs Γ n,1 , . . . , Γ n,n are assumed to be mutually independent so that SCHEMES for arbitrary A 1 , . . . , A n subsets of N −1 , . . . , N −n , respectively. Once this offline random pairing has been created, we construct the key rings Σ n,1 , . . . , Σ n,n , one for each node, as follows: Assumed available is a collection of nK distinct cryptographic keys {ω i|ℓ , i = 1, . . . , n; ℓ = 1, . . . , K}. Fix i = 1, . . . , n and let ℓ n,i : Γ n,i → {1, . . . , K} denote a labeling of Γ n,i . For each node j in Γ n,i paired to i, the cryptographic key ω i|ℓn,i(j) is associated with j. For instance, if the random set Γ n,i is realized as {j 1 , . . . , j K } with 1 ≤ j 1 < . . . < j K ≤ n, then an obvious labeling consists in ℓ n,i (j k ) = k for each k = 1, . . . , K with key ω i|k associated with node j k . Of course other labeling are possible, e.g., according to decreasing labels or according to a random permutation. Finally, the pairwise key ω ⋆ n,ji . Finally, it is plain by construction that this scheme supports node-to-node authentication. III. THE MODEL Under full visibility, this pairwise distribution scheme naturally gives rise to the following class of random graphs: With n = 2, 3, . . . and positive integer K < n, we say that the distinct nodes i and j are K-adjacent, written i ∼ K j, if and only if they have at least one key in common in their key rings, namely III. THE MODEL Let H(n; K) denote the undirected random graph on the vertex set {1, . . . , n} induced by the adjacency notion (3); this corresponds to modelling the pairwise distribution scheme under full visibility. We have III. THE MODEL where λ n (K) is the link assignment probability in H(n; K) given by III. THE MODEL As mentioned earlier, in this paper we seek to account for the possibility that communication links between nodes may not be available. To study such situations, we assume a communication model that consists of independent channels each of which can be either on or off. Thus, with p in (0, 1), let {B ij (p), 1 ≤ i < j ≤ n} denote i.i.d. {0, 1}-valued rvs with success probability p. The channel between nodes i and j is available (resp. up) with probability p and unavailable (resp. down) with the complementary probability 1 − p. III. THE MODEL Distinct nodes i and j are said to be B-adjacent, written i ∼ B j, if B ij (p) = 1. The notion of B-adjacency defines the standard ER graph G(n; p) on the vertex set {1, . . . , n}. Obviously, III. THE MODEL The random graph model studied here is obtained by intersecting the random pairwise graph H(n; K) with the ER graph G(n; p). More precisely, the distinct nodes i and j are said to be adjacent, written i ∼ j, if and only they are both K-adjacent and B-adjacent, namely III. THE MODEL The resulting undirected random graph defined on the vertex set {1, . . . , n} through this notion of adjacency is denoted H ∩ G(n; K, p). III. THE MODEL Throughout the collections of rvs {Γ n,1 , . . . , Γ n,n } and {B ij (p), 1 ≤ i < j ≤ n} are assumed to be independent, in which case the edge occurrence probability in H ∩ G(n; K, p) is given by III. THE MODEL IV. THE RESULTS III. THE MODEL To fix the terminology, we refer to any mapping K : N 0 → N 0 as a scaling (for random pairwise graphs) provided it satisfies the natural conditions III. THE MODEL Similarly, any mapping p : N 0 → (0, 1) defines a scaling for ER graphs. III. THE MODEL To lighten the notation we often group the parameters K and p into the ordered pair θ ≡ (K, p). Hence, a mapping θ : N 0 → N 0 × (0, 1) defines a scaling for the intersection graph H ∩ G(n; θ) provided the condition (8) holds on the first component. III. THE MODEL The results will be expressed in terms of the threshold function τ : III. THE MODEL It is easy to check that this threshold function is continuous on its entire domain of definition; see Figure 3 . A. Absence of isolated nodes The first result gives a zero-one law for the absence of isolated nodes. A. Absence of isolated nodes Theorem 4.1: Consider scalings K : N 0 → N 0 and p : A. Absence of isolated nodes for some c > 0. If A. Absence of isolated nodes The condition (10) on the scaling N 0 → (0, 1) × N 0 will often be used in the equivalent form A. Absence of isolated nodes with the sequence c : N 0 → R + satisfying lim n→∞ c n = c. B. Connectivity An analog of Theorem 4.1 also holds for the property of graph connectivity. B. Connectivity where the threshold τ (p ⋆ ) is given by (9) . Comparing Theorem 4.2 with Theorem 4.1, we see that the class of random graphs studied here provides one more instance where the zero-one laws for absence of isolated nodes and connectivity coincide, viz. ER graphs [5] , random geometric graphs [19] or random key graphs [3] , [18] , [24] . B. Connectivity A case of particular interest arises when p ⋆ > 0 since requiring (10) now amounts to B. Connectivity for some c > 0. Any scaling K : N 0 → N 0 which behaves like (14) must necessarily satisfy K n = o(n), and it is easy to see that requiring (10) is equivalent to B. Connectivity for some t > 0 with c and t related by t = c 2p ⋆ . With this reparametrization, Theorem 4.1 and Theorem 4.2 can be summarized in the following simpler form: B. Connectivity Under the condition (15) for some t > 0, we have B. Connectivity where we have set B. Connectivity This alternate formulation is particularly relevant for the case p n = p ⋆ (in (0, 1)) for all n = 1, 2, . . ., which captures situations when channel conditions are not affected by the number of users. Such simplifications do not occur in the more realistic case p ⋆ = 0 which corresponds to the situation where channel conditions are indeed influenced by the number of users in the system -The more users in the network, the more likely they will experience interferences from other users. B. Connectivity We now present numerical results that verify (16) . In all the simulations, we fix the number of nodes at n = 200. We consider the channel parameters p = 0.2, p = 0.4, p = 0.6, p = 0.8, and p = 1 (the full visibility case), while varying the parameter K from 1 to 25. For each parameter pair (K, p), we generate 500 independent samples of the graph H ∩ G(n; K, p) and count the number of times (out of a possible 500) that the obtained graphs i) have no isolated nodes and ii) are connected. Dividing the counts by 500, we obtain the (empirical) probabilities for the events of interest. The results for connectivity are depicted in Figure 1 , where the curve fitting tool of MATLAB is used. It is easy to check that for each value of p = 1, the connectivity threshold matches the prescription (16), namely K = τ (p) log n. It is also seen that, if the channel is poor, i.e., if p is close to zero, then the required value for K to ensure connectivity can be much larger than the one in the full visibility case p = 1. The results regarding the absence of node isolation are depicted in Figure 2 . For each value of p = 1, Figure 2 is indistinguishable from Figure 1 , with the difference between the estimated probabilities of graph connectivity and absence of isolated nodes being quite small, in agreement with (16). V. DISCUSSION AND COMMENTS A. Comparing with the full-visibility case At this point the reader may wonder as to what form would Theorem 4.2 take in the context of full visibility-In the setting developed here this corresponds to p = 1 so that H ∩ G(n; θ) coincides with H(n; K); see the curve for p = 1 in Figure 1 ). Relevant results for this case were obtained recently by the authors in [25] . Theorem 5.1: For any K a positive integer, it holds that A. Comparing with the full-visibility case The case where the parameter K is scaled with n is an easy corollary of Theorem 5.1. A. Comparing with the full-visibility case Corollary 5.2: For any scaling K : N 0 → N 0 such that K n ≥ 2 for all n sufficiently large, we have the one-law A. Comparing with the full-visibility case Each node in H(n; K) has degree at least K, so that no node is ever isolated in H(n; K). This is in sharp contrast with the model studied here, as reflected by the full zero-one law for node isolation given in Theorem 4.1. A. Comparing with the full-visibility case Theorem 5.1 and its Corollary 5.2 together show that very small values of K suffice to ensure asymptotically almost sure (a.a.s.) connectivity of the random graph H(n; K). However, these two results cannot be recovered from Theorem 4.2 whose zero-one laws are derived under the assumption p n < 1 for all n = 1, 2, . . .. Furthermore, even if the scaling p : N 0 → (0, 1) were to satisfy lim n→∞ p n = 1, only the one-laws in Theorem 4.3 remain since τ (p ⋆ ) = 0 (and τ (p ⋆ ) = 0) at p ⋆ = 1. Although this might perhaps be expected given the aforementioned absence of isolated nodes in H(n; K), the one-laws for both the absence of isolated nodes and graph connectivity in H ∩ G(n; θ) still require conditions on the behavior of the scaling K : N 0 → N 0 , namely (15) (whereas Corollary 5.2 does not). B. Comparing H ∩ G(n; θ) with ER graphs In the original paper of Chan et al. [7] (as in the reference [13] ), the connectivity analysis of the pairwise scheme was based on ER graphs [5] -It was assumed that the random graph induced by the pairwise scheme under a communication model (taken mostly to be the disk model [12] ) behaves like an ER graph; similar assumptions have been made in [11] , [13] when discussing the connectivity of the EG scheme. However, this assumption was made without any formal justification. Recently we have shown that the full visibility model H(n; K) has major differences with an ER graph. For instance, the edge assignments are (negatively) correlated in H(n; K) while independent in ER graphs; see [25] for a detailed discussion on the differences of H(n; K) and G(n; p). It is easy to verify that the edge assignments in H ∩ G(n; θ) are also negatively correlated; see Section IX. Therefore, the models H(n; K) and H ∩ G(n; θ) cannot be equated with an ER graph, and the results obtained in [25] and in this paper are not mere consequences of classical results for ER graphs. B. Comparing H ∩ G(n; θ) with ER graphs However, formal similarities do exist between H ∩ G(n; θ) and ER graphs. Recall the following well-known zero-one law for ER graphs: For any scaling p : B. Comparing H ∩ G(n; θ) with ER graphs log n n for some c > 0, it holds that On the other hand, the condition (10) can be rephrased more compactly as B. Comparing H ∩ G(n; θ) with ER graphs with the results (11) and (13) unchanged. Hence, in both ER graphs and H ∩ G(n; θ), the zero-one laws can be expressed as a comparison of the probability of link assignment against the critical scaling log n n ; this is also the case for random geometric graphs [19] , and random key graphs [3] , [18] , [24] . But the condition c > τ (p ⋆ ) that ensures a.a.s. connectivity in H ∩ G(n; θ) is not the same as the condition c > 1 for a.a.s. connectivity in ER graphs; see Figure 3 . Thus, the connectivity behavior of the model H ∩ G(n; θ) is in general different from that in an ER graph, and a "transfer" of the connectivity results from ER graphs cannot be taken for granted. Yet, the comparison becomes intricate when the channel is poor: The connectivity behaviors of the two models do match in the practically relevant case (for WSNs) lim n→∞ p n = 0 since τ (0) = 1. C. A more realistic communication model One possible extension of the work presented here would be to consider a more realistic communication model; e.g., the popular disk model [12] which takes into account the geographical positions of the sensor nodes. For instance, assume that the nodes are distributed over a bounded region D of the plane. According to the disk model, nodes i and j located at x i and x j , respectively, in D are able to communicate if C. A more realistic communication model where ρ > 0 is called the transmission range. When the node locations are independently and randomly distributed over the region D, the graph induced under the condition (18) is known as a random geometric graph [19] , thereafter denoted G(n; ρ). Under the disk model, studying the pairwise scheme of Chan et al. amounts to analyzing the intersection of H(n; K) and G(n; ρ), say H ∩ G(n; K, ρ). A direct analysis of this model seems to be very challenging; see below for more on this. However, limited simulations already suggest that the zero-one laws obtained here for H ∩ G(n; K, p) have an analog for the model H ∩ G(n; K, ρ). To verify this, consider 200 nodes distributed uniformly and independently over a folded unit square [0, 1] 2 with toroidal (continuous) boundary conditions. Since there are no border effects, it is easy to check that C. A more realistic communication model whenever ρ < 0.5. We match the two communication models G(n; p) and G(n; ρ) by requiring πρ 2 = p. Then, we use the same procedure that produced Figure 1 to obtain the empirical probability that H ∩ G(n; K, ρ) is connected for various values of K and p. The results are depicted in Figure 4 whose resemblance with Figure 1 suggests that the connectivity behaviors of the models H ∩ G(n; K, p) and H ∩ G(n; K, ρ) are quite similar. This raises the possibility that the results obtained here for the on/off communication model can also be used for dimensioning the pairwise scheme under the disk model. C. A more realistic communication model A complete analysis of H ∩ G(n; K, ρ) is likely to be very challenging given the difficulties already encountered in the analysis of similar problems. For example, the intersection of random geometric graphs with ER graphs was considered in [2] , [28] . Although zero-one laws for graph connectivity are available for each component random graph, the results for the intersection model in [2] , [28] were limited only to the absence of isolated nodes; the connectivity problem is still open for that model. Yi et al. [28] also consider the intersection of random key graphs with random geometric graphs, but these results are again limited to the property of node isolation. To the best of our knowledge, Theorem 4.2 reported here constitutes the only zero-one law for graph connectivity in a model formed by intersecting multiple random graphs! (Except of course the trivial case where an ER graph intersects another ER graph.) D. Intersection of random graphs When using random graph models to study networks, situations arise where the notion of adjacency between nodes reflects multiple constraints. This can be so even when dealing with networks other than WSNs. As was the case here, such circumstances call for studying models which are constructed by taking the intersection of multiple random graphs. However, as pointed out earlier, the availability of results for each component model does not necessarily imply the availability of results for the intersection of these models; see the examples provided in the previous section. D. Intersection of random graphs Figures 5-7 can help better understand the relevant issues as to why this is so: Figure 5 provides a sample of an ER graph G(n, p) with n = 200 and p = 0.2. As would be expected from the classical results, the obtained graph is very densely connected. Similarly, Figure 6 provides a sample of the pairwise random graph H(n; K) with n = 200 and K = 5. In line with Theorem 5.1, the obtained graph is connected. On the other hand, the graph formed by intersecting these graphs turn out to be disconnected as shown in Figure 7 . Fig. 7 . The intersection H ∩ G(n; θ) of the graphs in Figure 5 and Figure 6 -The graph is disconnected as the marked nodes form a component! To drive this point further, consider the constant parameter case for the models H(n; K) and G(n; p), a case which cannot be recovered from either Theorem 4.1 or Theorem 4.2. Nevertheless, Theorem 5.1 yields D. Intersection of random graphs while it well known [5] that D. Intersection of random graphs However, it can be shown that D. Intersection of random graphs for the same ranges of values for p and K; for details see the discussion at the end of Section X. This clearly provides a non-trivial example (one that is not for an ER intersecting an ER graph) where the intersection of two random graphs is indeed a.a.s. not connected although each of the components is a.a.s. connected. VI. A PROOF OF THEOREM 4.1 We prove Theorem 4.1 by the method of first and second moments [14, p. 55] applied to the total number of isolated nodes in H ∩ G(n; θ). First some notation: Fix n = 2, 3, . . . and consider θ = (K, p) with p in (0, 1) and positive integer K such that K < n. With VI. A PROOF OF THEOREM 4.1 for each i = 1, . . . , n, the number of isolated nodes in H ∩ G(n; θ) is simply given by VI. A PROOF OF THEOREM 4.1 The random graph H ∩ G(n; θ) has no isolated nodes if and only if I n (θ) = 0. VI. A PROOF OF THEOREM 4.1 The method of first moment [14, Eqn (3.10), p. 55] relies on the well-known bound VI. A PROOF OF THEOREM 4.1 while the method of second moment [14, Remark 3.1, p. 55] has its starting point in the inequality VI. A PROOF OF THEOREM 4.1 The rvs χ n,1 (θ), . . . , χ n,n (θ) being exchangeable, we find VI. A PROOF OF THEOREM 4.1 and VI. A PROOF OF THEOREM 4.1 by the binary nature of the rvs involved. It then follows that VI. A PROOF OF THEOREM 4.1 From (21) and (23) we see that the one-law lim n→∞ P [I n (θ n ) = 0] = 1 will be established if we show that lim VI. A PROOF OF THEOREM 4.1 It is also plain from (22) and (24) that the zero-law VI. A PROOF OF THEOREM 4.1 and VI. A PROOF OF THEOREM 4.1 The proof of Theorem 4.1 passes through the next two technical propositions which establish (25) , (26) and (27) under the appropriate conditions on the scaling θ : N 0 → N 0 ×(0, 1). VI. A PROOF OF THEOREM 4.1 Proposition 6.1: Consider scalings K : N 0 → N 0 and p : N 0 → (0, 1) such that (10) holds for some c > 0. Assume also that lim n→∞ p n = p ⋆ exists. Then, we have VI. A PROOF OF THEOREM 4.1 where the threshold τ (p ⋆ ) is given by (9) . A proof of Proposition 6.1 is given in Section VIII. VI. A PROOF OF THEOREM 4.1 Proposition 6.2: Consider scalings K : N 0 → N 0 and p : N 0 → (0, 1) such that (10) holds for some c > 0. Assume also that lim n→∞ p n = p ⋆ exists. Then, we have (27) whenever p ⋆ < 1. VI. A PROOF OF THEOREM 4.1 A proof of Proposition 6.2 can be found in Section X. To complete the proof of Theorem 4.1, pick a scaling θ : N 0 → N 0 × (0, 1) such that (10) holds for some c > 0 and lim n→∞ p n = p ⋆ exists. Under the condition c > τ (p ⋆ ) we get (25) from Proposition 6.1, and the onelaw lim n→∞ P [I n (θ n ) = 0] = 1 follows. Next, assume that c < τ (p ⋆ ) -This case is possible only if p ⋆ < 1 since τ (1) = 0 as seen at (9) . When p ⋆ < 1, we obtain (26) and (27) with the help of Propositions 6.1 and 6.2, respectively. The conclusion lim n→∞ P [I n (θ n ) = 0] = 0 is now immediate. VII. A PREPARATORY RESULT Fix n = 2, 3, . . . and consider θ = (K, p) with p in (0, 1) and positive integer K such that K < n. Under the enforced assumptions, for all i = 1, . . . , n, we easily see that VII. A PREPARATORY RESULT where D n,i denotes the degree of node i in H(n; K). Note that VII. A PREPARATORY RESULT By independence, since VII. A PREPARATORY RESULT the second term in (30) is a binomial rv with n − K − 1 trials and success probability given by VII. A PREPARATORY RESULT whence VII. A PREPARATORY RESULT The proof of Proposition 6.1 uses a somewhat simpler form of the expression (32) which we develop next. VII. A PREPARATORY RESULT Lemma 7.1: Consider scalings K : N 0 → N 0 and p : N 0 → (0, 1) such that (10) holds for some c > 0. It holds that VII. A PREPARATORY RESULT with VII. A PREPARATORY RESULT where the sequence c : N 0 → R is the one appearing in the form (12) of the condition (10) . VII. A PREPARATORY RESULT In what follows we make use of the decomposition VII. A PREPARATORY RESULT with VII. A PREPARATORY RESULT on that range. Note that VII. A PREPARATORY RESULT Proof. Consider a scaling θ : N 0 → N 0 × (0, 1) such that (10) holds for some c > 0 and assume the existence of the limit lim n→∞ p n = p ⋆ . Replacing θ by θ n in (32) for each n = 2, 3, . . . we get nE [χ n,1 (θ n )] = e βn (36) with β n given by VII. A PREPARATORY RESULT The decomposition (35) now yields VII. A PREPARATORY RESULT where the last step used the form (12) of the condition (10) on the scaling. Reporting this calculation into the expression for β n we find VII. A PREPARATORY RESULT Lemma 7.1 will be established if we show that VII. A PREPARATORY RESULT To that end, for each n = 2, 3, . . . we note that VII. A PREPARATORY RESULT and it is now plain that VII. A PREPARATORY RESULT Invoking the behavior of Ψ(x) at x = 0 mentioned earlier, we conclude from these facts that VII. A PREPARATORY RESULT This establishes (37) and the proof of Lemma 7.1 is completed. VIII. A PROOF OF PROPOSITION 6.1 In view of Lemma 7.1, Proposition 6.1 will be established if we show VIII. A PROOF OF PROPOSITION 6.1 To see this, first note from (35) that for each n = 1, 2, . . ., we have p n + log(1 − p n ) ≤ 0 and the lower bound in (38) implies VIII. A PROOF OF PROPOSITION 6.1 Letting n go to infinity in this last expression, we get lim n→∞ α n = −∞ whenever c > lim VIII. A PROOF OF PROPOSITION 6.1 since lim n→∞ c n = c. Next, we show that if c < τ (p ⋆ ), then lim n→∞ α n = +∞. We only need to consider the case 0 ≤ p ⋆ < 1 since τ (1) = 0 and the constraint c < τ (1) is vacuous. We begin by assuming p ⋆ = 0, in which case for each n = 2, 3, . . ., we have VIII. A PROOF OF PROPOSITION 6.1 with the inequality following from the upper bound in (38). Let n grow large in the last expression. Since we have assumed lim n→∞ p n = 0, we get VIII. A PROOF OF PROPOSITION 6.1 and the desired conclusion lim n→∞ α n = +∞ is obtained whenever c < 1 = τ (0) upon using lim n→∞ c n = c. Finally we assume 0 < p ⋆ < 1. For each ε > 0, there exists a finite positive integer n VIII. A PROOF OF PROPOSITION 6.1 On that range the upper bound in (38) yields VIII. A PROOF OF PROPOSITION 6.1 follow. Comparing this last fact against the lefthand side of (12) yields VIII. A PROOF OF PROPOSITION 6.1 From (34) it follows that VIII. A PROOF OF PROPOSITION 6.1 for all n sufficiently large. Letting n go to infinity in this last expression and using (44) with the earlier remarks, we readily conclude VIII. A PROOF OF PROPOSITION 6.1 where the last step follows by direct inspection. It is now clear that lim n→∞ α n = ∞ when c < τ (p ⋆ ) with 0 < p ⋆ < 1. The proof of Proposition 6.1 is now completed. IX. NEGATIVE DEPENDENCE AND CONSEQUENCES Fix positive integers n = 2, 3, . . . and K with K < n. Several properties of the {0, 1}-valued rvs IX. NEGATIVE DEPENDENCE AND CONSEQUENCES and IX. NEGATIVE DEPENDENCE AND CONSEQUENCES will play a key role in some of the forthcoming arguments. A. Negative association The properties of interest can be couched in terms of negative association, a form of negative correlation introduced to Joag-Dev and Proschan [15] . We first develop the needed definitions and properties: Let {X λ , λ ∈ Λ} be a collection of R-valued rvs indexed by the finite set Λ. For any nonempty subset A of Λ, we write X A to denote the R |A| -valued X A = (X λ , λ ∈ A). The rvs {X λ , λ ∈ Λ} are then said to be negatively associated if for any non-overlapping subsets A and B of Λ and for any monotone increasing mappings ϕ : R |A| → R and ψ : R |B| → R, the covariance inequality A. Negative association holds whenever the expectations in (47) are well defined and finite. Note that ϕ and ψ need only be monotone increasing on the support of X A and X B , respectively. This definition has some easy consequences to be used repeatedly in what follows: The negative association of {X λ , λ ∈ Λ} implies the negative association of the collection {X λ , λ ∈ Λ ′ } where Λ ′ is any subset of Λ. It is also well known [15, P2, p. 288 ] that the negative association of the rvs {X λ , λ ∈ Λ} implies the inequality A. Negative association where A is a subset of Λ and the collection {f λ , λ ∈ A} of mappings R → R + are all monotone increasing; by nonnegativity all the expectations exist and finiteness is moot. We can apply these ideas to collections of indicator rvs, namely for each λ in Λ, X λ = 1 [E λ ] for some event E λ . From the definitions, it is easy to see that if the rvs {1 [E λ ] , λ ∈ Λ} are negatively associated, so are the rvs {1 [E c λ ] , λ ∈ Λ}. Moreover, for any subset A of Λ, we have A. Negative association This follows from (48) by taking f λ (x) = x + on R for each λ in Λ. B. Useful consequences A key observation for our purpose is as follows: For each i = 1, . . . , n, the rvs B. Useful consequences form a collection of negatively associated rvs. This is a consequence of the fact that the random set Γ n,i represents a random sample (without replacement) of size K from N −i ; see [15, Example 3.2(c)] for details. The n collections (50) are mutually independent, so that by the "closure under products" property of negative association [15, P7, p . 288] [10, p. 35], the rvs (45) also form a collection of negatively associated rvs. B. Useful consequences Hence, by taking complements, the rvs B. Useful consequences also form a collection of negatively associated rvs. With distinct i, j = 1, . . . , n, we note that B. Useful consequences with mapping f : R 2 → R given by f (x, y) = x + y + for all x, y in R. This mapping being non-decreasing on R 2 , it follows [15, P6, p. 288 ] that the rvs B. Useful consequences are also negatively associated. Taking complements one more time, we see that the rvs (46) are also negatively associated. For each k = 1, 2 and j = 3, . . . , n, we shall find it useful to define u n,j,k (θ) := E (1 − p) B. Useful consequences Under the enforced assumptions, we have B. Useful consequences Before computing either one of the quantities u n (θ) and b n (θ), we note that B. Useful consequences This is a straightforward consequence of the negative association of the rvs (45) -In (47), with A and B singletons, use the increasing functions ϕ, ψ : R → R : B. Useful consequences An expression for b n (θ) is available but will not be needed due to the availability of (54). B. Useful consequences X. A PROOF OF PROPOSITION 6.2 As expected, the first step in proving Proposition 6.2 consists in evaluating the cross moment appearing in the numerator of (27) . Fix n = 2, 3, . . . and consider θ = (K, p) with p in (0, 1) and positive integer K such that K < n. Define the N 0 -valued rvs B n (θ) and U n (θ) by B. Useful consequences and B. Useful consequences Proposition 10.1: Fix n = 2, 3, . . .. For any p in (0, 1) and positive integer K such that K < n, we have B. Useful consequences where the rvs B n (θ) and U n (θ) given by (56) and (57), respectively. B. Useful consequences A proof of Proposition 10.1 is available in Appendix A. Still in the setting of Proposition 10.1, we can use (54) in conjunction with (58) to get B. Useful consequences It is plain that B. Useful consequences We note that B. Useful consequences by similar arguments. The expression B. Useful consequences now follows, and we find B. Useful consequences Next, with the help of (32) and (55) we conclude that B. Useful consequences Direct inspection readily yields B. Useful consequences Taking expectation and reporting into (62) we then find B. Useful consequences by a crude bounding argument. Now consider a scaling θ : N 0 → N 0 × (0, 1) such that (10) holds for some c > 0 and lim n→∞ p n = p ⋆ < 1. Replace θ by θ n in the bound (65) with respect to this scaling. It is immediate that (27) will be established if we show that B. Useful consequences These limits are an easy consequence of the inequalities (38) by virtue of the fact that lim n→∞ p n = p ⋆ < 1. B. Useful consequences We close with a proof of (19): Consider θ = (K, p) with p in (0, 1) and positive integer K. It follows from (32) that B. Useful consequences The arguments outlined in Section VI now yield B. Useful consequences and this establishes (19) . The conclusion (20) immediately follows; see discussion at (66). XI. A PROOF OF THEOREM 4.2 (PART I) Fix n = 2, 3, . . . and consider θ = (K, p) with p in (0, 1) and positive integer K such that K < n. We define the events XI. A PROOF OF THEOREM 4.2 (PART I) and I(n; θ) := [H ∩ G(n; θ) contains no isolated nodes] . XI. A PROOF OF THEOREM 4.2 (PART I) If the random graph H ∩ G(n; θ) is connected, then it does not contain any isolated node, whence C n (θ) is a subset of I(n; θ), and the conclusions XI. A PROOF OF THEOREM 4.2 (PART I) and XI. A PROOF OF THEOREM 4.2 (PART I) obtain. Taken together with Theorem 4.1, the relations (66) and (67) pave the way to proving Theorem 4.2. Indeed, pick a scaling θ : N 0 → N 0 × (0, 1) such that (10) holds for some c > 0 and lim n→∞ p n = p ⋆ exists. If c < τ (p ⋆ ), then lim n→∞ P [I(n; θ n )] = 0 by the zero-law for the absence of isolated nodes, whence lim n→∞ P [C n (θ n )] = 0 with the help of (66). If c > τ (p ⋆ ), then lim n→∞ P [I(n; θ n )] = 1 by the one-law for the absence of isolated nodes, and the desired conclusion lim n→∞ P [C n (θ n )] = 1 (or equivalently, XI. A PROOF OF THEOREM 4.2 (PART I) c ] = 0) will follow via (67) if we show the following: XI. A PROOF OF THEOREM 4.2 (PART I) Proposition 11.1: For any scaling θ : N 0 → N 0 ×(0, 1) such that lim n→∞ p n = p ⋆ exists and (10) holds for some c > τ (p ⋆ ), we have lim XI. A PROOF OF THEOREM 4.2 (PART I) The proof of Proposition 11.1 starts below and runs through two more sections, namely Sections XII and XIII. The basic idea is to find a sufficiently tight upper bound on the probability in (68) and then to show that this bound goes to zero as n becomes large. This approach is similar to the one used for proving the one-law for connectivity in ER graphs [5, p. 164] . XI. A PROOF OF THEOREM 4.2 (PART I) We begin by finding the needed upper bound: Fix n = 2, 3, . . . and consider θ = (K, p) with p in (0, 1) and positive integer K such that K < n. For any non-empty subset S of nodes, i.e., S ⊆ {1, . . . , n}, we define the graph H ∩ G(n; θ)(S) (with vertex set S) as the subgraph of H ∩ G(n; θ) restricted to the nodes in S. We also say that S is isolated in H ∩ G(n; θ) if there are no edges (in H ∩ G(n; θ)) between the nodes in S and the nodes in the complement S c = {1, . . . , n} − S. This is characterized by XI. A PROOF OF THEOREM 4.2 (PART I) With each non-empty subset S of nodes, we associate several events of interest: Let C n (θ; S) denote the event that the subgraph H ∩ G(n; θ)(S) is itself connected. The event C n (θ; S) is completely determined by the rvs {K i (θ), i ∈ S}. We also introduce the event B n (θ; S) to capture the fact that S is isolated in H ∩ G(n; θ), i.e., XI. A PROOF OF THEOREM 4.2 (PART I) Finally, we set XI. A PROOF OF THEOREM 4.2 (PART I) The starting point of the discussion is the following basic observation: If H ∩ G(n; θ) is not connected and yet has no isolated nodes, then there must exist a subset S of nodes with |S| ≥ 2 such that H ∩ G(n; θ)(S) is connected while S is isolated in H ∩ G(n; θ). This is captured by the inclusion XI. A PROOF OF THEOREM 4.2 (PART I) A moment of reflection should convince the reader that this union need only be taken over all subsets S of {1, . . . , n} with 2 ≤ |S| ≤ ⌊ n 2 ⌋. A standard union bound argument immediately gives XI. A PROOF OF THEOREM 4.2 (PART I) where N n,r denotes the collection of all subsets of {1, . . . , n} with exactly r elements. For each r = 1, . . . , n, we simplify the notation by writing A n,r (θ) := A n (θ; {1, . . . , r}), B n,r (θ) := B n (θ; {1, . . . , r})
{'paper_id': '11497276', 'title': 'Modeling the pairwise key distribution scheme in the presence of unreliable links', 's2_url': 'https://api.semanticscholar.org/CorpusID:11497276', 'source': 'S2ORC'}