# Multiset-Trie Data Structure
## 4 Mathematical Analysis of the Structure
### Time Complexity of the Algorithms
#### 4.1.1 Mathematical Model
Recall that for any given discrete random variable \(X\) taking values over positive non-negative integral values, one can define a so-called _probability generating function_ (PGF, for short) \(G_{X}\) to be a formal power series defined as  
\[G_{X}(z)=\sum_{i\geq 0}Pr(X=i)z^{i}.\]  
While the PGFs are usually not meant to be evaluated for concrete values of \(z\), certain values have special interpretation when used in PGF, or in a derivation(s) of PGF. For instance, \(Pr(X=0)=G_{X}(0)\), and also \(\mathbb{E}(X)=G_{X}^{\prime}(1)\). For many values of \(z\), the function \(G_{X}\) may not converge to any finite value. For this reason, it is a common notation to write, in particular,  
\[G_{X}(1^{-})=\lim_{z\
earrow 1}G_{X}(z).\]In what follows, we will denote a Bernoulli-distributed random variable with parameter \(p\) as \(Bernoulli(p)\). Furthermore, we denote a zero-truncated binomially distributed random variable on parameters \(n\) and \(p_{i+1}\) by \(\mathcal{B}_{0}(n,p_{i+1})\). Finally, \(\overset{d}{=}\) indicates so-called equality in distribution. **Example 1**. : _The probability generating function of a binomial random variable \(\mathcal{B}(n,p)\), the number of successes in \(n\) trials, with probability \(p\) of success in each trial, is_  
\[ \begin{split} G_{\mathcal{B}(n,p)}(z)=G(z)&=\sum_{ k=0}^{n}\binom{n}{k}p^{k}(1-p)^{n-k}z^{k}\\ &=\sum_{k=0}^{n}\binom{n}{k}(pz)^{k}(1-p)^{n-k}\\ &=((1-p)+pz)^{n}.\end{split} \]  
_It is thus easy to compute expectation_  
\[\mathbb{E}(\mathcal{B}(n,p))=G^{\prime}(1)=np.\]  
We now focus our attention on the distribution of \(\xi_{ij}\). **Lemma 2**. : _Suppose that a node \(v\) exists at level \(1\leq i\leq\sigma\). Then, the number of its children \(\xi_{iv}\) is modeled by a zero-truncated binomially distributed random variable on parameters \(n\) and \(p_{i+1}\). In particular, the probability of node \(v\) having \(k\) children equals_  
\[P(\xi_{iv}=k)=\frac{\binom{n}{k}(1-p_{i+1})^{n-k}}{1-(1-p_{i+1})^{n}} \tag{3}\]  
_and the corresponding probability generating function equals_  
\[\mathcal{B}_{0}(n,p_{i+1})\overset{d}{=}G_{i}(z)=\frac{(1+p_{i+1}(z-1))^{n}-( 1-p_{i+1})^{n}}{1-(1-p_{i+1})^{n}}. \tag{4}\]  
Proof. : In order to prove the lemma, we have to show that \(\xi_{iv}\overset{d}{=}\mathcal{B}_{0}(n,p_{i+1})\). Consider an arbitrary node \(v\) on level \(1\leq i\leq\sigma\). According to the definition of the multiset-trie, a node exists at level \(i\) if and only if it has at least one child. Note that this is not true for the nodes on the leaf level \(\sigma+1\). This implies that a node on level \(i\) can have \(k\in\{1,2,\ldots,n\}\) children. Let \(X_{0},X_{1},\ldots,X_{n-1}\) be random variables; they are defined as follows:  
\[X_{k}= \begin{cases}0&\text{child $k$ of node $v$ does not exist}\\ 1&\text{child $k$ of node $v$ exists}\end{cases} \]  
As was shown in the previous Lemma 2, the distribution of \(X_{k}\) is \(X_{k}\overset{d}{=}Bernoulli(p_{i+1})\). Since our model assumes that all the multisets in \(M\) are chosen uniformly at random, the variables \(X_{k},X_{l}\) are independent for \(k\
eq l\). However, in our case, the node \(v\) cannot have \(0\) children, so the sum \(\sum_{k=1}^{n}X_{k}\) has a zero-truncated binomial distribution,  
\[\sum_{k=1}^{n}X_{k}\overset{d}{=}\mathcal{B}_{0}(n,p_{i+1}),\]  
which completes the proof. Knowing the probability density and probability generating functions of \(\xi_{ij}\) from Lemma 2, we can now estimate the number of nodes in a randomly generated multiset-trie as follows:  
\[\mathbb{E}(|\mathcal{M}|)=\mathbb{E}\left[\sum_{i=1}^{\sigma+1}\xi_{i}\right]. \tag{5}\]  
In order to evaluate (5), we will use some of the tools from a Galton-Watson process; see [PERSON] [26] for an introduction. Using Equations (1) and (4), we can derive the probability generating function for the random variable \(\xi_{i+1}\) as  
\[G_{\xi_{i+1}}(z)=G_{\xi_{i}}(G_{i}(z)). \tag{6}\]  
Since there is always precisely one node at the root level, we have \(P(\xi_{1}=1)=1\).