TITLE: Is the convergence test for integrals limited to series and improper integrals?
QUESTION [0 upvotes]: In my Calculus text book there is a theorem named The Integral Test that states:
If the function $f$ is continous, positive and nondecreasing on the interval $x\in[a, \infty)$, then
$$\sum^{\infty}_{x=1} f(x) \text{ converges} \Leftrightarrow \int^{\infty}_{a} f(x) \text{ converges}$$
Based on my home made proof, the more general result
$$\sum^{b}_{x=1} f(x) \text{ converges} \Leftrightarrow \int^{b}_{a} f(x) \text{ converges}$$
should also hold.
Is my result true or is indeed The Integral Test limited to series and improper integrals?

REPLY [1 votes]: Better write $\sum^{\infty}_{k=1} f(k)$ instead of $\sum^{\infty}_{x=1} f(x)$.
If $b \in \mathbb N$, then $\sum^{b}_{k=1} f(k)$ is a finite sum ! No convergence considerations are needed !
What do you mean by "$\int^{b}_{a} f(x) dx \text{ converges}$" ?


text:
\subsection{DNN approximations for Monte Carlo Euler approximations}
\label{subsec:DNN:MCE}

\begin{prop}\label{Thm:ApproxOfEulerWithGronwall}
	Let $N, d \in \N$, $c, C \in [0,\infty)$,
	 $T, \mathfrak{D} \in (0,\infty)$, $q\in(2,\infty)$, $\varepsilon\in (0,1]$,  $(\tau_n)_{n\in\{0,1,\dots,N\}}\allowbreak\subseteq\R$
	satisfy
	for all $n\in\{0,1,\dots,N\}$ that $\tau_n=\tfrac{nT}{N}$
and
	\begin{equation}\label{ApproxOfEulerWithGronwall:paramBound}
	\mathfrak{D}=\big[\tfrac{720q}{(q-2)}\big][\LogBin(\eps^{-1})+q+1]-504,
	\end{equation}
	let
	$\Phi\in \ANNs $
	satisfy
	for all $x\in \R^d$ that $\inDimANN(\Phi)=\outDimANN(\Phi)=d$ and $\Vert (\functionANN(\Phi))(x)\Vert\le C +c\Vert x\Vert$,
	let
	$Y= (Y^{x,y }_t)_{(t,x,y)\in [0,T]\times \R^d\times(\R^d)^N} \colon\allowbreak [0,T]\times \R^d\times (\R^d)^N \to \R^d $
satisfy for all
	$n\in\{0,1,\dots,N-1\}$,
	$ t \in [\tau_{n},\tau_{n+1}]$,
	$ x \in \R^d $, $y=(y_1,y_2,\dots, y_N)\in (\R^d)^N$
	that $\affineProcess^{x,y }_0=x$ and
	\begin{equation}
	\label{ApproxOfEulerWithGronwall:Y_processes}
	\begin{split}
	&\affineProcess^{x,y }_t
	=
	\affineProcess^{x,y }_{\tau_n}+ \left(\tfrac{tN}{T}-n\right)\!\left[\tfrac{T}{N}(\functionANN(\Phi)) (
	\affineProcess^{x,y }_{\tau_n}
	)
	+
	y_{n+1}\right]\!,
	\end{split}
	\end{equation}
	and let $g_n\colon \R^d\times (\R^d)^N\to [0,\infty)$, $n\in\{0,1,\dots,N\}$,  satisfy for all $n\in\{0,1,\dots,N\}$,
	$ x \in \R^d $, $y=(y_1,y_2,\dots, y_N)\in (\R^d)^N$ that
	\begin{equation}
	g_{n}(x,y)=\bigg[\Vert x\Vert + C \tau_n+
	\max_{m\in\{0,1,\dots,n\}}\big\Vert \smallsum_{k=1}^{m} y_{k}\big\Vert\bigg]
	\exp(c \tau_n)
	\end{equation}
	(cf.\ \Cref{Def:euclideanNorm,Def:ANN,Definition:ANNrealization,Definition:Relu1}).
	Then there exist $\Psi_{y}\in \ANNs$,  $y\in (\R^d)^N$, such that
	\begin{enumerate}[(i)]
		\item \label{ApproxOfEulerWithGronwall:Function} it holds for all  $y\in (\R^d)^N$ that $\functionANN (\Psi_{y})\in C(\R^{d+1},\R^d)$,
		\item it holds for all
		$n\in\{0,1,\dots,N-1\}$,
		$ t \in [\tau_{n},\tau_{n+1}]$,
		$x\in\R^d$,
		$y\in (\R^d)^N$ that
		\begin{equation}
		\Vert \affineProcess^{x,y }_t -(\functionANN (\Psi_{y}))(t,x)\Vert
		\le\varepsilon \big[2\sqrt{d}+(g_{n}(x,y))^q+(g_{n+1}(x,y))^q\big],
		\end{equation}
		\item it holds for all
		$n\in\{0,1,\dots,N-1\}$,
		$ t \in [\tau_{n},\tau_{n+1}]$,
		$x\in\R^d$,
		$y\in (\R^d)^N$
		that
		\begin{equation}
		\Vert (\functionANN (\Psi_{y}))(t,x)\Vert
		\le 6\sqrt{d}+2\big[(g_{n}(x,y))^2+(g_{n+1}(x,y))^2\big],
		\end{equation}
		\item \label{ApproxOfEulerWithGronwall:ItemParams}
		it holds for all  $y\in (\R^d)^N$ that
		\begin{equation}
		\begin{split}
		\paramANN(\Psi_{y})
		&\le \tfrac{9}{2}\, N^6 d^{16} \big[  2 (\lengthANN(\Phi) - 1)
		+
		\mathfrak{D}+(
		24
		+6\lengthANN(\Phi)
		+   [4+\paramANN(\Phi)]^{2})^{2}
		\big]^{2},
		\end{split}
		\end{equation}
		\item \label{ApproxOfEulerWithGronwall:Continuity}
		it holds  for all $t\in [0,T]$, $x\in\R^d$ that $
		[(\R^d)^N\ni y\mapsto (\functionANN (\Psi_{y}))(t,x)\in\R^d] \in C((\R^d)^N,\R^d)$,
		and
		\item \label{ApproxOfEulerWithGronwall:Adaptedness}
		it holds  for all    $n\in\{0,1,\dots, N\}$, $t\in [0,\tau_n]$, $x\in\R^d$, $y=(y_1,y_2,\dots, y_N)$, $z=(z_1,z_2,\allowbreak\dots, z_N)\in (\R^d)^N$  with $\forall\, k\in \N\cap [0,n]\colon y_k=z_k$ that
		\begin{equation}
		(\functionANN (\Psi_{y}))(t,x)=(\functionANN (\Psi_{z}))(t,x).
		\end{equation}
	\end{enumerate}
\end{prop}

\begin{proof}[Proof of \Cref{Thm:ApproxOfEulerWithGronwall}]
	Throughout this proof let
	$\Psi_{y}\in \ANNs$,  $y\in (\R^d)^N$, satisfy  that
	\begin{enumerate}[(I)]
		\item \label{ProofApproxOfEulerWithGronwall:Function} it holds for all  $y\in (\R^d)^N$  that $\functionANN (\Psi_{y})\in C(\R^{d+1},\R^d)$,
		\item\label{ProofApproxOfEulerWithGronwall:Error} it holds for all
		$n\in\{0,1,\dots,N-1\}$,
		$ t \in [\tau_{n},\tau_{n+1}]$,
		$x\in\R^d$,
		$y\in (\R^d)^N$  that
		\begin{equation}
		\Vert \affineProcess^{x,y }_t -(\functionANN (\Psi_{y}))(t,x)\Vert
		\le \varepsilon \big(2\sqrt{d}+\|  Y_{\tau_{n}}^{x,y }\|^q+\|  Y_{\tau_{n+1}}^{x,y }\|^q\big),
		\end{equation}
		\item \label{ProofApproxOfEulerWithGronwall:Growth} it holds for all
		$n\in\{0,1,\dots,N-1\}$,
		$ t \in [\tau_{n},\tau_{n+1}]$,
		$x\in\R^d$,
		$y\in (\R^d)^N$  that
		\begin{equation}
		\Vert (\functionANN (\Psi_{y}))(t,x)\Vert
		\le 6\sqrt{d}+2\big(\Vert Y_{\tau_{n}}^{x,y }\Vert^2+\Vert Y_{\tau_{n+1}}^{x,y }\Vert^2\big),
		\end{equation}
		\item \label{ProofApproxOfEulerWithGronwall:ItemParams}
		it holds for all  $y\in (\R^d)^N$ that
		\begin{align*}
		&\paramANN(\Psi_{y}) \numberthis
		\\
		&\le\tfrac{1}{2} \Big[  6d^2N^2(\lengthANN(\Phi) - 1)
		+3N
		\big[d^2 \mathfrak{D}+(
		23
		+6N (\lengthANN(\Phi) - 1)
		+  7d^2+N [4d^2+\paramANN(\Phi)]^{2})^{2}\big]
		\Big]^{2},
		\end{align*}
		\item \label{ProofApproxOfEulerWithGronwall:Continuity}
		it holds  for all  $t\in [0,T]$, $x\in\R^d$ that
		$
		[(\R^d)^N\ni y\mapsto (\functionANN (\Psi_{y}))(t,x)\in\R^d]\in C((\R^d)^N,\R^d)
		$,
		and
		\item \label{ProofApproxOfEulerWithGronwall:Adaptedness}
		it holds  for all    $n\in\{0,1,\dots, N\}$, $t\in [0,\tau_n]$, $x\in\R^d$, $y=(y_1,y_2,\dots, y_N),\allowbreak z=(z_1,z_2,\allowbreak\dots,  z_N)\in (\R^d)^N$  with $\forall\, k\in \N\cap [0,n]\colon y_k=z_k$  that
		\begin{equation}
		(\functionANN (\Psi_{y}))(t,x)=(\functionANN (\Psi_{z}))(t,x)
		\end{equation}
	\end{enumerate}
	(cf.\ Grohs et al.~\cite[Proposition~3.10]{GrohsHornungJentzen2019} (applied with $N \is N$, $ d \is d$, $a \is \mathfrak{r}$, $T \is T$, $t_0 \is \tau_0$, $t_1 \is \tau_1$, $\dots$, $t_N \is \tau_N$,
	$\mathfrak{D} \is \mathfrak{D}$, $\varepsilon \is \varepsilon$, $q \is q$, $Y \is Y$
	in the notation of Grohs et al.~\cite[Proposition~3.10]{GrohsHornungJentzen2019})).
	Note that 	\eqref{ProofApproxOfEulerWithGronwall:ItemParams} ensures that  for all  $y\in (\R^d)^N$ it holds  that
	\begin{equation}
	\begin{split}
	&\paramANN(\Psi_{y})
	\\&\le\tfrac{1}{2} \Big[  6d^2N^2  (\lengthANN(\Phi) - 1)
	+3N
	\big[d^2 \mathfrak{D}+(
	23
	+6N  (\lengthANN(\Phi) - 1)
	+  7d^2+N d^4 [4+\paramANN(\Phi)]^{2})^{2}\big]
	\Big]^{2}
		\\&\le\tfrac{1}{2} \Big[  6d^2N^2 (\lengthANN(\Phi) - 1)
	+3N
	\big[d^2 \mathfrak{D}+N^2 d^8(
	23
	+6(\lengthANN(\Phi) -1) + 7
	+   [4+\paramANN(\Phi)]^{2})^{2}\big]
	\Big]^{2}
	\\&=\tfrac{1}{2} \Big[  6d^2N^2 (\lengthANN(\Phi) - 1)
	+3N
	\big[d^2 \mathfrak{D}+N^2 d^8(
	24
	+6\lengthANN(\Phi)
	+   [4+\paramANN(\Phi)]^{2})^{2}\big]
	\Big]^{2}.
	\end{split}
	\end{equation}
	Hence, we obtain that   for all  $y\in (\R^d)^N$ it holds that
	\begin{equation}\label{ProofApproxOfEulerWithGronwall:EstimateParams}
	\begin{split}
	\paramANN(\Psi_{y})
	&\le\tfrac{1}{2} \Big[  6d^2N^2 (\lengthANN(\Phi) - 1)
	+3N^3 d^8
	\big[ \mathfrak{D}+(
24
	+6\lengthANN(\Phi)
	+   [4+\paramANN(\Phi)]^{2})^{2}\big]
	\Big]^{2}
	\\&\le\tfrac{9}{2}\, N^6 d^{16} \big[  2 (\lengthANN(\Phi) - 1)
	+
	\mathfrak{D}+(
	24
	+6\lengthANN(\Phi)
	+   [4+\paramANN(\Phi)]^{2})^{2}
	\big]^{2}.
	\end{split}
	\end{equation}
	In addition, observe that, e.g., Grohs et al.~\cite[Lemma~3.11]{GrohsHornungJentzen2019} (applied with $N \is N$, $d \is d$, $c \is c$, $C \is C$, $A_1 \is \frac{T}{N} \id_{\R^d} $, $A_2 \is \frac{T}{N} \id_{\R^d}$, $\dots$, $A_N \is \frac{T}{N} \id_{\R^d}$, $\mu \is \functionANN(\Phi)$, $Y_0 \is  (Y^{x,y }_{\tau_0})_{(x,y)\in \R^d\times(\R^d)^N}$, $Y_1 \is  (Y^{x,y }_{\tau_1})_{(x,y)\in \R^d\times(\R^d)^N}$, $\dots$, $Y_N \is  (Y^{x,y }_{\tau_N})_{(x,y)\in \R^d\times(\R^d)^N}$  in the notation of Grohs et al.~\cite[Lemma~3.11]{GrohsHornungJentzen2019}) and the hypothesis that  $\forall \,  n\in\{0,1,\dots,N\} \colon \tau_n=\tfrac{nT}{N}$ demonstrate that 	 for all $n\in\{0,1,\dots,N\}$,
	$ x \in \R^d $, $y=(y_1,y_2,\dots, y_N)\in (\R^d)^N$ it holds that
	\begin{equation}\label{ApproxOfEuler:GronwallEstimate}
	\begin{split}
	\Vert \affineProcess^{x,y} _{\tau_n} \Vert
	&\le \bigg[\Vert x\Vert + \tfrac{C nT}{N}+
	\max_{m\in\{0,1,\dots,n\}}\big\Vert \smallsum_{k=1}^{m} y_{k}\big\Vert\bigg]
	\exp\!\left(\tfrac{c nT}{N}\right)
	\\&=\bigg[\Vert x\Vert + C \tau_n+
	\max_{m\in\{0,1,\dots,n\}}\big\Vert \smallsum_{k=1}^{m} y_{k}\big\Vert\bigg]
	\exp(c \tau_n)
	=g_n(x,y).
	\end{split}
	\end{equation}
	Combining this with  \eqref{ProofApproxOfEulerWithGronwall:Error} and \eqref{ProofApproxOfEulerWithGronwall:Growth} ensures that for all
	$n\in\{0,1,\dots,N-1\}$,
	$ t \in [\tau_{n},\tau_{n+1}]$,
	$x\in\R^d$, $y\in (\R^d)^N$ it holds that
	\begin{equation}
	\begin{split}
	\Vert \affineProcess^{x,y }_t -(\functionANN (\Psi_{y}))(t,x)\Vert
	&\le\varepsilon \big[2\sqrt{d}+\|  Y_{\tau_{n}}^{x,y }\|^q+\|  Y_{\tau_{n+1}}^{x,y }\|^q\big]
	\\&\le\varepsilon \big[2\sqrt{d}+(g_{n}(x,y))^q+(g_{n+1}(x,y))^q\big]
	\end{split}
	\end{equation}
	and
	\begin{equation}
	\begin{split}
	\Vert (\functionANN (\Psi_{y}))(t,x)\Vert
	&\le 6\sqrt{d}+2\big(\Vert Y_{\tau_{n}}^{x,y }\Vert^2+\Vert Y_{\tau_{n+1}}^{x,y }\Vert^2\big)
	\\&\le 6\sqrt{d}+2\big[(g_{n}(x,y))^2+(g_{n+1}(x,y))^2\big].
	\end{split}
	\end{equation}
	This, \eqref{ProofApproxOfEulerWithGronwall:Function},  \eqref{ProofApproxOfEulerWithGronwall:Continuity}, \eqref{ProofApproxOfEulerWithGronwall:Adaptedness}, and \eqref{ProofApproxOfEulerWithGronwall:EstimateParams} establish items~\eqref{ApproxOfEulerWithGronwall:Function}--\eqref{ApproxOfEulerWithGronwall:Adaptedness}.
	The proof of \Cref{Thm:ApproxOfEulerWithGronwall} is thus completed.
\end{proof}

\begin{prop}\label{Cor:ApproxOfMCSum}
	Let $M,N, d,\mathfrak{d} \in \N$,  $\alpha, c, C, \mathfrak{C} \in[0,\infty)$, $T, \mathfrak{D} \in (0,\infty)$,
$q\in(2,\infty)$, $\varepsilon\in (0,1]$, $\drift, \initial \in \ANNs$ satisfy  that  $\inDimANN(\drift)=\outDimANN(\drift)= \inDimANN(\initial)=d$, $\outDimANN(\initial)=\mathfrak{d}$, and
		\begin{equation}\label{ApproxOfMCSum:paramBound}
		\mathfrak{D}= \big[\tfrac{720q}{q-2} \big] [\LogBin(\eps^{-1})+q+1]-504,
		\end{equation}
assume for all $x,y\in\R^d$ that $\|(\functionANN(\drift))(x)\Vert\le C + c\Vert x\Vert$ and
\begin{align}
	\label{ApproxOfMCsum:Lipschitz}
	\Vert (\functionANN(\initial)) (x) - (\functionANN(\initial)) (y)\Vert \leq \mathfrak{C} (1 + \Vert x\Vert^{\alpha} + \Vert y \Vert^{\alpha})\Vert  x-y\Vert,
\end{align}
	let $ ( \Omega, \mathcal{F}, \P ) $ be a probability space,
	let $W^m=(W_n^m)_{n\in\{0,1,\dots,N\}}\colon \{0,1,\dots,N\}\times  \Omega\to \R^d$, $m\in\{1,2,\dots,M\}$, be stochastic processes which satisfy for all $m\in\{1,2,\dots,M\}$ that $W_0^m=0$,
	 let
	$Y^m= (Y^{m,x }_t (\omega))_{(t, x, \omega) \in [0,T] \times \R^d \times \Omega} \colon\allowbreak [0,T]\times \R^d\times\Omega \to \R^d $, $m\in\{1,2,\dots,\allowbreak M\}$,
 satisfy for all
	$m\in\{1,2,\dots,\allowbreak M\}$,
	$ x \in \R^d $,
	$n\in\{0,1,\dots,N-1\}$,
	$ t \in \big[\tfrac{nT}{N},\tfrac{(n+1)T}{N}\big]$
	that $\affineProcess^{m,x }_0=x$ and
	\begin{equation}
	\label{ApproxOfMCSum:Y_processes}
	\begin{split}
	&\affineProcess^{m,x }_t
	=
	\affineProcess^{m,x }_{\frac{nT}{N}}+ \left(\tfrac{tN}{T}-n\right)\left[\tfrac{T}{N}(\functionANN(\drift)) (
	\affineProcess^{m,x }_{\frac{nT}{N}}
	)
	+
	W_{n+1}^{m}-W_{n}^{m}\right],
	\end{split}
	\end{equation}
			and let
			$h_{m,r}\colon \R^d\times \Omega\to [0,\infty)$,  $m\in\{1,2,\dots, M\}$, $r\in (0,\infty)$, satisfy for all  $m\in\{1,2,\dots, M\}$, $r\in (0,\infty)$,
			$ x \in \R^d $ that
			\begin{equation}\label{ApproxOfMCSum:AuxFunctionTwo}
			h_{m,r}(x)=1+ \left[\Vert x\Vert + C T+
			\max_{n\in\{0,1,\dots,N\}}\Vert  W_n^m\Vert\right]^r
			\exp(rc T)
			\end{equation}
	(cf.\ \Cref{Def:euclideanNorm,Def:ANN,Definition:ANNrealization,Definition:Relu1}).
	Then there exists $(\Psi_{\omega})_{\omega\in \Omega}\subseteq \ANNs$ such that
	\begin{enumerate}[(i)]
		\item \label{ApproxOfMCsum:Function} it holds for all   $\omega\in \Omega$ that $\functionANN (\Psi_{\omega})\in C(\R^{d+1},\R^\mathfrak{d})$,
		\item it holds for all
		$ t \in [0,T]$,
		$x\in\R^d$, $\omega\in \Omega$ that
	\begin{equation}
	\begin{split}
	&\left\Vert(\functionANN(\Psi_{\omega}))(t,x)-\frac{1}{M}\left[\smallsum\limits_{m=1}^M (\functionANN(\initial))(Y_t^{m,x}(\omega))\right]\right\Vert
	\\&\le \frac{2\varepsilon \mathfrak{C} \sqrt{d}}{M}\bigg[\smallsum\limits_{m=1}^M   \left[1 +2 {d}^{\nicefrac{\alpha}{2}} 6^\alpha
	|h_{m,2}(x,\omega)|^\alpha \right]
	h_{m,q}(x,\omega) \bigg],
	\end{split}
	\end{equation}
		\item \label{ApproxOfMCsum:ItemParams}
		it holds for all  $\omega\in \Omega$ that
				\begin{equation}
				\begin{split}
				\paramANN(\Psi_\omega)
				&\le 2 M^2 \paramANN(\initial) + 9 M^2 N^6 d^{16} \big[ 2 \lengthANN(\drift)
				+
				 \mathfrak{D}+(
				24
				+6\lengthANN(\drift)
				+   [4+\paramANN(\drift) ]^{2} )^{2}
				\big]^{2},
				\end{split}
				\end{equation}
		and
		\item \label{ApproxOfMCsum:Continuity}
		it holds  for all  $t\in [0,T]$, $x\in\R^d$ that $\Omega\ni \omega\mapsto (\functionANN (\Psi_{\omega}))(t,x)\in\R^\mathfrak{d}$
		is measurable.
	\end{enumerate}
\end{prop}

\begin{proof}[Proof of Proposition~\ref{Cor:ApproxOfMCSum}]
	Throughout this proof
	let $\tau_0, \tau_1, \ldots, \tau_N \in \R$
	satisfy
	for all $n\in\{0,1, \allowbreak \dots,N\}$ that $\timeGrid_n=\tfrac{nT}{N}$,
	let
	$g_{m}\colon \R^d\times \Omega\to [0,\infty)$,  $m\in\{1,2,\dots, M\}$,  satisfy for all  $m\in\{1,2,\dots, M\}$,
	$ x \in \R^d $ that
	\begin{equation}\label{ApproxOfMCSum:AuxFunctionOne}
	g_{m}(x)=\left[\Vert x\Vert + CT+
	\max_{n\in\{0,1,\dots,N\}}\big\Vert  \smallsum_{l=1}^{n} \big(W_{l}^m-W_{l-1}^m\big)\big\Vert\right]
	\exp(c T),
	\end{equation}
	let $(\Psi_{\omega,m})_{\omega\in\Omega,m\in\{1,2,\dots, M\}}\allowbreak\subseteq \ANNs$ satisfy that
		\begin{enumerate}[(I)]
			\item \label{ApproxOfMCsumProof:Function} it holds for all   $m\in\{1,2,\dots, M\}$, $\omega\in \Omega$ that $\functionANN (\Psi_{\omega,m})\in C(\R^{d+1},\R^d)$,
			\item \label{ApproxOfMCsumProof:EstimateDifference}  it holds for all    $m\in\{1,2,\dots, M\}$,
			$ t \in [0,T]$,
			$x\in\R^d$, $\omega\in \Omega$ that
			\begin{equation}
			\Vert \affineProcess^{m, x }_t (\omega) -(\functionANN (\Psi_{\omega,m}))(t,x)\Vert
			\le 2\varepsilon \sqrt{d}\, \big[1+(g_{m}(x,\omega))^q\big],
			\end{equation}
			\item \label{ApproxOfMCsumProof:EstimateGrowth}  it holds for all   $m\in\{1,2,\dots, M\}$,
			$ t \in [0,T]$,
			$x\in\R^d$, $\omega\in \Omega$
			that
			\begin{equation}
			\Vert (\functionANN (\Psi_{\omega,m}))(t,x)\Vert
			\le  6 \sqrt{d}\, \big[1+(g_{m}(x,\omega))^2\big],
			\end{equation}
			\item \label{ApproxOfMCsumProof:ItemParams}
			 it holds
			 for all   $m\in\{1,2,\dots, M\}$, $\omega\in \Omega$  that
						\begin{equation}
						\begin{split}
						\paramANN(\Psi_{\omega,m})
						&\le\tfrac{9}{2}\, N^6 d^{16} \big[  2 \lengthANN(\drift)
						+
						 \mathfrak{D}+(
						24
						+6\lengthANN(\drift)
						+   [4+\paramANN(\drift)]^{2})^{2}
						\big]^{2},
						\end{split}
						\end{equation}
			and
			\item \label{ApproxOfMCsumProof:Continuity}
			 it holds
		  for all $m\in\{1,2,\dots, M\}$,  $t\in [0,T]$, $x\in\R^d$ that $\Omega\ni \omega\mapsto (\functionANN (\Psi_{\omega,m}))(t,x)\in\R^d$
			is measurable
		\end{enumerate}
		(cf.\ \Cref{Thm:ApproxOfEulerWithGronwall} (applied with $N \is N$, $d \is d$, $c \is c$, $C \is C$, $T \is T$, $\mathfrak{D} \is \mathfrak{D}$, $ q \is q$, $\varepsilon \is \varepsilon$, $\tau_0 \is \tau_0$, $\tau_1 \is \tau_1, \ldots, \tau_N \is \tau_N$, $\Phi \is \drift$ in the notation of  \Cref{Thm:ApproxOfEulerWithGronwall})),
let $\mathbb{I}\in \ANNs$ satisfy for all $x\in\R^d$ that $\functionANN(\mathbb{I})\in C(\R^d,\R^d)$, $\dims(\mathbb{I})=(d,2d,d)$, and $(\functionANN(\mathbb{I}))(x)=x$ (cf.~\cite[Lemma~5.4]{JentzenSalimovaWelti2018}),
	let $(\psi_{\omega,m})_{\omega\in\Omega,m\in\{1,2,\dots, M\}}\subseteq \ANNs$ satisfy for all $m\in\{1,2,\dots, M\}$, $\omega\in\Omega$ that $\psi_{\omega,m}=\concANN{\initial}{\Psi_{\omega,m}}$ (cf.\ Definition~\ref{Definition:ANNconcatenation}),
	and let $(\Phi_{\omega})_{\omega\in\Omega}\subseteq \ANNs$ satisfy that
	\begin{enumerate}[(A)]
		\item \label{ApproxOfMCsum:MCsumItemOne}   it holds for all $\omega\in\Omega$  that $\functionANN(\Phi_{\omega})\in C(\R^{\inDimANN(\psi_{\omega,1})},\R^{\outDimANN(\psi_{\omega,1})})$,
		\item\label{ApproxOfMCsum:MCsumItemTwo}   it holds for all $\omega\in\Omega$ that $\paramANN(\Phi_\omega)\le M^2 \paramANN(\psi_{\omega,1})$, and
		\item\label{ApproxOfMCsum:MCsumItemThree}  it holds for all  $t\in\R$, $x\in\R^{d}$, $\omega\in\Omega$  that
			\begin{equation}
			\begin{split}
			(\functionANN (\Phi_\omega))(t,x)=\frac{1}{M}\smallsum\limits_{m=1}^M (\functionANN (\psi_{\omega,m}))(t,x)
			\end{split}
			\end{equation}
	\end{enumerate}
	(cf.\ Grohs et al.~\cite[Proposition 2.25]{GrohsHornungJentzen2019}).
	Note that \eqref{ApproxOfMCsum:MCsumItemTwo}, \eqref{ApproxOfMCsumProof:ItemParams}, Grohs et al.~\cite[item~(iii) in Proposition 2.16]{GrohsHornungJentzen2019}, and the fact that $\dims(\mathbb{I})=(d,2d,d)$ demonstrate that
	for all $\omega\in\Omega$ it holds that
		\begin{equation}\label{ApproxOfMCsum:ParamEstimate}
		\begin{split}
		\paramANN(\Phi_\omega) &\le M^2 \paramANN(\psi_{\omega,1})
		\le 2 M^2 [\paramANN(\initial)+\paramANN(\Psi_{\omega,1})]
		\\&\le  2 M^2 \paramANN(\initial) + 9 M^2 N^6 d^{16} \big[  2 \lengthANN(\drift)
		+
		 \mathfrak{D}+(
		24
		+6\lengthANN(\drift)
		+   [4+\paramANN(\drift)]^{2})^{2}
		\big]^{2}.
		\end{split}
		\end{equation}
	Moreover, observe that \eqref{ApproxOfMCsum:MCsumItemOne}, \eqref{ApproxOfMCsum:MCsumItemThree}, and Grohs et al.~\cite[item~(iv) in Proposition 2.16]{GrohsHornungJentzen2019}   imply that for all  $t\in\R$, $x\in\R^{d}$, $\omega\in\Omega$ it holds that $\functionANN (\Phi_\omega)\in C(\R^{d+1},\R^\mathfrak{d})$ and
	\begin{equation}\label{ApproxOfMCsum:PhiSum}
	\begin{split}
	(\functionANN (\Phi_\omega))(t,x)=\frac{1}{M}\smallsum\limits_{m=1}^M (\functionANN (\initial))((\functionANN(\Psi_{\omega,m}))(t,x)).
	\end{split}
	\end{equation}
	Next note that the fact that  $ \forall \, m\in\{1,2,\dots, M\} \colon W_0^m=0$ ensures that for all $n\in\{1,2,\dots, N\}$, $m\in\{1,2,\dots, M\}$ it holds that
		\begin{equation}\label{telescopicSum}
			\begin{split}
			\smallsum\limits_{l=1}^{n} \big(W_{l}^m-W_{l-1}^m\big)=W_{n}^m-W_{0}^m=W_{n}^m.
			\end{split}
		\end{equation}
	Combining this with \eqref{ApproxOfMCSum:AuxFunctionOne} proves that
	for all  $m\in\{1,2,\dots, M\}$,
	$ x \in \R^d $ it holds that
	\begin{equation}\label{ApproxOfMCSum:AuxFunctionOneTilde}
	g_{m}(x)=\left[\Vert x\Vert + CT+
	\max_{n\in\{0,1,\dots,N\}}\Vert W_{n}^m \Vert\right]
	\exp(cT).
	\end{equation}
	In addition, observe that \eqref{ApproxOfMCSum:Y_processes} and the fact that
	$\forall \, n\in\{0,1,\dots,N\} \colon \timeGrid_n=\tfrac{nT}{N}$
	assure that for all    $m\in\{1,2,\dots, M\}$,  $n\in\{0, 1, \dots,N-1\}$,
	$ x \in \R^d $ it holds that
	\begin{equation}
	\begin{split}
 \affineProcess^{m,x} _{\timeGrid_{n+1}}  &= \affineProcess^{m,x} _{\timeGrid_{n}}  + \tfrac{T }{N} (\functionANN(\drift)) (
 \affineProcess^{m,x }_{\timeGrid_n}
 ) + W_{n+1}^{m}-W_{n}^{m}.
	\end{split}
	\end{equation}
	Induction and \eqref{telescopicSum} hence show
 that for all    $m\in\{1,2,\dots, M\}$,  $n\in\{0, 1, \dots,N-1\}$,
$ x \in \R^d $ it holds that
\begin{equation}
\begin{split}
\affineProcess^{m,x} _{\timeGrid_{n+1}}  &= \affineProcess^{m,x} _{\timeGrid_{0}}  + \tfrac{T }{N} \left[\smallsum\limits_{l=0}^n (\functionANN(\drift)) (
\affineProcess^{m,x }_{\timeGrid_l}
) \right] + \left[\smallsum\limits_{l=0}^n ( W_{l+1}^{m}-W_{l}^{m} ) \right]\\
& = x + \tfrac{T }{N} \left[\smallsum\limits_{l=0}^n (\functionANN(\drift)) (
\affineProcess^{m,x }_{\timeGrid_l}
) \right] +  W_{n+1}^{m}.
\end{split}
\end{equation}
This and the assumption that $ \forall \, x \in \R^d \colon \|(\functionANN(\drift))(x)\Vert\le C + c\Vert x\Vert$ establish that for all    $m\in\{1,2,\dots, M\}$,  $n\in\{0, 1, \dots,N\}$,
$ x \in \R^d $ it holds that
\begin{equation}
\begin{split}
\Vert  \affineProcess^{m,x} _{\timeGrid_{n}}  \Vert &\le \|x\| +  \tfrac{T }{N} \left[ \smallsum\limits_{l=0}^{n-1} \| (\functionANN(\drift)) (
\affineProcess^{m,x }_{\timeGrid_l}
) \| \right] + \| W_{n}^{m} \|\\
& \le \|x\| +  \tfrac{ T}{N} \left[\smallsum\limits_{l=0}^{n-1} ( C + c\Vert  \affineProcess^{m,x} _{\timeGrid_{l}}  \Vert ) \right] + \| W_{n}^{m} \|\\
& \le \|x\| + C T + \left[\max_{k\in\{0,1,\dots,N\}}\Vert  W_{k}^m\Vert \right] + \tfrac{c T}{N} \left[ \smallsum\limits_{l=0}^{n-1} \Vert  \affineProcess^{m,x} _{\timeGrid_{l}}  \Vert \right].
\end{split}
\end{equation}
The time-discrete Gronwall inequality, e.g., in  Hutzenthaler et al.~\cite[Lemma~2.1]{HutzenthalerPricing2019} (applied with $N \is N$, $\alpha \is( \|x\| +C T + \max_{k\in\{0,1,\dots,N\}}\Vert  W_{k}^m(\omega)\Vert)$, $\beta_0 \is \frac{c T}{N}$, $\beta_1 \is \frac{cT}{N}$, $\dots$, $\beta_{N-1} \is \frac{c T}{N}$, $\epsilon_0 \is \|x\|$, $\epsilon_1 \is  \Vert  \affineProcess^{m,x} _{\timeGrid_{1}}(\omega)  \Vert$, $\dots$, $\epsilon_N \is  \Vert  \affineProcess^{m,x} _{\timeGrid_{N}}(\omega)  \Vert$ for  $m\in\{1,2,\dots, M\}$,
$ x \in \R^d $, $\omega\in\Omega$ in the notation of  Hutzenthaler et al.~\cite[Lemma~2.1]{HutzenthalerPricing2019}) and \eqref{ApproxOfMCSum:AuxFunctionOneTilde}
 hence demonstrate that 	 for all $m\in\{1,2,\dots, M\}$,  $n\in\{0,1,\dots,N\}$,
		$ x \in \R^d $ it holds that
		\begin{equation}\label{Gronwall:GridpointEstimate}
		\begin{split}
		&\Vert \affineProcess^{m,x} _{\timeGrid_n} \Vert
\le\left[\Vert x\Vert + C T+
		\max_{k\in\{0,1,\dots,N\}}\Vert  W_{k}^m\Vert \right]
		\exp(c T)=g_{m}(x)
		.
		\end{split}
		\end{equation}
		In addition,
		note that \eqref{ApproxOfMCSum:Y_processes} and the fact that  $\forall \, n\in \{0,1,\dots, N-1\}, t\in [\timeGrid_n,\timeGrid_{n+1}] \colon \tfrac{t-\timeGrid_n}{\timeGrid_{n+1}-\timeGrid_n}=\tfrac{tN}{T}-n$
		ensure that for all $m\in\{1,2,\dots, M\}$, $n\in \{0,1,\dots, N-1\}$, $t\in [\timeGrid_n,\timeGrid_{n+1}]$, $x\in\R^d$  it holds that
		\begin{align*}
		&
		\affineProcess^{m,x}_{\timeGrid_{n+1}} \big[\tfrac{t-\timeGrid_n}{\timeGrid_{n+1}-\timeGrid_n}\big]+\affineProcess^{m,x}_{\timeGrid_n}\big[1- \tfrac{t-\timeGrid_n}{\timeGrid_{n+1}-\timeGrid_n}\big]
				\\&=
				\big( \affineProcess^{m,x }_{\timeGrid_n}+ \big[\tfrac{\timeGrid_{n+1}N}{T}-n\big]\big[\tfrac{T}{N}(\functionANN(\drift)) (
						\affineProcess^{m,x }_{\timeGrid_n}
						)
						+
						W_{n+1}^{m}-W_{n}^{m}\big]\big)
				\tfrac{t-\timeGrid_n}{\timeGrid_{n+1}-\timeGrid_n}
+\affineProcess^{m,x}_{\timeGrid_n}\big[1- \tfrac{t-\timeGrid_n}{\timeGrid_{n+1}-\timeGrid_n}\big]
		\\&= 		\left(\affineProcess^{m,x}_{\timeGrid_n}+ \big[\tfrac{T}{N}(\functionANN(\drift))(
		\affineProcess^{m,x}_{\timeGrid_n}
		)
		+
		W_{n+1}^m-W_{n}^m\big]\right)
		\tfrac{t-\timeGrid_n}{\timeGrid_{n+1}-\timeGrid_n}
+
		\affineProcess^{m,x}_{\timeGrid_n}\big[1- \tfrac{t-\timeGrid_n}{\timeGrid_{n+1}-\timeGrid_n}\big]
		\\&= \affineProcess^{m,x}_{\timeGrid_n}+  \big[\tfrac{T}{N}(\functionANN(\drift))(
		\affineProcess^{m,x}_{\timeGrid_n}
		)
		+
			W_{n+1}^m-W_{n}^m\big]
		\tfrac{t-\timeGrid_n}{\timeGrid_{n+1}-\timeGrid_n}
		\\&=Y_t^{m,x}. \numberthis
		\end{align*}
		Combining this with \eqref{Gronwall:GridpointEstimate} implies that for all $m\in\{1,2,\dots, M\}$, $n\in \{0,1,\dots, N-1\}$, $t\in [\timeGrid_n,\timeGrid_{n+1}]$, $x\in\R^d$ it holds that
		\begin{equation}\label{ApproxOfMCsum:EulerEstimate}
		\begin{split}
		&\Vert Y_t^{m,x}\Vert
		\le \Vert \affineProcess^{m,x}_{\timeGrid_n}\Vert \big[1- \tfrac{t-\timeGrid_n}{\timeGrid_{n+1}-\timeGrid_n}\big]+
		\Vert \affineProcess^{m,x}_{\timeGrid_{n+1}}\Vert \big[\tfrac{t-\timeGrid_n}{\timeGrid_{n+1}-\timeGrid_n}\big]
		\\&\le \max\!\big\{\Vert \affineProcess^{m,x}_{\timeGrid_n} \Vert,\Vert \affineProcess^{m,x}_{\timeGrid_{n+1}} \Vert\big\} \le g_{m}(x)
\le 1+|g_{m}(x)|^2
		.
		\end{split}
		\end{equation}
	This, \eqref{ApproxOfMCsum:Lipschitz}, \eqref{ApproxOfMCsumProof:EstimateDifference}, and \eqref{ApproxOfMCsumProof:EstimateGrowth} ensure that for all  $m\in\{1,2,\dots, M\}$,	 $t\in [0,T]$, $x\in\R^d$, $\omega\in\Omega$ it holds that
	\begin{equation}
	\begin{split}
	&\norm{(\functionANN (\initial))((\functionANN(\Psi_{\omega,m}))(t,x))-(\functionANN (\initial))(Y_t^{m,x}(\omega))}
	\\&\le \mathfrak{C} \big(1 + \Vert(\functionANN(\Psi_{\omega,m}))(t,x)\Vert^{\alpha} + \Vert Y_t^{m,x}(\omega) \Vert^{\alpha}\big)\Vert(\functionANN(\Psi_{\omega,m}))(t,x)-Y_t^{m,x}(\omega)\Vert
	\\&\le  \mathfrak{C} \left[1 + 6^\alpha {d}^{\nicefrac{\alpha}{2}}
	(1+|g_{m}(x,\omega)|^2)^{\alpha} + (1+|g_{m}(x,\omega)|^2)^{\alpha}\right]
\, 2\varepsilon \sqrt{d}\left(1+|g_{m}(x,\omega)|^q\right)
\!.
	\end{split}
	\end{equation}
	Combining this, \eqref{ApproxOfMCSum:AuxFunctionTwo}, and \eqref{ApproxOfMCSum:AuxFunctionOneTilde} demonstrates that for all  $m\in\{1,2,\dots, M\}$, $t\in [0,T]$, $x\in\R^d$, $\omega\in\Omega$ it holds that
		\begin{equation}\label{ApproxOfMCsum:FinalOne}
		\begin{split}
		&\norm{(\functionANN (\initial))((\functionANN(\Psi_{\omega,m}))(t,x))-(\functionANN (\initial))(Y_t^{m,x}(\omega))}
			\\&\le 2\varepsilon \mathfrak{C} \sqrt{d}  \left[1 +2 {d}^{\nicefrac{\alpha}{2}} 6^\alpha
			(1+|g_{m}(x,\omega)|^2)^{\alpha}\right]
(1+|g_{m}(x,\omega)|^q)
		\\&= 2\varepsilon \mathfrak{C} \sqrt{d}  \left[1 +2 {d}^{\nicefrac{\alpha}{2}} 6^\alpha
		|h_{m,2}(x,\omega)|^\alpha \right]
		 h_{m,q}(x,\omega).
		\end{split}
		\end{equation}
	This  and \eqref{ApproxOfMCsum:PhiSum} show that for all 	 $t\in [0,T]$, $x\in\R^d$, $\omega\in\Omega$ it holds that
	\begin{equation}\label{ApproxOfMCsum:FinalTwo}
	\begin{split}
	&\left\Vert(\functionANN(\Phi_\omega))(t,x)-\frac{1}{M}\left[\smallsum\limits_{m=1}^M (\functionANN(\initial))(Y_t^{m,x}(\omega))\right]\right\Vert
	\\&= \left\Vert\frac{1}{M}\left[\smallsum\limits_{m=1}^M (\functionANN (\initial))((\functionANN(\Psi_{\omega,m}))(t,x))\right]-\frac{1}{M}\left[\smallsum\limits_{m=1}^M (\functionANN(\initial))(Y_t^{m,x}(\omega))\right]\right\Vert
	\\&\le \frac{1}{M}\left[\smallsum\limits_{m=1}^M \norm{ (\functionANN (\initial))((\functionANN(\Psi_{\omega,m}))(t,x))-(\functionANN(\initial))(Y_t^{m,x}(\omega))} \right]
	\\&\le \frac{2\varepsilon \mathfrak{C} \sqrt{d}}{M}\bigg[\smallsum\limits_{m=1}^M   \left[1 +2 {d}^{\nicefrac{\alpha}{2}} 6^\alpha
	|h_{m,2}(x,\omega)|^\alpha \right]
	h_{m,q}(x,\omega) \bigg]\!.
	\end{split}
	\end{equation}
	Moreover, observe that \eqref{ApproxOfMCsumProof:Continuity},
	the fact that $\functionANN(\initial)$ is continuous,
	and \eqref{ApproxOfMCsum:PhiSum} ensure that
	for all $t\in[0,T]$, $x\in\R^d$ it holds that $\Omega\ni \omega\mapsto (\functionANN (\Phi_{\omega}))(t,x)\in\R^{\mathfrak{d}}$ is measurable.
	Combining this with \eqref{ApproxOfMCsum:ParamEstimate}, \eqref{ApproxOfMCsum:FinalTwo}, and the fact that  $\forall \, \omega\in\Omega \colon \functionANN (\Phi_\omega)\in C(\R^{d+1},\R^{\mathfrak{d}})$
	establishes items~\eqref{ApproxOfMCsum:Function}--\eqref{ApproxOfMCsum:Continuity}.
	This completes the proof of Proposition~\ref{Cor:ApproxOfMCSum}.
\end{proof}

\begin{lemma}\label{Lemma:LpBoundsGronwall}
	Let $N, d\in \N$, $T\in (0,\infty)$, $\alpha, c,  C, \mathcal{C} \in[0,\infty)$,  $p\in (1,\infty)$,
	let $\nu \colon \mathcal{B}([0,T]\times\R^d) \to [0,\infty)$ be a finite measure 	which  satisfies that
	\begin{equation}\label{LpBoundsGronwall:MomentBound}
	\mathcal{C}=\max\!\left\{\left[\int_{[0,T]\times\R^d}\Vert x\Vert^{\max\{4p\alpha,6p\}} \, \nu(dt,dx)\right]^{\!\nicefrac{1}{\max\{4p\alpha,6p\}}},1\right\},
	\end{equation}
	let $ ( \Omega, \mathcal{F}, \P,(\mathbb{F}_n)_{n\in\{0,1,\dots, N\}} ) $ be a filtered probability space,
	let $\mathcal{M}=(\mathcal{M}_n)_{n\in\{0,1,\dots,N\}}\colon\allowbreak \{0,1,\dots,N\}\times  \Omega\to [0,\infty)$  be an $(\mathbb{F}_n)_{n\in\{0,1,\dots, N\}}$-submartingale which satisfies for all $n\in\{0,1,\dots,N\}$ that $ \E [ |\mathcal{M}_n|^{\max\{4p\alpha,6p\}}] < \infty$,
	and let
	$h_r\colon \R^d\times \Omega\to [0,\infty)$, $r\in (0,\infty)$,   satisfy for all $r\in (0,\infty)$,
	$ x \in \R^d $ that
	\begin{equation}\label{LpBoundsGronwall:AuxFunctionOne}
	h_r(x)=1+e^{r c}\left[\Vert x\Vert + C+
	\max_{n\in\{0,1,\dots,N\}} \mathcal{M}_n\right]^{r}
	\end{equation}
	(cf.\ Definition~\ref{Def:euclideanNorm}).
	Then
	\begin{enumerate}[(i)]
		\item \label{LpBoundsGronwall:ItemOne}
	it holds for all $q,r\in (0,\infty)$ with  $ 1 < qr \leq \max\{4\alpha p,6p\}$ that
				\begin{align*}
				&\left[\int_{[0,T]\times\R^d}\E\big[\vert  h_r(x)\vert^{q}\big] \, \nu(dt,dx)\right]^{\!\nicefrac{1}{q}} \numberthis
				\\&\le 2e^{r c} \max\!\big\{2^{(\nicefrac{1}{q}) - 1},1\big\} \left[\mathcal{C}   +C+
				\tfrac{qr}{qr-1} \big|\E\big[\vert  \mathcal{M}_N\vert^{qr}\big]\big|^{\nicefrac{1}{qr}} \right]^{r}
				\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{q}}\big\}
				\end{align*}
	and
	\item \label{LpBoundsGronwall:ItemTwo} it holds that
				\begin{equation}
				\begin{split}
				&\left[\int_{[0,T]\times\R^d}\E\Big[\big\vert [h_{2}(x)]^\alpha  h_{3}(x)\big\vert^p\Big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
				\\&\le  \Big[\mathcal{C}   +C+
				\tfrac{\max\{4p\alpha,6p\}}{\max\{4p\alpha,6p\}-1} \big|\E\big[\vert  \mathcal{M}_N\vert^{\max\{4p\alpha,6p\}}\big]\big|^{\nicefrac{1}{\max\{4p\alpha,6p\}}} \Big]^{2\alpha+3}
				\\&\cdot 2^{\alpha+1}e^{(2\alpha+3)c } \max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{p}}\big\}.
				\end{split}
				\end{equation}
	\end{enumerate}
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{Lemma:LpBoundsGronwall}]
	Throughout this proof let $\mathscr{C}_q \in \R$, $q
\in (0,\max\{4p\alpha,6p\}]$, satisfy for all $q
\in (0,\max\{4p\alpha,6p\}]$ that
	\begin{equation}\label{LpBoundsGronwall:MomentBoundq}
	\mathscr{C}_q=\max\!\left\{\left[\int_{[0,T]\times\R^d}\Vert x\Vert^q \, \nu(dt,dx)\right]^{\!\nicefrac{1}{q}},1\right\}
	\end{equation}
	and let
			$g\colon \R^d\times \Omega\to [0,\infty)$ satisfy for all
			$ x \in \R^d $ that
			\begin{equation}\label{LpBoundsGronwall:AuxFunctionTwo}
			g(x)=\left[\Vert x\Vert + C+
			\max_{n\in\{0,1,\dots,N\}} \mathcal{M}_n\right]
			.
			\end{equation}
	Observe that  Doob's inequality (cf., e.g., Klenke \cite[Theorem 11.2]{Klenke14}), H\"older's inequality, the hypothesis that $\mathcal{M}$ is a submartingale, the hypothesis that  $\forall \, n\in\{0,1,\dots, N\} \colon \mathcal{M}_n\ge 0$, and  the hypothesis that  $\forall \, n\in\{0,1,\dots, N\} \colon \E [ |\mathcal{M}_n|^{\max\{4p\alpha,6p\}}] < \infty $ demonstrate that for all $q\in (1,\max\{4p\alpha,6p\}]$ it holds that
	\begin{equation}\label{LpBoundsGronwall:Doob}
	\begin{split}
	\Big|\E\Big[\max_{n\in\{0,1,\dots,N\}}\vert\mathcal{M}_n\vert^q\Big]\Big|^{\nicefrac{1}{q}}
	&\le \tfrac{q}{q-1} \big|\E\big[\vert  \mathcal{M}_N\vert^q\big]\big|^{\nicefrac{1}{q}}
	\\&\le \tfrac{q}{q-1} \big|\E\big[\vert  \mathcal{M}_N\vert^{\max\{4p\alpha,6p\}}\big]\big|^{\nicefrac{1}{{\max\{4p\alpha,6p\}}}}
	<\infty.
	\end{split}
	\end{equation}
	Moreover, note that the triangle inequality and \eqref{LpBoundsGronwall:AuxFunctionTwo}   prove that for all $q, r\in (0,\infty)$ with  $ 1 < qr \leq \max\{4\alpha p,6p\}$  it holds that
	\begin{equation}
	\begin{split}
	&\left[\int_{[0,T]\times\R^d}\E\big[\vert  g(x)\vert^{qr}\big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{qr}}
	\\&\le \left[\int_{[0,T]\times\R^d}\E\big[\Vert  x\Vert^{qr}\big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{qr}}
 +\left[\int_{[0,T]\times\R^d}\E\bigg[\Big\vert C+ \max_{n\in\{0,1,\dots,N\}} \mathcal{M}_n\Big\vert^{qr}\bigg]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{qr}}.
	\end{split}
	\end{equation}
	The triangle inequality,   \eqref{LpBoundsGronwall:MomentBoundq}, and \eqref{LpBoundsGronwall:Doob}  hence show that for all $q, r \in (0,\infty)$ with  $ 1 < qr \leq \max\{4\alpha p,6p\}$   it holds that
		\begin{equation}\label{LpBoundsGronwall:g}
		\begin{split}
		&\left[\int_{[0,T]\times\R^d}\E\big[\vert  g(x)\vert^{qr}\big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{qr}}
		\\&\le \left[\int_{[0,T]\times\R^d}\Vert x\Vert^{qr} \, \nu(dt,dx)\right]^{\!\nicefrac{1}{qr}}   +\bigg[C+
		\Big|\E\Big[\max_{n\in\{0,1,\dots,N\}}\vert  \mathcal{M}_n\vert^{qr}\Big]\Big|^{\nicefrac{1}{qr}}\bigg] [\nu([0,T]\times\R^d)]^{\nicefrac{1}{qr}}
		\\&\le \mathscr{C}_{qr}   +\left[C+
		\tfrac{qr}{qr-1} \big|\E\big[\vert  \mathcal{M}_N\vert^{qr}\big]\big|^{\nicefrac{1}{qr}}\right] [\nu([0,T]\times\R^d)]^{\nicefrac{1}{qr}}
		.
		\end{split}
		\end{equation}
	Combining this with \eqref{LpBoundsGronwall:AuxFunctionOne}, \eqref{LpBoundsGronwall:AuxFunctionTwo}, and the fact that $\forall \, a, b \in  [0, \infty)$, $ q \in (0, \infty) \colon (a+b)^q \leq 2^{\max\{q-1, 0\}} (a^q + b^q)$ ensures that for all  $q, r \in (0,\infty)$ with  $ 1 < qr \leq \max\{4\alpha p,6p\}$ it holds that
		\begin{equation}\label{LpBoundsGronwall:hOne}
		\begin{split}
		&\left[\int_{[0,T]\times\R^d}\E\big[\vert  h_r(x)\vert^{q}\big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{q}}
		\\&\le \max\!\big\{2^{(\nicefrac{1}{q}) - 1},1\big\}  \left[\int_{[0,T]\times\R^d}\indicator{[0,T]\times\R^d}(t,x)\, \nu(dt,dx)\right]^{\!\nicefrac{1}{q}}\\
		&   +e^{rc} \max\!\big\{2^{(\nicefrac{1}{q}) - 1},1\big\} \left[\int_{[0,T]\times\R^d}\E\big[\vert  g(x)\vert^{rq}\big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{q}}
		\\&\le \max\!\big\{2^{(\nicefrac{1}{q}) - 1},1\big\} [\nu([0,T]\times\R^d)]^{\nicefrac{1}{q}}\\
& +e^{r c} \max\!\big\{2^{(\nicefrac{1}{q}) - 1},1\big\}\left[\mathscr{C}_{qr}   +\left[C+
		\tfrac{qr}{qr-1} \big|\E\big[\vert  \mathcal{M}_N\vert^{qr}\big]\big|^{\!\nicefrac{1}{qr}}\right] [\nu([0,T]\times\R^d)]^{\nicefrac{1}{qr}}\right]^{r}.
		\end{split}
		\end{equation}
	In addition, observe that  \eqref{LpBoundsGronwall:MomentBound} and H\"older's inequality show that for all  $q, r \in (0,\infty)$ with  $ 1 < qr \leq \max\{4\alpha p,6p\}$  it holds that
	\begin{equation}
	\begin{split}
			&\left[\int_{[0,T]\times\R^d}\Vert x\Vert^{qr} \, \nu(dt,dx)\right]^{\!\nicefrac{1}{qr}}
			\\&\le \left[\int_{[0,T]\times\R^d}\Vert x\Vert^{\max\{4\alpha p,6p\}} \, \nu(dt,dx)\right]^{\!\nicefrac{1}{\max\{4\alpha p,6p\}}} [\nu([0,T]\times\R^d)]^{[\frac{1}{qr}-\frac{1}{\max\{4\alpha p,6p\}}]}
						\\&\le \mathcal{C}
						\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{qr}}\big\}.
	\end{split}
	\end{equation}
	This, the fact that $\mathcal{C} \geq 1$, and  \eqref{LpBoundsGronwall:MomentBoundq} prove that
	 for all  $q, r \in (0,\infty)$ with  $ 1 < qr \leq \max\{4\alpha p,6p\}$  it holds that
	\begin{equation}
	\begin{split}
	\mathscr{C}_{qr} \le \mathcal{C}
	\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{qr}}\big\}.
	\end{split}
	\end{equation}
Combining this with \eqref{LpBoundsGronwall:hOne} implies that for all $q, r \in (0,\infty)$ with  $ 1 < qr \leq \max\{4\alpha p,6p\}$   it holds that
		\begin{equation}
		\begin{split}
		&\left[\int_{[0,T]\times\R^d}\E\big[\vert  h_r(x)\vert^{q}\big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{q}}
		\\&\le \max\!\big\{2^{(\nicefrac{1}{q}) - 1},1\big\} [\nu([0,T]\times\R^d)]^{\nicefrac{1}{q}}\\
&  +e^{r c} \max\!\big\{2^{(\nicefrac{1}{q}) - 1},1\big\} \left[\mathcal{C}   +C+
		\tfrac{qr}{qr-1} \big|\E\big[\vert  \mathcal{M}_N\vert^{qr}\big]\big|^{\nicefrac{1}{qr}} \right]^{r}
		\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{q}}\big\}.
		\end{split}
		\end{equation}
	Therefore, we obtain that for all $q, r \in (0,\infty)$ with  $ 1 < qr \leq \max\{4\alpha p,6p\}$  it holds that
				\begin{equation}\label{LpBoundsGronwall:h}
				\begin{split}
				&\left[\int_{[0,T]\times\R^d}\E\big[\vert  h_r(x)\vert^{q}\big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{q}}
				\\&\le 2e^{r c} \max\!\big\{2^{(\nicefrac{1}{q}) - 1},1\big\} \left[\mathcal{C}   +C+
				\tfrac{qr}{qr-1} \big|\E\big[\vert  \mathcal{M}_N\vert^{qr}\big]\big|^{\nicefrac{1}{qr}} \right]^{r}
				\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{q}}\big\}.
				\end{split}
				\end{equation}
		This establishes item~\eqref{LpBoundsGronwall:ItemOne}.
	Next observe that H\"older's inequality assures that
		\begin{equation}\label{LpBoundsGronwall:itemBstart}
		\begin{split}
		&\left[\int_{[0,T]\times\R^d}\E\Big[\big\vert [h_{2}(x)]^\alpha  h_{3}(x)\big\vert^p\Big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
		\\&\le \left[\int_{[0,T]\times\R^d}\E\big[\vert h_{2}(x)\vert^{2p\alpha}  \big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{2p}}
		\left[\int_{[0,T]\times\R^d}\E\big[\vert h_{3}(x)\vert^{2p}\big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{2p}}.
		\end{split}
		\end{equation}
	Moreover, note that H\"older's inequality demonstrates that
	\begin{equation}
	\begin{split}
	&\left[\int_{[0,T]\times\R^d}\E\big[\vert h_{2}(x)\vert^{2p\alpha}  \big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{2p\alpha}}
	\\&\le \left[\int_{[0,T]\times\R^d}\E\big[\vert h_{2}(x)\vert^{\max\{2p\alpha,3p\}}  \big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{\max\{2p\alpha,3p\}}} [\nu([0,T]\times\R^d)]^{[\frac{1}{2p\alpha}-\frac{1}{\max\{2p\alpha,3p\}}]}
	\end{split}
	\end{equation}
	and
	\begin{align*}
	&\left[\int_{[0,T]\times\R^d}\E\big[\vert h_{3}(x)\vert^{2p}  \big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{2p}} \numberthis
	\\&\le \left[\int_{[0,T]\times\R^d}\E\big[\vert h_{3}(x)\vert^{\max\{(\nicefrac{4}{3})p\alpha,2p\}}  \big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{\max\{(\nicefrac{4}{3})p\alpha,2p\}}} [\nu([0,T]\times\R^d)]^{[\frac{1}{2p}-\frac{1}{\max\{(\nicefrac{4}{3})p\alpha,2p\}}]}.
	\end{align*}
	Combining this with \eqref{LpBoundsGronwall:h} implies that
\begin{align*}
	&\left[\int_{[0,T]\times\R^d}\E\big[\vert h_{2}(x)\vert^{2p\alpha}  \big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{2p\alpha}}
		\\&\le  2e^{2 c} \Big[\mathcal{C}   +C+
		\tfrac{\max\{4p\alpha,6p\}}{\max\{4p\alpha,6p\}-1} \big|\E\big[\vert  \mathcal{M}_N\vert^{\max\{4p\alpha,6p\}}\big]\big|^{\nicefrac{1}{\max\{4p\alpha,6p\}}} \Big]^{2} \numberthis
		\\&\cdot \max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{\max\{2p\alpha,3p\}}}\big\}\ [\nu([0,T]\times\R^d)]^{[\frac{1}{2p\alpha}-\frac{1}{\max\{2p\alpha,3p\}}]}
		\\&\le  2e^{2 c} \Big[\mathcal{C}   +C+
		\tfrac{\max\{4p\alpha,6p\}}{\max\{4p\alpha,6p\}-1} \big|\E\big[\vert  \mathcal{M}_N\vert^{\max\{4p\alpha,6p\}}\big]\big|^{\nicefrac{1}{\max\{4p\alpha,6p\}}} \Big]^{2}
\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{2p\alpha}}\big\}
\end{align*}
and
\begin{align*}
&\left[\int_{[0,T]\times\R^d}\E\big[\vert h_{3}(x)\vert^{2p}  \big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{2p}}
\\&\le 2e^{3 c} \Big[\mathcal{C}   +C+
\tfrac{\max\{4p\alpha,6p\}}{\max\{4p\alpha,6p\}-1} \big|\E\big[\vert  \mathcal{M}_N\vert^{\max\{4p\alpha,6p\}}\big]\big|^{\nicefrac{1}{\max\{4p\alpha,6p\}}} \Big]^{3} \numberthis
\\&\cdot \max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{\max\{(\nicefrac{4}{3})p\alpha,2p\}}}\big\} [\nu([0,T]\times\R^d)]^{[\frac{1}{2p}-\frac{1}{\max\{(\nicefrac{4}{3})p\alpha,2p\}}]}
\\&\le  2e^{3 c} \Big[\mathcal{C}   +C+
\tfrac{\max\{4p\alpha,6p\}}{\max\{4p\alpha,6p\}-1} \big|\E\big[\vert  \mathcal{M}_N\vert^{\max\{4p\alpha,6p\}}\big]\big|^{\nicefrac{1}{\max\{4p\alpha,6p\}}} \Big]^{3}
\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{2p}}\big\}.
\end{align*}
This and \eqref{LpBoundsGronwall:itemBstart} show that
\begin{equation}
\begin{split}
&\left[\int_{[0,T]\times\R^d}\E\Big[\big\vert [h_{2}(x)]^\alpha  h_{3}(x)\big\vert^p\Big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
\\&\le \left[\left[\int_{[0,T]\times\R^d}\E\big[\vert h_{2}(x)\vert^{2p\alpha}  \big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{2p\alpha}}\right]^{\!\alpha}
\left[\int_{[0,T]\times\R^d}\E\big[\vert h_{3}(x)\vert^{2p}\big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{2p}}
				\\&\le  2^{\alpha+1}e^{(2\alpha+3)c} \Big[\mathcal{C}   +C+
				\tfrac{\max\{4p\alpha,6p\}}{\max\{4p\alpha,6p\}-1} \big|\E\big[\vert  \mathcal{M}_N\vert^{\max\{4p\alpha,6p\}}\big]\big|^{\nicefrac{1}{\max\{4p\alpha,6p\}}} \Big]^{2\alpha+3}
				\\&\cdot \max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{2p}}\big\} \left[\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{2p\alpha}}\big\}\right]^\alpha.
\end{split}
\end{equation}
Hence, we obtain that
\begin{equation}
\begin{split}
&\left[\int_{[0,T]\times\R^d}\E\Big[\big\vert [h_{2}(x)]^\alpha  h_{3}(x)\big\vert^p\Big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
\\&\le 2^{\alpha+1}e^{(2\alpha+3)c} \Big[\mathcal{C}   +C+
\tfrac{\max\{4p\alpha,6p\}}{\max\{4p\alpha,6p\}-1} \big|\E\big[\vert  \mathcal{M}_N\vert^{\max\{4p\alpha,6p\}}\big]\big|^{\nicefrac{1}{\max\{4p\alpha,6p\}}} \Big]^{2\alpha+3}
\\&\cdot \max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{p}}\big\}.
\end{split}
\end{equation}
This establishes item~\eqref{LpBoundsGronwall:ItemTwo}.
	This completes the proof of Lemma~\ref{Lemma:LpBoundsGronwall}.
\end{proof}

\begin{cor}\label{Cor:MCeuler}
	Let $M,N, d,\mathfrak{d},k \in \N$, $p\in [2, \infty)$, $\alpha, c, C,\mathcal{C}, \mathfrak{C} \in[0,\infty)$, $T, \mathfrak{D} \in (0,\infty)$,  $B\in \R^{d\times k}$, $\varepsilon\in (0,1]$, $\drift, \initial \in \ANNs$ satisfy  that  $\inDimANN(\drift)=\outDimANN(\drift)= \inDimANN(\initial)=d$, $\outDimANN(\initial)=\mathfrak{d}$, and
		\begin{equation}\label{MCeuler:paramBound}
		\mathfrak{D}= 2160 [\LogBin(\eps^{-1})+4]-504,
		\end{equation}
	let $\nu \colon \mathcal{B}([0,T]\times\R^d) \to [0,\infty)$ be a finite measure which satisfies that
		\begin{equation}\label{MCeuler:MomentBound}
		\mathcal{C}=\max\!\left\{\left[\int_{[0,T]\times\R^d}\Vert x\Vert^{\max\{4p\alpha,6p\}} \, \nu(dt,dx)\right]^{\!\nicefrac{1}{\max\{4p\alpha,6p\}}},1\right\},
		\end{equation}
assume for all $x,y\in\R^d$ that $\Vert (\functionANN(\drift))(x)\Vert\le C+ c\Vert x\Vert$ and
\begin{align}
\label{MCeuler:Lipschitz}
\Vert (\functionANN(\initial)) (x) - (\functionANN(\initial)) (y)\Vert \leq \mathfrak{C} (1 + \Vert x\Vert^{\alpha} + \Vert y \Vert^{\alpha})\Vert  x-y\Vert,
\end{align}
	let $ ( \Omega, \mathcal{F}, \P, (\mathbb{F}_t)_{t\in [0,T]} ) $ be a filtered probability space which satisfies the usual conditions\footnote{Note that we say that a filtered probability space $(\Omega,\mathcal F,\P,( \mathbb{F}_t)_{t\in [0,T]})$ satisfies the usual conditions if and only if it holds for all
		$ t \in [0,T) $
		that
		$ \{ A \in \mathcal F\colon \P(A) = 0 \} \subseteq \mathbb{F}_t = (\cap_{s\in (t,T]} \mathbb{F}_s) $; cf., e.g., Liu \& R\"ockner~\cite[Definition 2.1.11]{LiuRoeckner2015SPDEs}.},
	let $ W^{  m } \colon [0,T] \times \Omega \to \R^k $, $  m \in \{1,2,\dots,M\} $,
	be standard $(\mathbb{F}_t)_{t\in [0,T]}$--Brownian motions,
	and let
	$Y^m= (Y^{m,x }_t(\omega))_{(t, x, \omega) \in [0,T] \times \R^d \times \Omega} \colon\allowbreak [0,T]\times \R^d\times\Omega \to \R^d $, $m\in\{1,2,\dots,\allowbreak M\}$,
satisfy for all
	$m\in\{1,2,\dots,\allowbreak M\}$,
	$ x \in \R^d $,
	$n\in\{0,1,\dots,N-1\}$,
	$ t \in \big[\tfrac{nT}{N},\tfrac{(n+1)T}{N}\big]$
	that $\affineProcess^{m,x }_0=x$ and
	\begin{equation}
	\label{MCeuler:Y_processes}
	\begin{split}
	&\affineProcess^{m,x }_t
	=
	\affineProcess^{m,x }_{\frac{nT}{N}}+ \left(\tfrac{tN}{T}-n\right)\left[\tfrac{T}{N}(\functionANN(\drift)) (
	\affineProcess^{m,x }_{\frac{nT}{N}}
	)
	+
	B\big(W_{\frac{(n+1)T}{N}}^{m}-W_{\frac{nT}{N}}^{m}\big)\right]
	\end{split}
	\end{equation}
	(cf.\ \Cref{Def:euclideanNorm,Def:ANN,Definition:ANNrealization,Definition:Relu1}).
	Then there exists $(\Psi_{\omega})_{\omega\in\Omega}\subseteq \ANNs$ such that
	\begin{enumerate}[(i)]
		\item \label{MCeuler:Function} it holds for all   $\omega\in \Omega$ that $\functionANN (\Psi_{\omega})\in C(\R^{d+1},\R^\mathfrak{d})$,
				\item \label{MCeuler:Continuity}
				it holds  for all  $t\in [0,T]$, $x\in\R^d$ that $\Omega\ni \omega\mapsto (\functionANN (\Psi_{\omega}))(t,x)\in\R^\mathfrak{d}$
				is measurable,
		\item it holds  that
\begin{equation}\label{MCeuler:Estimate}
\begin{split}
&\left[\int_{[0,T]\times\R^d}\int_{\Omega}
\left\Vert(\functionANN(\Psi_{\omega}))(t,x)-\frac{1}{M}\left[\smallsum\limits_{m=1}^M (\functionANN(\initial))(Y_t^{m,x}(\omega))\right]\right\Vert^p
\P(d\omega) \, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
\\&\le  \big[2p\max\{C,\mathcal{C}\}\max\{T,1\}\max\{\alpha,1\}\big]^{2\alpha+3}\left[1+
\sqrt{ \operatorname{Trace}(B^*B)} \right]^{2\alpha+3}
\\&\cdot \varepsilon {d}^{\nicefrac{(\alpha+1)}{2}} \mathfrak{C}\,e^{(2\alpha+3)cT} 2^{2\alpha+4} 3^{\alpha}
\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{p}}\big\},
\end{split}
\end{equation}
		and
		\item \label{MCeuler:ItemParams}
		it holds for all  $\omega\in \Omega$ that
								\begin{equation}
								\begin{split}
								\paramANN(\Psi_\omega)
								&\le 2 M^2 \paramANN(\initial) + 9 M^2 N^6 d^{16} \big[  2 \lengthANN(\drift)
								+
								 \mathfrak{D}+(
								24
								+6\lengthANN(\drift)
								+   [4+\paramANN(\drift)]^{2})^{2}
								\big]^{2}.
								\end{split}
								\end{equation}
	\end{enumerate}
\end{cor}

\begin{proof}[Proof of Corollary~\ref{Cor:MCeuler}]
	Throughout this proof let
	$h_{m,r}\colon \R^d\times \Omega\to [0,\infty)$,  $m\in\{1,2,\dots, M\}$, $r\in \R$, satisfy for all $m\in\{1,2,\dots, M\}$, $r\in \R$,
	$ x \in \R^d$ that
	\begin{equation}\label{MCeuler:AuxFunctionTwo}
	h_{m,r}(x)=1+\Big[\Vert x\Vert + CT+
	\max_{n\in\{0,1,\dots,N\}}\big\Vert B  W_{\frac{nT}{N}}^m\big\Vert\Big]^r
	\exp(rc T),
	\end{equation}
	let $(\Psi_{\omega})_{\omega\in\Omega}\subseteq \ANNs$ satisfy that
	\begin{enumerate}[(I)]
		\item \label{MCeulerProof:Function} it holds for all  $\omega\in \Omega$  that $\functionANN (\Psi_{\omega})\in C(\R^{d+1},\R^\mathfrak{d})$,
		\item  it holds  for all  $\omega\in \Omega$,
		$ t \in [0,T]$,
		$x\in\R^d$ that
		\begin{equation}\label{MCeulerProof:FinalTwo}
		\begin{split}
		&\left\Vert(\functionANN(\Psi_{\omega}))(t,x)-\frac{1}{M}\left[\smallsum\limits_{m=1}^M (\functionANN(\initial))(Y_t^{m,x}(\omega))\right]\right\Vert
		\\&\le \frac{2\varepsilon \mathfrak{C} \sqrt{d}}{M}\bigg[\smallsum\limits_{m=1}^M   \left[1 +2 {d}^{\nicefrac{\alpha}{2}}  6^\alpha
		|h_{m,2}(x,\omega)|^\alpha \right]
		h_{m,3}(x,\omega) \bigg],
		\end{split}
		\end{equation}
		\item \label{MCeulerProof:ItemParams}
		it holds
		for all  $\omega\in \Omega$ that
						\begin{equation}
						\begin{split}
						&\paramANN(\Psi_\omega) \le 2 M^2 \paramANN(\initial) +  9 M^2 N^6 d^{16} \big[  2 \lengthANN(\drift)
						+
						 \mathfrak{D}+(
						24
						+6\lengthANN(\drift)
						+   [4+\paramANN(\drift)]^{2})^{2}
						\big]^{2},
						\end{split}
						\end{equation}
		and
		\item \label{MCeulerProof:Continuity}
		it holds
		 for all  $t\in [0,T]$, $x\in\R^d$  that $\Omega\ni \omega\mapsto (\functionANN (\Psi_{\omega}))(t,x)\in\R^\mathfrak{d}$
		is measurable
	\end{enumerate}
	(cf.\ Proposition~\ref{Cor:ApproxOfMCSum}), let
		$Z= (Z^{x,y }_t)_{(t,x,y)\in [0,T]\times \R^d\times(\R^d)^N} \colon\allowbreak [0,T]\times \R^d\times (\R^d)^N \to \R^d $
		satisfy for all
		$n\in\{0,1,\dots,N-1\}$,
		$ t \in [\tfrac{nT}{N},\tfrac{(n+1)T}{N}]$,
		$ x \in \R^d $, $y=(y_1, y_2, \dots, y_N)\in (\R^d)^N$
		that $Z^{x,y }_0=x$ and
		\begin{equation}
		\label{MCeulerProof:Z_processes}
		\begin{split}
Z^{x,y }_{t}=
		Z^{x,y }_{\frac{nT}{N}}+ \left(\tfrac{tN}{T}-n\right) \!\left[\tfrac{T}{N}(\functionANN(\drift)) \big(
		Z^{x,y }_{\frac{nT}{N}}
		\big)
		+
		y_{n+1}\right]\!,
		\end{split}
		\end{equation}
		and let $\mathcal{W}^m\colon [0,T]\times \R^d\times \Omega\to [0,T]\times \R^d\times (\R^d)^N$, $m\in\{1,2,\dots, M\}$,  satisfy for all $m\in\{1,2,\dots, M\}$, $t\in [0,T]$, $x\in\R^d$  that
		\begin{equation}\label{MCeuler:increments}
			\mathcal{W}^m(t,x)=\Big(t,x, B\big(W_{\frac{T}{N}}^{m}-W_{0}^{m}\big), B\big(W_{\frac{2T}{N}}^{m}-W_{\frac{T}{N}}^{m}\big), \ldots, B\big(W_{\frac{NT}{N}}^{m}-W_{\frac{(N-1)T}{N}}^{m}\big) \Big).
		\end{equation}
		Note that \eqref{MCeulerProof:Function}, \eqref{MCeulerProof:Continuity}, and Beck et al.~\cite[Lemma~2.4]{Kolmogorov} demonstrate that $ [0,T]\times\R^{d}\times \Omega \ni(t,x,\omega)\mapsto (\functionANN(\Psi_{\omega}))(t,x)\in \R^{\mathfrak{d}}$ is
		measurable.
In addition, observe that \eqref{MCeuler:Y_processes}, \eqref{MCeulerProof:Z_processes}, and \eqref{MCeuler:increments} ensure that for all $m\in\{1,2,\dots,M\}$, $t\in [0,T]$, $x\in\R^d$ it holds that
\begin{equation}\label{MCeuler:Y_processes:Factorization}
Y_t^{m,x}=(Z\circ \mathcal{W}^m)(t,x).
\end{equation}
Next note that Grohs et al.~\cite[Lemma 3.8]{GrohsHornungJentzen2019}
(applied with $N\is N$, $d\is d$, $\mu\is \functionANN(\drift)$, $T\is T$, $
(\{-1,0,1,\dots,N+1\} \ni n \mapsto t_n \in \R) \is (\{-1,0,1,\dots,N+1\} \ni n \mapsto \tfrac{nT}{N} \in \R)$,  $Y\is Z$ in the notation of Grohs et al.~\cite[Lemma 3.8]{GrohsHornungJentzen2019}) proves that $Z\in C([0,T]\times \R^d\times (\R^d)^N,\R^d)$.
Combining this with \eqref{MCeuler:Y_processes:Factorization} and the fact that for all $m\in\{1,2,\dots,M\}$ it holds that $\mathcal{W}^m$ is measurable shows that for all $m\in\{1,2,\dots,M\}$ it holds that $Y^m$ is measurable.
The fact that $\functionANN(\initial)\in C(\R^d,\R^{\mathfrak{d}})$ hence ensures that
\begin{equation}
	[0,T]\times \R^d\times \Omega \ni (t,x,\omega)\mapsto \frac{1}{M}\bigg[\smallsum\limits_{m=1}^M (\functionANN(\initial))(Y_t^{m,x}(\omega))\bigg]\in \R^{\mathfrak{d}}
\end{equation}
is measurable.
Combining this with \eqref{MCeulerProof:FinalTwo} and the fact that $ [0,T]\times\R^{d}\times \Omega \ni(t,x,\omega)\mapsto (\functionANN(\Psi_{\omega}))(t,x)\in \R^{\mathfrak{d}}$ is measurable proves that
		\begin{align*}
		&\left[\int_{[0,T]\times\R^d}\int_{\Omega}
		\left\Vert(\functionANN(\Psi_{\omega}))(t,x)-\frac{1}{M}\bigg[\smallsum\limits_{m=1}^M (\functionANN(\initial))(Y_t^{m,x}(\omega))\bigg]\right\Vert^p
		\P(d\omega) \, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}} \numberthis
		\\&\le \frac{2\varepsilon \mathfrak{C} \sqrt{d}}{M}
		\left[\int_{[0,T]\times\R^d}\int_{\Omega}\bigg\vert\smallsum\limits_{m=1}^M   \left[1 +2 {d}^{\nicefrac{\alpha}{2}} 6^\alpha
		|h_{m,2}(x,\omega)|^\alpha \right]
		h_{m,3}(x,\omega) \bigg\vert^p
		\,\P(d\omega) \, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}.
		\end{align*}
The triangle inequality
therefore implies that
		\begin{equation}\label{MCeulerProof:Start}
		\begin{split}
		&\left[\int_{[0,T]\times\R^d}\int_{\Omega}
		\left\Vert(\functionANN(\Psi_{\omega}))(t,x)-\frac{1}{M}\bigg[\smallsum\limits_{m=1}^M (\functionANN(\initial))(Y_t^{m,x}(\omega))\bigg]\right\Vert^p
		\P(d\omega) \, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
				\\&\le  \frac{2\varepsilon \mathfrak{C} \sqrt{d}}{M} \sum_{m=1}^M
				\left[\int_{[0,T]\times\R^d}\int_{\Omega}\vert
				h_{m,3}(x,\omega) \vert^p
				\,\P(d\omega) \, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
				\\&+\frac{4  {d}^{\nicefrac{\alpha}{2}} 6^\alpha \varepsilon \mathfrak{C} \sqrt{d}}{M} \sum_{m=1}^M
				\left[\int_{[0,T]\times\R^d}\int_{\Omega}|
				[h_{m,2}(x,\omega)]^\alpha
				h_{m,3}(x,\omega) |^p
				\,\P(d\omega) \, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}.
		\end{split}
		\end{equation}
Next note that \eqref{MCeuler:AuxFunctionTwo}, Lemma~\ref{Lemma:LpBoundsGronwall}, and the fact that for all $m\in\{1,2,\dots, M\}$ it holds that
$(\|  B W_{\frac{nT}{N}}^m\|)_{n \in \{0, 1, \ldots, N\}}$ is a nonnegative $(\mathbb{F}_{\frac{nT}{N}})_{n \in \{0, 1, \ldots, N\}}$-submartingale
 demonstrate that for all $m\in\{1,2,\dots, M\}$ it holds that
	\begin{equation}\label{MCeulerProof:H}
	\begin{split}
	&\left[\int_{[0,T]\times\R^d}\E\big[\vert  h_{m,3}(x)\vert^{p}\big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
	\\&\le 2e^{3cT} \left[\mathcal{C}  +CT+
	\tfrac{3p}{3p-1} \big|\E\big[\Vert  B W_T^m\Vert^{3p}\big]\big|^{\nicefrac{1}{3p}} \right]^{3}
	\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{p}}\big\}
	\end{split}
	\end{equation}
	and
	\begin{equation}\label{MCeulerProof:productH}
	\begin{split}
	&\left[\int_{[0,T]\times\R^d}\E\big[| [h_{m,2}(x)]^\alpha  h_{m,3}(x)|^p\big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
	\\&\le  \Big[\mathcal{C}  +CT+
	\tfrac{\max\{4p\alpha,6p\}}{\max\{4p\alpha,6p\}-1} \big|\E\big[\Vert  B W_T^m\Vert^{\max\{4p\alpha,6p\}}\big]\big|^{\nicefrac{1}{\max\{4p\alpha,6p\}}} \Big]^{2\alpha+3}
	\\&\cdot 2^{\alpha+1}e^{(2\alpha+3)cT} \max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{p}}\big\}.
	\end{split}
	\end{equation}
	Moreover, observe that
	Lemma~\ref{lem:momentsGauss},
	 the fact that for all $m\in\{1,2,\dots, M\}$ it holds that  $B W_T^m$ is a  Gaussian random variable, and  the fact that for all $m\in\{1,2,\dots, M\}$ it holds that  $ \covariance\,(B W_T^m)= T B^*B$
	ensure that  for all $m\in\{1,2,\dots, M\}$, $q\in [2,\infty)$ it holds that
	\begin{equation}
	\label{MCeulerProof:Moments}
	\begin{split}
	\tfrac{q}{q-1}\big|\E\big[\Vert  B W_T^m\Vert^{q}\big]\big|^{\nicefrac{1}{q}}
	&\leq \tfrac{q}{q-1}
	\sqrt{ \max\{1,q-1\} T \operatorname{Trace}(B^*B)}
	\\&= \tfrac{q}{q-1}
	\sqrt{ (q-1) T \operatorname{Trace}(B^*B)}
	\\&= \tfrac{q}{\sqrt{q-1}}
	\sqrt{T \operatorname{Trace}(B^*B)}
	.
	\end{split}
	\end{equation}
	Combining this with \eqref{MCeulerProof:H} and \eqref{MCeulerProof:productH} assures that
	\begin{equation}\label{MCeulerProof:Htwo}
	\begin{split}
	&\frac{1}{M} \sum_{m=1}^M\left[\int_{[0,T]\times\R^d}\E\big[\vert  h_{m,3}(x)\vert^{p}\big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
	\\&\le 2e^{3cT} \left[\mathcal{C}  +CT+
	\tfrac{3p}{\sqrt{3p-1}}
	\sqrt{T \operatorname{Trace}(B^*B)} \right]^{3}
	\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{p}}\big\}
	\end{split}
	\end{equation}
	and
	\begin{equation}\label{MCeulerProof:productHtwo}
	\begin{split}
	&\frac{1}{M} \sum_{m=1}^M\left[\int_{[0,T]\times\R^d}\E\big[\big\vert [h_{m,2}(x)]^\alpha  h_{m,3}(x)\big\vert^p\big]\, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
	\\&\le  \Big[\mathcal{C}  +CT+
	\tfrac{\max\{4p\alpha,6p\}}{\sqrt{\max\{4p\alpha,6p\}-1}}
	\sqrt{T \operatorname{Trace}(B^*B)} \Big]^{2\alpha+3}
	\\&\cdot 2^{\alpha+1}e^{(2\alpha+3)cT} \max\!\big\{1,[\nu([0,T]\times\R^d)]^{\!\nicefrac{1}{p}}\big\}.
	\end{split}
	\end{equation}
	This and \eqref{MCeulerProof:Start}	demonstrate that
\begin{equation}\label{MCeulerProof:PreFinal}
\begin{split}
&\left[\int_{[0,T]\times\R^d}\int_{\Omega}
\left\Vert(\functionANN(\Psi_{\omega}))(t,x)-\frac{1}{M}\left[\smallsum\limits_{m=1}^M (\functionANN(\initial))(Y_t^{m,x}(\omega))\right]\right\Vert^p
\P(d\omega) \, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
\\&\le  4\varepsilon \mathfrak{C} e^{3cT} \sqrt{d} \max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{p}}\big\}   \left[\mathcal{C}  +CT+
\tfrac{3p}{\sqrt{3p-1}}
\sqrt{T \operatorname{Trace}(B^*B)} \right]^{3}
\\&+ \Big[\mathcal{C}  +CT+
\tfrac{\max\{4p\alpha,6p\}}{\sqrt{\max\{4p\alpha,6p\}-1}}
\sqrt{T \operatorname{Trace}(B^*B)} \Big]^{2\alpha+3}
\\&\cdot 4\varepsilon \mathfrak{C} 6^\alpha {d}^{\nicefrac{\alpha}{2}} 2^{\alpha+1} e^{(2\alpha+3)cT} \sqrt{d} \max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{p}}\big\}.
\end{split}
\end{equation}
The fact that  $[2,\infty)\ni x\mapsto \nicefrac{x}{\sqrt{x-1}}\in\R$ is non-decreasing
hence implies that
\begin{equation}
\begin{split}
&\left[\int_{[0,T]\times\R^d}\int_{\Omega}
\left\Vert(\functionANN(\Psi_{\omega}))(t,x)-\frac{1}{M}\left[\smallsum\limits_{m=1}^M (\functionANN(\initial))(Y_t^{m,x}(\omega))\right]\right\Vert^p
\P(d\omega) \, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
\\&\le   \left[\mathcal{C}  +CT+
\tfrac{\max\{4p\alpha,6p\}}{\sqrt{\max\{4p\alpha,6p\}-1}}
\sqrt{T \operatorname{Trace}(B^*B)} \right]^{2\alpha+3}
\\&\cdot \Big[4\varepsilon \mathfrak{C} e^{3cT} \sqrt{d} +  4\varepsilon \mathfrak{C} 6^\alpha {d}^{\nicefrac{\alpha}{2}} 2^{\alpha+1} e^{(2\alpha+3)cT} \sqrt{d} \Big]
\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{p}}\big\}
\\&\le  |\!\max\{C,\mathcal{C}\}|^{2\alpha+3} |\!\max\{T,1\}|^{2\alpha+3} \left[2+
\tfrac{\max\{4p\alpha,6p\}}{\sqrt{\max\{4p\alpha,6p\}-1}}
\sqrt{ \operatorname{Trace}(B^*B)} \right]^{2\alpha+3}
\\&\cdot \varepsilon {d}^{\nicefrac{(\alpha+1)}{2}} \mathfrak{C}\,e^{(2\alpha+3) c T} \big[4  + 6^\alpha  2^{\alpha+1} 4\big]
\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{p}}\big\}.
\end{split}
\end{equation}
The fact that $\sqrt{\max\{4p\alpha,6p\}-1}\ge \sqrt{6p-1}\ge \sqrt{11}\ge 3$ therefore ensures that
\begin{equation}\label{MCeulerProof:Final}
\begin{split}
&\left[\int_{[0,T]\times\R^d}\int_{\Omega}
\left\Vert(\functionANN(\Psi_{\omega}))(t,x)-\frac{1}{M}\left[\smallsum\limits_{m=1}^M (\functionANN(\initial))(Y_t^{m,x}(\omega))\right]\right\Vert^p
\P(d\omega) \, \nu(dt,dx)\right]^{\!\nicefrac{1}{p}}
\\&\le  |\!\max\{C,\mathcal{C}\}|^{2\alpha+3} |\!\max\{T,1\}|^{2\alpha+3} \left[2+
\max\{(\nicefrac{4}{3})p\alpha,2p\}
\sqrt{ \operatorname{Trace}(B^*B)} \right]^{2\alpha+3}
\\&\cdot \varepsilon {d}^{\nicefrac{(\alpha+1)}{2}} \mathfrak{C}\,e^{(2\alpha+3)cT} \big[4+2^{2\alpha+3} 3^{\alpha}\big]
\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{p}}\big\}
\\&\le  |\!\max\{C,\mathcal{C}\}|^{2\alpha+3} |\!\max\{T,1\} |^{2\alpha+3}
[2p\max\{\alpha,1\}]^{2\alpha+3}\left[1+
\sqrt{ \operatorname{Trace}(B^*B)} \right]^{2\alpha+3}
\\&\cdot \varepsilon {d}^{\nicefrac{(\alpha+1)}{2}} \mathfrak{C}\,e^{(2\alpha+3)cT} 2^{2\alpha+4} 3^{\alpha}
\max\!\big\{1,[\nu([0,T]\times\R^d)]^{\nicefrac{1}{p}}\big\}.
\end{split}
\end{equation}
Combining this with \eqref{MCeulerProof:Function}, \eqref{MCeulerProof:ItemParams}, and \eqref{MCeulerProof:Continuity} establishes items~\eqref{MCeuler:Function}--\eqref{MCeuler:ItemParams}.
	This completes the proof of Corollary~\ref{Cor:MCeuler}.
\end{proof}

config: arxiv


TITLE: Evaluate $\int [\cos(\csc^{-1}(\tan(\sec^{-1} (\cot(\sin^{-1}(\sec(\cot^{-1}(\csc(\cos^{-1}(x))))))))))]^2 dx$
QUESTION [5 upvotes]: I was trying to evaluate the below integral:

$$\int \big[\cos(\csc^{-1}(\tan(\sec^{-1}(\cot(\sin^{-1}(\sec(\cot^{-1}(\csc(\cos^{-1}(x))))))))))\big]^2 dx$$

I managed to simplify it  to the below form:
$$\int \frac{3x^2-5}{2x^2-3}dx$$I then got to this form:
$$\frac{3x}{2}+C-\frac{1}{2}\int\frac{1}{2x^2-3}dx$$
I'm stuck at this point; could anyone show me how to proceed?

REPLY [3 votes]: Assuming your simplification is correct (I didn't check), the final step would be handled like this:
$$\int\frac{1}{ax^2 - b}dx = \frac 1b \int\frac{1}{(\sqrt{\frac{a}{b}}x)^2 - 1}dx$$
At this point, you can factor the denominator into $(\sqrt{\frac{a}{b}}x + 1)(\sqrt{\frac{a}{b}}x - 1)$ and use partial fractions.
Alternatively, you could apply the substitution $\sqrt{\frac{a}{b}}x = \cosh y$ which would involve hyperbolic trig functions, if you're comfortable with that.


TITLE: What's the relation between molecular orbitals and electron density?
QUESTION [2 upvotes]: The way molecular orbitals are drawn represent the "encapsulated" space in which the wave function has a significant amplitude. How do I obtain from this the electron density? Is there a fundamental difference been them? And why "everyone" talks about orbitals if the electron density is what actually we're interested in?

REPLY [2 votes]: The electron density is proportional to the square of the wavefunction. More precisely it's:
$$ D \propto \Psi\Psi^* $$
where $\Psi^*$ is the complex conjugate of the wavefunction. The wavefunction can be complex, but the product $\Psi\Psi^*$ is always real, which is just as well since the electrons are real too.
So a diagram of the electron density looks very like a diagram of the wavefunction, which is why people tend not to make the distinction clear.


TITLE: Finding operator norm
QUESTION [3 upvotes]: I have to solve the following problem:
Find a norm of operator $$A:L^2[-\pi,\pi]\rightarrow L^2[-\pi,\pi]$$ given with $$Af(x)=\int_{-\pi}^{\pi} \cos^2{\left(\frac{x-t}{2}\right)}f(t) \,dt.$$
I proved that $\|A\|\leq 2\pi$, by using Holder's inequality, but I'm having difficulties to determine it exactly. Any help is welcome.

REPLY [1 votes]: If you don't want to use the Fourier transform techniques suggested in the comments, here's something you can do. Recall that $L^2([-\pi, \pi])$ has an orthogonal basis consisting of the functions $1$, $\cos(mx)$ for $m\geq 1$ and $\sin(nx)$ for $n\geq 1$. You can explicitly compute what $A$ does to this orthogonal basis. For instance, if $f = \sin(nx)$, then $$(Af)(x) = \int_{-\pi}^\pi\cos^2\left(\frac{x-t}{2}\right)\sin(nt)\,dt = \begin{cases}\frac{1}{2}\pi\sin(x) & n = 1.\\
0 & n>1.\end{cases}$$
Similarly, if $f = \cos(nx)$, then  $$(Af)(x) = \int_{-\pi}^\pi\cos^2\left(\frac{x-t}{2}\right)\cos(nt)\,dt = \begin{cases}\frac{1}{2}\pi\cos(x) & n = 1.\\ 0 & n>1.\end{cases}$$
Finally, when $f \equiv 1$, you have $$(Af)(x) = \int_{-\pi}^\pi \cos^2\left(\frac{x-t}{2}\right)\,dt \equiv \pi.$$
(You should check these computations, as I could easily have made a mistake)
If these computations are indeed correct, this implies the norm of $A$ is $\|A\| = \pi$, and moreover $\|Af\| = \pi\|f\|$ when $f$ is a constant function.


TITLE: Convergence of the number of visits in a Markov Chain
QUESTION [0 upvotes]: Suppose we have an irreducible and recurrent discrete-time Markov chain with states over the finite set $\mathcal{X}$. Let $N_t (x)$ denote the number of visits to state $x$ up to time $t$. Let $\pi(x)$ denote the stationary distribution of this Markov chain, and let $X_1 \sim \pi(x)$, i.e., the Markov chain is initially at the stationary distribution. Is the following almost surely true?
$$
\lim_{T\to \infty}\frac{1}{T} N_T(x) = \pi(x)
$$
Clearly we cannot directly use strong law of large numbers (at least its standard form), since $X_1, X_2, \dots$ are not independent. Intuitively it seems obvious but I could not find a way of proving it.

REPLY [2 votes]: It's true. See for example Theorem 5.3 of this reference. The idea is that you can indeed apply the strong law of large numbers by splitting $N_T(x)/T$ into excursion times: considering how long it takes to come back to state $x$ when one has just reached state $x$. These excursion times are all independent of each other and hence the strong law applies.


TITLE: Sufficiency for being a probability density function
QUESTION [0 upvotes]: Once my professor told us in passing that a non-negative integrable (Riemann or Lebesgue) function that integrates to one over its support need not be a probability density function. I have since tried to find counterexamples where this is true, but have failed. Is there any such counterexample? Also, is there a theorem establishing sufficient conditions on a function to be a pdf?

REPLY [2 votes]: If $f:\mathbb{R}\to \mathbb{R}$ is a Borel function that satisfies $f(x)\geq 0$ for all $x\in\mathbb{R}$ and $\int_\mathbb{R} f d\lambda =1$, then
$$
P(A)=\int_A f d\lambda,\quad A\in \mathcal{B}(\mathbb{R})
$$
defines a probability meausure on $(\mathbb{R},\mathcal{B}(\mathbb{R}))$. Now let $(\Omega,\mathcal{F},P)=(\mathbb{R},\mathcal{B}(\mathbb{R}),P)$ be your probability space and define a random variable $X:\Omega \to \mathbb{R}$ by the identity mapping, i.e. $X(\omega)=\omega, \;\omega\in\Omega$. Then the distribution of $X$ is $P\circ X^{-1}=P$ which has density $f$.
So I guess you would have to look at non-measureable functions $f$ to find your counterexample.


TITLE: What is the computational complexity of the PageRank problem?
QUESTION [6 upvotes]: I was just wondering what the complexity of the PageRank problem is.  A description can be found here:  http://en.wikipedia.org/wiki/PageRank .  (I am referring to the problem that is solved by the PageRank algorithm, i.e., the question of how one should reasonably distribute "ranking" throughout a graph in a way that is consistent with the model presented in the article I've linked to.)
I've always been curious as to whether or not there is a deterministic polynomial time algorithm that can do as well as the actual PageRank algorithm that Google uses.
It's clear to me that the problem is FNP at worst, as it's easy to verify if a given "arrangement" of rankings for a series of nodes is consistent and valid.  I'm not sure beyond that, though.  Is it NP-hard?  I cannot think of which NP-complete problem would reduce to it.
Thank you,
Philip

REPLY [10 votes]: As pointed out on the wikipedia page you cite, PageRank is simply computing the eigenvector corresponding to the maximum eigenvalue of the (modified) adjacency matrix of the web graph.  Since this is simple linear algebra, it should definitely be in FP, if not much smaller classes.
Part of the issue with Google's implementation is that the web is so large that its adjacency matrix doesn't fit into the memory of any single (or even any 10,000) computers.  So although the complexity of PageRank is technically in FP, the scale at which Google is doing it doesn't really fit into the realm of traditional single-processor complexity.  To discuss the complexity of actually computing PageRank on a graph as large as the whole web, you'd at the very least have to consider some sort of distributed computation model.


text:
\begin{document}

\title
{Growth rates of amenable groups}
\author{G.~N.~Arzhantseva}
\address{Section de Math\'ematiques\\
    Universit\'e de Gen\`eve\\ CP 240, 1211 Gen\`eve 24\\
    Switzerland}
\email{Goulnara.Arjantseva@math.unige.ch}
\author{V.~S.~Guba}
\address{Department of mathematics\\
    Vologda State University\\ 6 S. Orlov St.\\ Vologda\\ 160600\\
    Russia}
\email{guba@uni-vologda.ac.ru}
\author{L.~Guyot}
\address{Section de Math\'ematiques\\
    Universit\'e de Gen\`eve\\ CP 240, 1211 Gen\`eve 24\\
    Switzerland}
\email{Luc.Guyot@math.unige.ch}

\thanks{The work has been supported by the Swiss National Science
 Foundation, No.~PP002-68627.}

\date{}

\begin{abstract}
Let $F_m$ be a free group with $m$ generators and let $R$ be its normal
subgroup such that $F_m/R$ projects onto $\zz$. We give a lower bound for the
growth rate of the group $F_m/R'$ (where $R'$ is the derived subgroup of $R$)
in terms of the length $\rho=\rho(R)$ of the shortest nontrivial relation in
$R$. It follows that the growth rate of $F_m/R'$ approaches $2m-1$ as $\rho$
approaches infinity. This implies that the growth rate of an $m$-generated
amenable group can be arbitrarily close to the maximum value $2m-1$. This
answers an open question by P. de la Harpe. In fact we prove that such groups
can be found already in the class of abelian-by-nilpotent groups as well as in
the class of finite extensions of metabelian groups.
\end{abstract}

\maketitle

\section{Introduction}

Let $G$ be a finitely generated group and $A$ a fixed finite set of
generators for ~$G$. By $\ell(g)$ we denote the {\em word length\/}
of an element $g\in G$ in the generators ~$A$, i.e.\ the length of
a shortest word in the alphabet ~$A^{\pm 1}$ representing ~$g$. Let
$B(n)$ denote the ball $\{g\in G\mid\ell(g)\le n\}$ of radius ~$n$
in ~$G$ with respect to ~$A$. The {\it growth rate\/} of the pair
$(G,A)$ is the limit
$$
\om(G,A)=\lim_{n\to\infty}\sqrt[n]{|B(n)|}.
$$
(Here $|X|$ denotes the number of elements of a finite set ~$X$.)
This limit exists due to the submultiplicativity property of the
function ~$|B(n)|$,

see for example \cite[VI.C, Proposition 56]{Harpe}. Clearly,
$\om(G,A) \ge 1$. A finitely generated group ~$G$ is said to be of
{\em exponential growth\/} if $\om(G,A)>1$ for some (which in fact
implies for any) finite generating set ~$A$. Groups with $\om(G,A)=1$
are groups of {\em subexponential\/} growth.

Let $|A|=m$. It is known that $\om(G,A)=2m-1$ if and only if
$G$ is freely generated by $A$~\cite[Section V]{GrH}.
In this case $G$ is non-amenable whenever $m>1$.

A finitely generated group which is nonamenable is necessarily of
exponential growth~\cite{Adel}. The following interesting question
is due to P.~de la Harpe.

\begin{question}\cite[VI.C~62]{Harpe}
For an integer $m\ge2$, does there exist a constant $c_m>1$, with
$c_m<2m-1$, such that $G$ is not amenable provided  $\om(G,A)\ge c_m$?
\end{question}

We show that the answer to this question is negative. Thus, given $m\ge2$,
there exists an amenable group on $m$ generators with the growth rate
as close to $2m-1$ as one likes.

It is worth noticing that for every $m\ge2$ there exists a sequence of
non-amenable groups (even containing  non-abelian free subgroups) whose
growth rates approach 1 (see~\cite{GrHa}).
\vspace{0.5ex}

For a group $H$, we denote by $H'$ its derived subgroup, that is,
$[H,H]$.
\vspace{0.5ex}

The authors thank A.\,Yu.\,Ol'shanskii for helpful comments.

\section{Results}

Let $F_m$ be a free group of rank $m$ with free basis $A$. Suppose
that $R$ is a normal subgroup of $F_m$. Assume that there is a
homomorphism $\phi$ from $F_m$ {\bf onto} the (additive) infinite cyclic
group such that $R$ is contained in its kernel (that is, $F_m/R$ has $\zz$
as a homomorphic image). By $a$ we denote a letter from $A^{\pm1}$ such that
$$
\phi(a)=\max\{\,\phi(x)\mid x\in A^{\pm1}\,\}.
$$
Clearly, $\phi(a)\ge1$.
\vspace{1ex}

Throughout the paper, we fix a homomorphism $\phi$ from $F_m$ {\bf onto}
$\zz$, the letter $a$ described above and the value $C=\phi(a)$. By $R$
we will usually denote a normal subgroup in $F_m$ that is contained in
the kernel of $\phi$.
\vspace{1ex}

A word $w$ over $A^{\pm1}$ is called {\em good\/} whenever it satisfies the
following conditions:

\begin{enumerate}
\item
$w$ is freely irreducible,
\item
the first letter of $w$ is $a$,
\item
the last letter of $w$ is not $a^{-1}$,
\item
$\phi(w)>0$.
\end{enumerate}

Let $D_k$ be the set of all good words of length $k$ and let $d_k$ be
the number of them.

\begin{lm}
\label{estim}
The number of good words of length $k\ge4$ satisfies the following inequality:
\be{goods}
d_k\ge4m(m-1)^2(2m-1)^{k-4}.
\ee
In particular, $\lim\limits_{k\to\infty}d_k^{1/k}=2m-1$.
\end{lm}

\proof
Let $\Omega$ be the set of all freely irreducible words $v$ of length $k-1$
satisfying $\phi(v)\ge0$. The number of all freely irreducible words of length
$k-1$ equals $2m(2m-1)^{k-2}$. At least half of them has a nonnegative image
under $\phi$. So $|\Omega|\ge m(2m-1)^{k-2}$.

Let $\Omega_1$ be the subset of $\Omega$ that consists of all words whose
initial letter is different from $a^{-1}$. We show that
$|\Omega_1|\ge((2m-2)/(2m-1))|\Omega|$. It is sufficient to prove that
$|\Omega_1\cap A^{\pm1}u|\ge((2m-2)/(2m-1))|\Omega\cap A^{\pm1}u|$ for any
word $u$ of length $k-2$. Suppose that $a^{-1}u$ belongs to $\Omega$.
For every letter $b$ one has $\phi(b)\ge\phi(a^{-1})$. Therefore,
$bu\in\Omega_1$ for every letter $b\ne a^{-1}$ provided $bu$ is irreducible.
There are exactly $2m-2$ ways to choose a letter $b$ with the above properties.
Hence $|\Omega_1\cap A^{\pm1}u|$ and $|\Omega\cap A^{\pm1}u|$ have $2m-2$
and $2m-1$ elements, respectively. If $a^{-1}u\notin\Omega$, then both sets
coincide.

Now let $\Omega_2$ denote the subset of $\Omega_1$ that consists of all
words whose terminal letter is different from $a^{-1}$. Analogous argument
implies that $|\Omega_2|\ge((2m-2)/(2m-1))|\Omega_1|$. It is obvious that
$av$ is good provided $v\in\Omega_2$. Therefore, the number of good words
is at least
$$
|\Omega_2|\ge\frac{2m-2}{2m-1}|\Omega_1|\ge\left(\frac{2m-2}{2m-1}\right)^2
|\Omega|\ge4m(m-1)^2(2m-1)^{k-4}.
$$
\endproof

To every word $w$ in $A^{\pm1}$ one can uniquely assign the path $p(w)$ in the
Cayley graph ${\cal C}={\cal C}(F/R,A)$ of the group $F/R$ with $A$ the
generating set. This is the path that has label $w$ and starts at the identity.
We say that a path $p$ is {\em self-avoiding\/} if it never visits the same
vertex more than once.

Let $\rho=\rho(R)$ be the length of the shortest nontrivial element in a
normal subgroup $R\le F_m$.

\begin{lm}
\label{saw}
Let $R$ be a normal subgroup in $F_m$ that is contained in the kernel of a
homomorphism $\phi$ from $F_m$ onto $\zz$. Suppose that $k\ge2$ is chosen in
such a way that the following inequality holds:
\be{rhok}
\rho(R)>Ck(2k-3)+2k-2.
\ee
Then any path in the Cayley graph ${\cal C}$ of $F_m/R$ labelled by a word of
the form $g_1g_2\cdots g_t$, where $t\ge1$, $g_s\in D_k$ for all $1\le s\le t$,
is self-avoiding.
\end{lm}

\proof
If $p$ is not self-avoiding, then let us consider its minimal subpath $q$
between two equal vertices. Clearly, $|q|\ge\rho\ge k$. Therefore, $q$ can be
represented as $q=g'g_i\cdots g_jg''$, where $g_i$, \dots, $g_j$ are in $D_k$,
the word $g'$ is a proper suffix of some word in $D_k$, the word $g''$ is a
proper prefix of some word in $D_k$. We have $|g'|,|g''|\le k-1$ so
$|g_i\ldots g_j|>Ck(2k-3)$. This implies that $j-i+1$ (the number of sections
that are completely contained in $q$) is at least $C(2k-3)+1$. Obviously,
$\phi(g')\ge-C(k-1)$ and $\phi(g'')\ge-C(k-2)$ (we recall that $g''$ starts
with $a$ if it is nonempty). On the other hand, $\phi(g_s)\ge1$ for all $s$.
Hence $\phi(g_i\cdots g_j)\ge j-i+1\ge C(2k-3)+1$ and so
$\phi(g'g_i\cdots g_jg'')\ge1$, which is obviously impossible because for every
$r\in R$ one has $\phi(r)=0$.
\endproof

\begin{thm}
\label{main}
Suppose that $R$ is a normal subgroup in the free group $F_m$ that is
contained in the kernel of a homomorphism $\phi$ from $F_m$ onto $\zz$.
Let $C$ be the maximum value of $\phi$ on the generators or their inverses.
Let $\rho=\rho(R)$ be the length of the shortest cyclically irreducible
nonempty word in $R$. If a number $k\ge4$ satisfies the inequality
\be{rhock}
\rho\ge Ck(2k-3)+2k-1,
\ee
then the growth rate of the group $F_m/R'$ w.r.t. the natural generators
is at least
$$
(2m-1)\cdot\left(\frac{4m(m-1)^2}{(2m-1)^4}\right)^{1/k}.
$$
\end{thm}

\proof
We use the following known fact \cite[Lemma 1]{DLS}. A word $w$ belongs to $R'$
if and only if, for any edge $e$, the path labelled by $w$ in the Cayley graph
of the group $F_m/R$ has the same number of occurrences of $e$ and $e^{-1}$. Hence,
if we have a number of different self-avoiding paths of length $n$ in the Cayley
graph of $F_m/R$, then they represent different elements of the group $F_m/R'$.
Moreover, all the corresponding paths in the Cayley graph of $F_m/R'$ are geodesic
so these elements have length $n$ in the group $F_m/R'$.

Suppose that the conditions of the theorem hold. For every $n$, one can
consider the set of all words of the form $g_1g_2\ldots g_n$, where all
the $g_i$'s belong to $D_k$. By Lemma \ref{saw} all these elements give
us different self-avoiding paths in the Cayley graph of $F_m/R$. Hence
for any $n$ we have at least $d_k^n$ different elements in the group $F_m/R'$
that have length $kn$. Therefore, the growth rate of $F_m/R'$ is at least
$d_k^{1/k}$. It remains to apply Lemma \ref{estim}.
\endproof

One can summarize the statement of Theorem \ref{main} as follows: if
all relations of $F_m/R$ are long enough, then the growth rate of
the group $F_m/R'$ is big enough. Notice that we cannot avoid the
assumption that $F_m/R$ projects onto $\zz$. Indeed, for any number
$\rho$, there exists a finite index normal subgroup in $F_m$ such
that all the nontrivial elements in this subgroup are longer than $\rho$.
If $R$ was such a subgroup, then $F/R'$ would be a finite extension of an
abelian group and its growth rate would be equal to $1$.

\begin{thm}
\label{chain}
Let $F_m$ be a free group of rank $m$ with free basis $A$ and
let $\phi$ be a homomorphism from $F_m$ onto $\zz$. Suppose that
$$
\ker\phi\ge R_1\ge R_2\ge\cdots\ge R_n\ge\cdots
$$
is a sequence of normal subgroups in $F_m$. If the intersection of all the
$R_n$'s is trivial, then the growth rates of the groups $F_m/R_n'$ approach
$2m-1$ as $n$ approaches infinity, that is,
$$
\lim\limits_{n\to\infty}\,\om(F_m/R_n',A)=2m-1.
$$
\end{thm}

\proof
Since the subgroups $R_n$ have trivial intersection, the lengths of their
shortest nontrivial relations approach infinity, that is,
$\rho(R_n)\to\infty$ as $n\to\infty$. Let $k(n)=\left[\sqrt{\rho(R_n)/2C}\right]$,
where $C$ is defined in terms of $\phi$ as above). Obviously, inequality
(\ref{rhock}) holds and $k(n)\to\infty$. Now Theorem \ref{main} implies that
the growth rates of the groups $F_m/R_n'$ approach $2m-1$.
\endproof

Now we show that for every $m$ there exists an amenable group with $m$
generators whose growth rate is arbitrarily close to $2m-1$.

\begin{thm}
\label{amen}
For every $m\ge1$ and for every $\varepsilon>0$, there exists an $m$-generated
amenable group $G$, which is an extension of an abelian group by a nilpotent
group such that the growth rate of $G$ is at least $2m-1-\varepsilon$.
\end{thm}

\proof
It suffices to take the lower central series in the statement of Theorem \ref{chain}
(that is, $R_1=F_m'$, $R_{i+1}=[R_i,F_m]$ for all $i\ge1$). The subgroups $R_n$ ($n\ge1$)
have trivial intersection and they are contained in $F_m'$. So all of them are
contained in the kernel of a homomorphism $\phi$ from $F_m$ onto $\zz$ (one of the
free generators of $F_m$ is sent to 1, the others are sent to 0). The groups
$G_n=F_m/R_n'$ are extensions of (free) abelian groups $R_n/R_n'$ by (free) nilpotent
groups $F_m/R_n$ so all the groups $G_n$ are amenable. The growth rates of them approach
$2m-1$.
\endproof

Notice that one can take the sequence $R_n=F_m^{(n)}$ of the $n$th derived subgroups
as well (that is, $R_1=F_m'$, $R_{i+1}=R_i'$ for all $i\ge1$). It is not hard to
show that $\rho(R_n)$ grows exponentially. The groups $F_m/R_n'=F_m/R_{n+1}$ are free
soluble. Their growth rates approach $2m-1$ very quickly. For instance, the growth rate
of the free soluble group of degree 15 with 2 generators is greater than $2.999$.

One more application of Theorem \ref{amen} can be obtained as follows. The
set of finite index subgroups of $F_m$ is countable so one can enumerate them as
$N_1$, $N_2$, \dots, $N_i$, \dots\,. Let $M_i=N_1\cap N_2\cap\cdots\cap N_i$
and let $R_i=M_i'$ for all $i\ge1$. Obviously, the subgroups $M_i$ (and thus $R_i$)
have trivial intersection. Indeed, $F_m$ is residually finite and so the subgroups
$N_i$ intersect trivially. As above, all the $R_i$'s are contained in $F_m'$ so
they are contained in the kernel of a homomorphism $\phi$ from $F_m$ onto $\zz$.
Hence the growth rates of the groups $F_m/R_i'=F_m/M_i''$ approach $2m-1$. These
groups are extensions of $M_i/M_i''$ by $F_m/M_i$, that is, they are finite
extensions of (free) metabelian groups.

Therefore, in each of the two classes of groups: 1) extensions of abelian
groups by nilpotent groups, 2) finite extensions of metabelian groups, there
exist $m$-generated groups with growth rates approaching $2m-1$.
\vspace{0.5ex}

{\bf Remark.}\ A.\,Yu.\,Ol'shan\-skii suggested the following improvement.
Let $p$ be a prime. Since $F_m$ is residually a finite $p$-group, one can get
a chain $M_1\ge M_2\ge\cdots$ of normal subgroups with trivial intersection, where
$F_m/M_i$ are finite $p$-groups. Now let $R_i=\ker\phi\cap M_i$. The group
$F_m/R_i$ is a subdirect product of $\zz$ and a finite $p$-group. In particular,
it is nilpotent. Besides, it is an extension of $\zz$ by a finite $p$-group
and an extension of a finite $p$-group by $\zz$, as well. So $F_m/R_i'$ will be
abelian-by-nilpotent and metabelian-by-finite at the same time. (In fact,
the metabelian part is an extension of an abelian group by $\zz$.) Also
one can view $F_m/R_i'$ as an extension of a virtually abelian group by $\zz$.