###### Abstract  
A classic and fundamental result about the decomposition of random sequences into a mixture of simpler ones is de Finetti's Theorem. In its original form, it applies to infinite 0-1 valued sequences with the special property that the distribution is invariant to permutations (called an exchangeable sequence). Later it was extended and generalized in numerous directions. After reviewing this line of development, we present our new decomposition theorem, covering cases that have not been previously considered. We also introduce a novel way of applying these types of results in the analysis of random networks. For self-containment, we provide the introductory exposition in more detail than usual, with the intent of making it also accessible to readers who may not be closely familiar with the subject. de Finetti's Theorem; exchangeable sequence; decomposition theorem; random network analysis +
Footnote †: journal: _Algorithms_  
for any permutation \(\sigma\) of \(\{1,\ldots,n\}\), the joint distribution of \((\xi_{\sigma(1)},\ldots,\xi_{\sigma(n)})\) is the same as the joint distribution of \((\xi_{1},\ldots,\xi_{n})\). An infinite sequence is called exchangeable if every finite initial segment of the sequence is exchangeable._  
It means, an exchangeable sequence is stochastically indistinguishable from any permutation of itself. An equivalent definition is that if we pick \(k\) entries of the sequence, then their joint distribution depends only on \(k\), but not on that which \(k\) entries are selected and in which order. This also implies (with \(k=1\)) that each individual entry has the same distribution. Sampling tasks often produce exchangeable sequences, since in most cases the order of the samples does not matter. As a special case, the definition is satisfied by i.i.d. random variables, but not every exchangeable sequence is i.i.d. There are many examples to demonstrate this; a simple one can be obtained from geometric considerations:  
**Example 1**. : _Take a square in the plane, and divide it into two triangles by one of its diagonals. Select one of the triangles at random with probability 1/2, and then pick \(n\) uniformly random points from the selected triangle. These random points constitute an exchangeable sequence, since their joint probability distribution remains the same, regardless of the order they have been produced. Furthermore, each individual point is uniformly distributed over the whole square, because it is uniformly distributed over a triangle, which is selected with equal probability from among the two triangles. On the other hand, the random points are not independent, since if we know that a point falls in the interior of a given one of the two triangles, all the others must fall in the same triangle._  
As we have argued before Definition 1, the mixing of i.i.d. sequences produces exchangeable sequences. A classical theorem of [PERSON], originally published in Italian [2] in 1931, says that the converse is also true for infinite binary sequences: every infinite exchangeable sequence of binary random variables can be represented as a mixture of i.i.d. Bernoulli random variables (for short, a Bernoulli i.i.d.-mix). The result can be formally stated in several different ways, here is a frequently used one, which captures the distribution of the exchangeable sequence as a mixture of binomial distributions:  
**Theorem 1** ([PERSON]'s Theorem--distributional form). : _Let \(X_{1},X_{2},\ldots\) be an infinite sequence of \(\{0,1\}\)-valued exchangeable random variables. Then there exists a probability measure \(\mu\) (called mixing measure) on \([0,1]\), such that for every positive integer \(n\) and for any \(x_{1},\ldots,x_{n}\in\{0,1\}\) the following holds:_  
\[\Pr(X_{1}=x_{1},\ldots,X_{n}=x_{n})=\int_{0}^{1}p^{s}(1-p)^{n-s}d\mu(p) \tag{1}\]  
_where \(s=\sum_{i=1}^{n}x_{i}\).