# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## Appendix A Missing Proofs
For each \(p\in SP_{\infty}\), there always exists a super-sequence \(\mathbf{y}\sqsupset p\) such that \(f_{\mathcal{D}}(p)=f_{\mathcal{D}}(\mathbf{y})=0\). This implies that each sequence of \(SP_{\infty}\) is not closed. Thus, \(\overline{V}_{\mathcal{D}}=\{v_{\mathcal{D}}(p):\ p\in CS(\mathcal{D})\}\) and \(|V_{\mathcal{D}}|=|\overline{V}_{\mathcal{D}}|+1\leq|CS(\mathcal{D})|+1\). Lemma 3: _We have_  
\[|C_{a,\tau}|\leq 2^{k_{a,\tau}-m_{a,\tau}}(2^{m_{a,\tau}}-1). \tag{10}\]  
Proof: \(C_{a,\tau}\) represents a subset of the set \(\Phi\) of all those subsequences of \(\tau\) that are made of only items equal to \(a\) or that come after \(a\) in \(<_{o}\), with item-length at least two and with at least one occurrence of \(a\). Let us focus on finding an upper bound to \(|\Phi|\). In order to build such a generic subsequence of \(\tau\), it is sufficient to select \(i\) occurrences of \(a\) among the \(m_{a,\tau}\) available, with \(1\leq i\leq m_{a,\tau}\), and choose \(j\) items among the remaining \(k_{a,\tau}-m_{a,\tau}\) items different from \(a\). Note that if \(i=1\), then \(j\) must be greater than \(0\). Thus, using the fact that the sum of \((^{n}_{k})\) for \(k=0,\ldots,n\) is equal to \(2^{n}\), we have  
\[|\Phi|\leq\binom{m_{a,\tau}}{1}\sum_{j=1}^{k_{a,\tau}-m_{a,\tau}}\binom{k_{a, \tau}-m_{a,\tau}}{j}+\sum_{i=2}^{m_{a,\tau}}\left[\binom{m_{a,\tau}}{i}\sum_{j= 0}^{k_{a,\tau}-m_{a,\tau}}\binom{k_{a,\tau}-m_{a,\tau}}{j}\right]\leq \tag{11}\]  
\[\leq 2^{k_{a,\tau}-m_{a,\tau}}\sum_{i=1}^{m_{a,\tau}}\binom{m_{a,\tau}}{i}=2^{ k_{a,\tau}-m_{a,\tau}}(2^{m_{a,\tau}}-1), \tag{12}\]  
where the first inequality holds because some sequences of \(\Phi\) are counted more times. Since \(|C_{a,\tau}|\leq|\Phi|\), the thesis holds. **Lemma 4**. : _Given an item \(a\) in \(\mathcal{I}\), we define the following quantity:_  
\[q(a,\eta)=1+\sum_{k=1}^{\chi_{a}}\sum_{m=1}^{k}\sum_{j=1}^{g_{a,k}\eta}\left(1 \left(k\leq\eta\right)2^{k-m}(2^{m}-1)+1\left(k>\eta\right)\sum_{i=1}^{\eta-1} \binom{k-1}{i}\right).\] (A9)  
_Let \(\bar{w}:\mathbb{R}^{+}\to\mathbb{R}^{+}\) be the function_  
\[\bar{w}(s,\eta)=\frac{1}{s}\ln\sum_{a\in\mathcal{I}}\left(q(a,\eta)e\frac{s^{2 }f_{\mathcal{D}}(\langle\{a\}\rangle)}{2|\mathcal{D}|}+|V_{\mathcal{D}(\eta)}| e\frac{s^{2}|\mathcal{D}(\eta)|}{2|\mathcal{D}|^{2}}+1\right).\] (A10)  
_Then,_  
\[\left|\frac{|\mathcal{D}\cap r|}{|\mathcal{D}|}-\frac{|S\cap r|}{|S|}\right| \leq\frac{\varepsilon}{2}. \tag{10}\]0 (A11)  
Proof. : Let us consider the function \(w\) from Theorem 7. For a given value of \(\eta\), we have that \(V_{\mathcal{D}}\subseteq(V_{\mathcal{D}}\setminus V_{\mathcal{D}(\eta)}) \cup V_{\mathcal{D}(\eta)}\), since not all the binary vectors of \(V_{\mathcal{D}(\eta)}\) necessarily belong to \(V_{\mathcal{D}}\). Thus:  
\[\left|\frac{|\mathcal{D}\cap r|}{|\mathcal{D}|}-\frac{|S\cap r|}{|S|}\right| \leq\frac{\varepsilon}{2}. \tag{10}\]1 (A12)  
where \(n=|\mathcal{D}|\). For each binary vector \(v\in V_{\mathcal{D}(\eta)}\) the maximum number of \(1\)'s is \(\left\lvert\mathcal{D}(\eta)\right\rvert\). Thus,  
\[\left|\frac{|\mathcal{D}\cap r|}{|\mathcal{D}|}-\frac{|S\cap r|}{|S|}\right| \leq\frac{\varepsilon}{2}. \tag{10}\]2 (A13)  
By using the definition of Euclidean norm, we have that, for any sequence \(p\in\mathbb{U}\),  
\[\left|\frac{|\mathcal{D}\cap r|}{|\mathcal{D}|}-\frac{|S\cap r|}{|S|}\right| \leq\frac{\varepsilon}{2}. \tag{10}\]3 (A14)  
Note that each closed sequential pattern \(p\) with \(||p||>\eta\) can only appear in transactions of \(\mathcal{D}(\eta)\) and, consequently, it is associated with a binary vector of \(V_{\mathcal{D}(\eta)}\) and not of \(V_{\mathcal{D}}\setminus V_{\mathcal{D}(\eta)}\).