## 5 Application of de Finetti Style Theorems in Random Network Analysis
Below we show an approach that is grounded in [PERSON] style theorems, and provides a tool that can come in handy in the analysis of conditional random graph models. **Theorem 12**: _Let \(S\) be a Borel measurable space, and let \(\mathcal{P}\) be a property of random graph models. Fix an i.i.d.-based random graph model \(\mathbf{G}\) over \(S\), and assume that \(\mathbf{G}(X)\) has property \(\mathcal{P}\), regardless of the value of \(X\), with probability 1. Let \(C\) represent a condition with \(\Pr(X\subseteq C)>0\). Then \(\mathbf{G}(X\,|\,C)\) also has property \(\mathcal{P}\), regardless of the value of \(X\), with probability 1._  
Let \(Y\) be a random variable that has the conditional distribution of \(X\), given \(C\). That is, for every measurable set \(A\)  
\[\Pr(Y\subseteq A)=\Pr(X\subseteq A\,\mid\,X\subseteq C).\]Note that \(Y\) may not remain i.i.d. However, we show that \(Y\) is still exchangeable. Let \(\sigma\) be any permutation. Then we can write  
\[\Pr(\sigma(Y)\subseteq A)=\Pr(\sigma(X)\subseteq A\mid\sigma(X)\subseteq C)= \frac{\Pr(\sigma(X)\subseteq A\cap C)}{\Pr(\sigma(X)\subseteq C)}. \tag{14}\]  
Since \(X\) is i.i.d., therefore, \(X=_{d}\sigma(X)\), i.e., they have the same distribution, making them statistically indistinguishable. This implies that for any measurable set \(B\) the equality \(\Pr(\sigma(X)\subseteq B)=\Pr(X\subseteq B)\) holds. Using it in (14), we get that  
\[\Pr(\sigma(Y)\subseteq A)=\frac{\Pr(\sigma(X)\subseteq A\cap C)}{\Pr(\sigma( X)\subseteq C)}=\frac{\Pr(X\subseteq A\cap C)}{\Pr(X\subseteq C)}=\Pr(Y \subseteq A)\]  
for any permutation \(\sigma\), which means that \(Y\) is exchangeable. Here we also used that \(\Pr(X\subseteq C)>0\), so the denominator does not become 0. Recall now that by the Hewitt-Savage Theorem, an infinite sequence \(Y\) of \(S\)-valued exchangeable random variables is an \(S\)-valued i.i.d.-mix, whenever \(S\) is a Borel measurable space. For each component \(X\) of this i.i.d. mix we can take the function \(\mathbf{G}\) to obtain a random graph model \(\mathbf{G}(X)\). After taking the mixture, this results in \(\mathbf{G}(Y)\). The reason is that applying the function to each sequence \(X\) first and then selecting one of them must yield the same result as first selecting one of them (by the same mixing measure), and applying the function to the selected sequence \(Y\). As a result of the above reasoning, we get \(\mathbf{G}(X)=_{d}\mathbf{G}(Y)\), i.e., the two random graph models have the same distribution. However, \(Y\) was chosen such that it has the conditional distribution of \(X\), given \(C\). Therefore, we have \(\mathbf{G}(Y)=_{d}\mathbf{G}(X\!\mid\!C)\). Thus, we obtain \(\mathbf{G}(X\!\mid\!C)=_{d}\mathbf{G}(X)\). Since, by assumption, \(\mathbf{G}(X)\) has property \(\mathcal{P}\), regardless of the value of \(X\), with probability 1, therefore, \(\mathbf{G}(X\!\mid\!C)\) also has property \(\mathcal{P}\), regardless of the value of \(X\), with probability 1. The reason for we need that \(\mathcal{P}\) does not depend on \(X\) (with probability 1) is that when we mix various realizations of \(X\), they should all come with the same property \(\mathcal{P}\), otherwise, a mixture of properties would result. This completes the proof. The above result may sound very abstract, so let us illustrate it with two examples. **Example 4**. : _It follows from the results of [PERSON] [22] that every i.i.d.-based geometric random graph has the following property:_  
_If the graph is asymptotically connected (that is, the probability of being connected approaches 1 as the number of nodes tends to infinity), then the average degree must tend to infinity._  
Let us choose this as property \(\mathcal{P}\). One may ask: does this property remain valid in conditional models over the same geometric domain? We may want to know this in more sophisticated models, such as the one presented in Example 3.