# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## Appendix A Missing Proofs  
In this appendix we present the proofs not included in the main text. Theorem 3: _Let \(S\) be a random sample of \(m\) transactions taken with replacement from the sequential dataset \(\mathcal{D}\) and \(\varepsilon,\delta\in(0,1)\). Let \(d\) be the \(s\)-bound of \(\mathcal{D}\). If_  
\[m\geq\frac{2}{\varepsilon^{2}}\left(d+\ln\frac{1}{\delta}\right)\,, \tag{1}\]_then \(\sup_{p\in\mathbb{U}}|f_{\mathcal{D}}(p)-f_{S}(p)|\leq\varepsilon/2\) with probability at least \(1-\delta\)._  
Proof. : From Theorem 1 in the main text we know that \(S\) is an \(\varepsilon/2\)-bag for \(\mathcal{D}\) with probability at least \(1-\delta\). This means that for all \(r\in\mathcal{R}\) we have  
\[\left|\frac{|\mathcal{D}\cap r|}{|\mathcal{D}|}-\frac{|S\cap r|}{|S|}\right| \leq\frac{\varepsilon}{2}. \tag{10}\]  
Given a sequence \(p\in\mathbb{U}\) and its support set \(T_{\mathcal{D}}(p)\) on \(\mathcal{D}\), that is the range \(r_{p}\), and from the definition of range set of a sequential dataset, we have  
\[\frac{|\mathcal{D}\cap r_{p}|}{|\mathcal{D}|}=f_{\mathcal{D}}(p) \tag{11}\]  
and  
\[\frac{|S\cap r_{p}|}{|S|}=f_{S}(p). \tag{12}\]  
Thus, \(\sup_{p\in\mathbb{U}}|f_{\mathcal{D}}(p)-f_{S}(p)|\leq\varepsilon/2\) with probability \(\geq 1-\delta\). Let \(\mathcal{D}\) be a finite bag of \(|\mathcal{D}|\) i.i.d. samples from an unknown probability distribution \(\pi\) on \(\mathbb{U}\) and \(\delta\in(0,1)\). Let \(d\) be the \(s\)-bound of \(\mathcal{D}\). If  
\[\mu_{\text{VC}}=\sqrt{\frac{2}{|\mathcal{D}|}\left(d+\ln\frac{1}{\delta}\right)}, \tag{13}\]  
then \(\sup_{p\in\mathbb{U}}|t_{\pi}(p)-f_{\mathcal{D}}(p)|\leq\mu_{\text{VC}}/2\) with probability at least \(1-\delta\). Proof. : The proof is analogous to the proof of Theorem 3, when we consider the dataset \(\mathcal{D}\) a random sample of a fixed size and we aim to compute an upper bound on the maximum deviation between the true frequency of a sequence and its frequency in \(\mathcal{D}\). Consider a subset \(W\) of the dataset \(\mathcal{D}\), \(W\subseteq\mathcal{D}\). Let \(CS_{W}(\mathcal{D})\) be the set of closed sequential patterns in \(\mathcal{D}\) whose support set in \(\mathcal{D}\) is \(W\), that is, \(CS_{W}(\mathcal{D})=\{p\in CS(\mathcal{D}):T_{\mathcal{D}}(p)=W\}\), with \(C=|CS_{W}(\mathcal{D})|\). Then the number \(C\) of closed sequential patterns in \(\mathcal{D}\) with \(W\) as support set satisfies: \(0\leq C\leq|CS(\mathcal{D})|\). Proof. : The proof is organized in such a way: first, we show that the basic cases \(C=0\) and \(C=1\) hold, second, we prove the cases for \(2\leq C\leq|CS(\mathcal{D})|\). Let us consider the case where \(W\) is a particular subset of \(\mathcal{D}\) for which no sequence has \(W\) as support set in \(\mathcal{D}\). Thus, \(CS_{W}(\mathcal{D})\) is an empty set and \(C=0\). The case \(C=1\) is trivial, since it could happen that only one closed sequential pattern has \(W\) as support set in \(\mathcal{D}\). Now, before proving the cases for a generic value of \(C\) in \([2,\ldots,|CS(\mathcal{D})|]\), we start by considering the case \(C=2\). Let \(p_{1}\),\(p_{2}\) be two sequences with \(W\) as support set. Assume that each super-sequence of \(p_{1}\) but not of \(p_{2}\) has support lower than the support of \(p_{1}\), and each super-sequence of \(p_{2}\) but not of \(p_{1}\) has support lower than the support of \(p_{2}\). Now, let us focus on super-sequences of both \(p_{1}\) and \(p_{2}\). Let \(\tau\in W\) be a transaction of \(W\). We define \(\mathbf{y}_{\tau}=\tau_{p_{1},p_{2}}\) as the subsequence of \(\tau\) restricted to only the sequences \(p_{1}\) and \(p_{2}\), preserving the relative order of their itemsets. For instance, let \(p_{1}=\langle A,B\rangle\), \(p_{2}=\langle C,D\rangle\) and \(\tau=\langle A,C,F,D,B\rangle\), where \(A,B,C,D,F\) are itemsets: thus, \(\mathbf{y}_{\tau}=\langle A,C,D,B\rangle\).