## 2 p-Refined Multilevel Quasi-Monte Carlo
### Cost Complexity Theorem  
Having introduced the p-MLQMC method, we now present a complexity theorem for MLQMC, which also covers the MLMC method, when \(\delta=1\). More details can be found in [22] and in ([29], page 76). We refer to [8] for the original MLMC complexity theorem and its generalization on which the current theorem is based, see [17]. **Theorem 1**. : _Given the positive constants \(\alpha,\beta,\gamma,c_{1},c_{2},c_{3}\) such that \(\alpha\geq\dfrac{1}{2}\min\left(\beta,\delta^{-1}\gamma\right)\) with \(\delta\in(1/2,1]\), and assume that the following conditions hold:_  
1. \(|\mathbb{E}[P_{\ell}-P]|\leq c_{1}2^{-\alpha\ell}\)_,_
2. \(\mathbb{V}\left[Q_{\ell}^{\text{ML}(\text{Q})\text{MC}}\right]\leq c_{2}2^{- \beta\ell}N_{\ell}^{-1/\delta}\) _and_
3. \(C_{\ell}\leq c_{3}2^{\gamma\ell}\)_._  
_Then, there exists a positive constant \(c_{4}\) such that for any \(\epsilon<\exp(-1)\) there exists an \(L\) and a sequence \(\{N_{\ell}\}_{\ell=0}^{L}\) for which the multilevel estimator, \(Q_{L}^{\text{ML}(\text{Q})\text{MC}}\) has an \(\text{MSE}\leq\epsilon^{2}\), and_  
\[\text{cost}(Q^{\text{ML}(\text{Q})\text{MC}})\leq \begin{cases}c_{4}\epsilon^{ -2\delta}&\text{if}\quad\delta\beta>\gamma,\\ c_{4}\epsilon^{-2\delta}\left(\log\ \epsilon\right)^{1+\delta}&\text{if}\quad\delta \beta=\gamma,\\ c_{4}\epsilon^{-2\delta-(\gamma-\delta\beta)/\alpha}&\text{if}\quad\delta \beta<\gamma.\end{cases}  \tag{19}\]  
The constant \(\alpha\) in Assumption 1 of Theorem 1, represents the rate at which \(\mathbb{E}\left[\Delta P_{\ell}\right]\) decreases with increasing level \(\ell\). The constant \(\beta\) in Assumption 2, stands for the decay rate of \(\mathcal{V}_{\ell}\), i.e., the variance of the estimator of the difference on level \(\ell\). The constant \(\gamma\) in Assumption 3, is determined by the efficiency of the solver. This factor will be different for h-refinement and p-refinement. All three factors will be estimated on the fly in our numerical experiments. The parameter \(\delta\) depends on the Quasi-Monte Carlo (QMC) rule used. The theorem can now be interpreted as follows. When the variance \(\mathcal{V}_{\ell}\) decreases faster with increasing level \(\ell\) than the cost increases, i.e., \(\delta\beta>\gamma\), the dominant computational cost is located on the coarsest level, which is small because \(C_{0}\) is small. Conversely, if the variance decreases slower with increasing level \(\ell\) than the cost increases, i.e., \(\delta\beta<\gamma\), the dominant computational cost will be located on the finest level. The cost will be small because \(\mathcal{V}_{L}\) is small. Observe that if \(\mathbb{E}[P_{\ell}]\to\mathbb{E}[P]\), then \(V_{\ell}\to 0\), see Equation (7), as \(\ell\) increases. Hence, the number of samples \(N_{\ell}\) will be a decreasing function of \(\ell\). This means that most samples will be taken on the coarse mesh, where samples are cheap, whereas increasingly fewer samples are required on the finer, but more expensive meshes. In practice, the number of samples must be truncated to \(\lceil N_{\ell}\rceil\), the smallest integer larger than or equal to \(N_{\ell}\). Using Equation (10), the total cost of the MLMC estimator, from Equation (8), can be written as  
\[\text{cost}(Q^{\text{MLMC}})=\dfrac{2}{\epsilon^{2}}\left(\sum_{\ell=0}^{L} \sqrt{V_{\ell}C_{\ell}}\right)^{2}. \tag{20}\]  
Following this theorem, we note that the optimal cost of the MLMC estimator, which corresponds to \(\delta=1\), is proportional to \(\epsilon^{-2}\) when the variance over the levels decreases faster than the cost per level increases, i.e., \(\beta>\gamma\). Similarly for the MLQMC estimator, we can hope to achieve an optimal cost proportional to \(\epsilon^{-1}\). Note that this is only true in the limit when \(\delta\to 1/2\). We will show in our numerical experiments that the theoretically derived asymptotic cost complexity is close to what we observe. Quasi-Monte Carlo methods work so well because they are based on the concept of _weighted_ function spaces and _low effective dimension_.