text:
\section{Simulations}\label{sec:simulations}
We investigate the finite sample behavior of $\dodstatnn$ in Monte Carlo simulations. To this end, we simulate the speed of convergence of $\dodstatnn$ under $H_0$ to its limit distribution (\Cref{thm:main2}) and its behavior under $H_1$. Moreover, we showcase the accuracy of the approximation by the bootstrap scheme introduced in \Cref{sec:bootsrapping the quantiles} and investigate what kind of differences are detectable in the finite sample setting using the bootstrapped DoD-test $\Phi_{DoD}^*$ defined in \eqref{eq:bootstraptest}. All simulations were performed using $\mathsf{R}$ (\citet{Rbasicversion}).
\subsection{The Hypothesis}\label{subsec:hypothesis simulation}
We begin with the simulation of the finite sample distribution under the hypothesis and consider the metric measure space $\mmspaceX$ from \Cref{ex:dod3}, where $\mathcal{X}$ denotes the unit square in $\R^2$, $d_\mathcal{X}$ the distance induced by the supremum norm and $\muX$ the uniform distribution on $\mathcal{X}$. We generate for $n=m=10,50,100,250$ two samples $\X_n$ and $\X_n'$ of $\muX$ and calculate for $\beta=0.01$ the statistic $\frac{n}{2}\dodstatnn$. For each $n$, we repeat this process 10.000 times. The finite sample distribution is then compared to a Monte Carlo sample of its theoretical limit distribution (sample size 10.000). Kernel density estimators (Gaussian kernel with bandwidth given by Silverman's rule) and Q-Q-plots are displayed in \Cref{fig: hypothesis visiualization}.

All plots highlight that the finite sample distribution of $\dodstatnn$ is already well approximated by its theoretical limit distribution for moderate sample sizes.

Moreover, for $n=10$ the quantiles of the finite sample distribution of $\dodstatnn$ are in general larger than the ones of the sample of its theoretical limit distribution, which suggests that the DoD-test will be rather conservative for small $n$. For $n\geq 50$ most quantiles of the finite sample distribution of $\dodstatnn$ match the ones of its theoretical limit distribution reasonably well.
\begin{figure}
	\includegraphics[width = \textwidth,height=0.5\textwidth]{Graphics/hypothesiscombinednospace.png}
	\caption{\textbf{Finite sample accuracy of the limit law under the hypothesis:}

	Upper row: Kernel density estimators of the sample of $\dodstatnn$ (in blue) and a Monte Carlo sample of its theoretical limit distribution (in red, sample size 10.000) for $n=10,50,100,250$ (from left to right).
Lower row: The corresponding Q-Q-plots.}
	\label{fig: hypothesis visiualization}
\end{figure}
\subsection{Alternative}
Next we investigate the behavior of the statistic $\dodstatnn$ under the alternative. To this end, we consider the metric measure spaces $\mmspaceX$ and $\mmspaceY$, where $\mmspaceX$ denotes the one as defined in \Cref{subsec:hypothesis simulation} and $\mmspaceY$ the one, where $\mathcal{Y}$ is a disc in $\R^2$ with radius 0.5, $\dY$ the distance induced by the supremum norm and $\muY$ the uniform distribution on $\mathcal{Y}$. From a testing point of view it is more interesting to compare the finite sample distribution under the alternative to the limit distribution under $H_0$ (the considered metric measure spaces are isomorphic) than to investigate the speed of convergence to the limit derived in \Cref{thm:main}. Thus, we repeat the course of action of \Cref{subsec:hypothesis simulation} for $n=m=10,50,100,250$ and $\beta=0.01$ with samples $\X_n$ and $\Y_n$ from $\muX$ and $\muY$, respectively.\\
In order to highlight the different behavior of $\dodstatnn(\X_n,\Y_n)$ in this setting, we compare its finite sample distributions to the theoretical limit distribution under the hypothesis, which has already been considered in \Cref{subsec:hypothesis simulation}.\\
The results are visualized as kernel density estimators (Gaussian kernel with bandwidth given by Silverman's rule) and Q-Q-plots in \Cref{fig: alternative visiualization}.

As $n$ grows, the kernel density estimator based on the realizations of $\dodstatnn(\X_n,\Y_n)$ shifts to the right and becomes less and less concentrated. Furthermore, it becomes more and more symmetric around its peak which matches its theoretical Gaussian limit behavior (recall \Cref{thm:main}). For $n \geq100$ we see in \Cref{fig: alternative visiualization} that the densities based on the realizations of $\dodstatnn(\X_n,\Y_n)$ differ drastically from the ones based on the Monte Carlo samples of the theoretical limit distribution under $H_0$. The corresponding Q-Q-plots underline this observation and highlight that for $n\geq50$ essentially all quantiles of the sample are drastically larger than the ones of the theoretical limit distribution. This suggests that the proposed test discriminates between these metric measure spaces with high probability already for moderate values of $n$.
\begin{figure}
	\includegraphics[width = \textwidth,height=0.45\textwidth]{Graphics/alternativecombinednospace.png}
	\caption{\textbf{The behavior of \boldmath$\dodstatnn$ under the alternative:}

Upper Row: Kernel density estimators based on the Monte Carlo sample of the theoretical limit distribution under $H_0$ (red, sample size 10.000) and the realizations of $\dodstatnn(\X_n,\Y_n)$ (blue) for $n=10,50,100,250$ (from left to right). Lower row: The corresponding Q-Q-plots.}
	\label{fig: alternative visiualization}
\end{figure}

\subsection{The Bootstrap Test}\label{subsec:bootstrap test}
We now investigate the finite sample properties of the bootstrap test $\Phi_{DoD}^*$ (defined in \eqref{eq:bootstraptest}). Therefore, we compare the metric measure space $\mmspaceV$, where $\mathcal{V}$ is the unit square, $\dV$ is the Euclidean distance and $\muV$ the uniform distribution on $\mathcal{V}$, with the spaces $\left\lbrace\left(\mathcal {W}_i,d_{\mathcal {W}_i},\mu_{\mathcal {W}_i} \right) \right\rbrace_{i=1}^5$. Here, $\mathcal {W}_i$ denotes the intersection of the unit square with a disc of radius $r_i\in\left\lbrace \sqrt{2}/2,0.65,0.6,0.55,0.5\right\rbrace$ both centered at $(0,0)$, $d_{\mathcal {W}_i}$ the Euclidean distance and $\mu_{\mathcal {W}_i}$ the uniform distribution on $\mathcal {W}_i$. In \Cref{fig:mmspacevisiualization} the sets $\mathcal{V}$ (white) and $\left\lbrace\mathcal {W}_i \right\rbrace_{i=1}^5$ (red) are displayed. It highlights the increasing similarity of the sets for growing $r_i$.\\
	\begin{figure}
	\begin{subfigure}[c]{0.19\textwidth}
		\centering\resizebox{0.8\textwidth}{!}{
			\begin{tikzpicture}
			\begin{scope}
			\clip (-0.5,-0.5) rectangle (0.5,0.5);
			\fill[red] (0,0) circle (0.7);
			\end{scope}
			\draw (-0.5,-0.5) rectangle (0.5,0.5);
			\end{tikzpicture}}
		\caption{$r_1=\frac{\sqrt{2}}{2}$}
	\end{subfigure}
	\begin{subfigure}[c]{0.19\textwidth}
		\centering\resizebox{0.8\textwidth}{!}{
			\begin{tikzpicture}
			\begin{scope}
			\clip (-0.5,-0.5) rectangle (0.5,0.5);
			\fill[red] (0,0) circle (0.65);
			\end{scope}
			\draw (-0.5,-0.5) rectangle (0.5,0.5);
			\end{tikzpicture}}
		\caption{$r_2=0.65$}
	\end{subfigure}
	\begin{subfigure}[8]{0.19\textwidth}
		\centering
		\resizebox{0.8\textwidth}{!}{
			\begin{tikzpicture}
			\begin{scope}
			\clip (-0.5,-0.5) rectangle (0.5,0.5);
			\fill[red] (0,0) circle (0.6);
			\end{scope}
			\draw (-0.5,-0.5) rectangle (0.5,0.5);
			\end{tikzpicture}}
		\caption{$r_3=0.6$}
	\end{subfigure}
	\begin{subfigure}[c]{0.19\textwidth}
		\centering
		\resizebox{0.8\textwidth}{!}{
			\begin{tikzpicture}
			\begin{scope}
			\clip (-0.5,-0.5) rectangle (0.5,0.5);
			\fill[red] (0,0) circle (0.55);
			\end{scope}
			\draw (-0.5,-0.5) rectangle (0.5,0.5);
			\end{tikzpicture}}
		\caption{$r_4=0.55$}
	\end{subfigure}
	\begin{subfigure}[c]{0.19\textwidth}
		\centering
		\resizebox{0.8\textwidth}{!}{
			\begin{tikzpicture}
			\begin{scope}
			\clip (-0.5,-0.5) rectangle (0.5,0.5);
			\fill[red] (0,0) circle (0.5);
			\end{scope}
			\draw (-0.5,-0.5) rectangle (0.5,0.5);
			\end{tikzpicture}}
		\caption{$r_5=0.5$}
	\end{subfigure}
	\caption{\textbf{Different metric measure spaces:} Comparisons of the metric measure space $\mmspaceV$ (white)

		  to the spaces $\left\lbrace\left( \mathcal {W}_i,d_{\mathcal{W}_i},\mu_{\mathcal{W}_i}\right) \right\rbrace_{i=1}^5$ (red).

	  }\label{fig:mmspacevisiualization}
\end{figure}Before we employ the bootstrap DoD-test with $\beta = 0.01$ in the present setting, we consider the bootstrap approximation proposed in \Cref{sec:bootsrapping the quantiles} in this simple setting. Therefore, we generate $n=10,50,100,250$ realizations of $\mu_\mathcal{V}$ and calculate for $n_B=n$ based on these samples 1000 times
\begin{equation*}
{\Xi}_{n_B}^*=\int_{0.01}^{0.99}\!\left(\left( {\mathbb{U}}_{n_B}^*\right) ^{-1}(t)\right)^2 \,dt\end{equation*}
as described in \Cref{sec:bootsrapping the quantiles}. We then compare for the different $n$ the obtained finite sample distributions to ones of $\dodstatnn(\V_n,\mathcal{W}_{1,n})$ (generated as described in \Cref{subsec:hypothesis simulation}).
\begin{figure}
	\includegraphics[width = \textwidth,height=0.45\textwidth]{Graphics/hypothesisbootstrapapproximationnospace.png}
	\caption{\textbf{Bootstrap under the hypothesis:} Illustration of the $n$ out of $n$ plug-in bootstrap approximation for the statistic $\dodstatnn$ based on samples from $\mmspaceV$ and $\left( \mathcal {W}_1,d_{\mathcal{W}_1},\mu_{\mathcal{W}_1}\right)$. Upper Row: Kernel density estimators of 1000 realizations of $\dodstatnn$ (in red) and its bootstrap approximation (blue, 1000 replications) for $n=10,50,100,250$ (from left to right). Lower row: The corresponding Q-Q-plots. }
	\label{fig: bootstrap visiualization}
\end{figure}
 The results are summarized as kernel density estimators (Gaussian kernel with bandwidth given by Silverman's rule) and Q-Q-plots in \Cref{fig: bootstrap visiualization}. Both, the kernel density estimators and the Q-Q-plots show that for $n\leq50$ the bootstrap quantiles are clearly larger than the empirical quantiles leading to a rather conservative procedure for smaller $n$, an effect that disappears for large $n$.

\noindent Next, we aim to apply $\Phi_{DoD}^*$ for $\beta=0.01$ at $5\%$-significance level for discriminating between $\mmspaceV$ and each of the spaces $\left( \mathcal {W}_i,d_{\mathcal{W}_i},\mu_{\mathcal{W}_i}\right)$, $i=1,\dots,5$. To this end, we bootstrap the quantile $\xi_{0.95}$ based on samples from $\muV$ as described in \Cref{sec:bootsrapping the quantiles} ($R=1000$) and then we apply the test $\Phi_{DoD}^*$, defined in \eqref{eq:bootstraptest}, with the bootstrapped quantile $\xi_{n_B,\alpha}^{(R)}$ on 1000 samples of size $n=10, 50, 100,250,500,$ $1000$ as illustrated in \Cref{sec:bootsrapping the quantiles}. The results are summarized in \Cref{tab:res}. In accordance to the previous simulations, we find that the prespecified significance level (for $r_1=\sqrt{2}/2$ the sets are equal) is approximated well for $n\geq 100$. Concerning the power of the test we observe that it is conservative for small $n$, but already for $n\geq 100$ the cases (d) and (e) (see \Cref{fig:mmspacevisiualization}) are detected reasonably well. If we choose $n=1000$, even the spaces in (c) are distinguishable, although in this case, $\mathcal {W}_3$ fills out about $94\%$ of $\mathcal{V}$. For (b), i.e.,  $r_2=0.65$, where more than $98\%$ of $\mathcal{V}$ is covered by $\mathcal {W}_4$, the power of the test falls below $0.11$.
\begin{table}
	\centering
\begin{tabular}{|c|c|c|c|c|c|}
	\hline\multicolumn{6}{|c|}{$\Phi_{DoD}^*$\rule{0pt}{10pt}} \\
	\hline\rule{0pt}{10pt}
	Sample Size & $r_1={\sqrt{2}}/{2}$ &$r_2=0.65$& $r_3=0.6$ & $r_4=0.55$ &  $r_5=0.5$  \\\hline
	10  & 0.010&0.018&0.005&0.006&0.009    \\
	50  & 0.031&0.034&0.041&0.139&0.406      \\
	100 &0.048& 0.048&0.098&0.323&0.824 \\
	250 &0.038& 0.058&0.203&0.722&1.000 \\
	500 &0.045& 0.080&0.402&0.962&1.000 \\
	1000&0.051& 0.108&0.713&1.000&1.000 \\\hline
\end{tabular}
\medskip
\caption{\textbf{Comparison of different metric measure spaces I:} The empirical power of the DoD-test $\Phi_{DoD}^*$ (1000 replications) for the comparison of the metric measure spaces represented in \Cref{fig:mmspacevisiualization} for different $n$.}\label{tab:res}
\end{table}

\noindent In order to highlight how much power we gain in the finite sample setting by carefully handling the occurring dependencies we repeat the above comparisons, but calculate $\dodstat$ only based on the independent distances, i.e., on $\lbrace \dX(X_1,X_2),\dX(X_3,X_4),\dots,\dX(X_{n-1},X_n)\rbrace $ and $\{ \dY(Y_1,Y_2),\dY(Y_3,Y_4),\dots,\dY(Y_{m-1},Y_m) \} $, instead of all available distances. In the following, the corresponding statistic is denoted as $\widehat{D}_{\beta,ind}$. From the existing theory on testing with the empirical (trimmed) Wasserstein distance \cite{MunkNonparametricvalidationsimilar1998,BarrioTestsgoodnessfit1999,BarrioAsymptoticsL2functionals2005} it is immediately clear, how to construct an asymptotic level $\alpha$ test $\Phi_{{D}_{ind}}$ based on $\widehat{D}_{\beta,ind}$. The results for comparing $\mmspaceV$ and $\left\lbrace\left(\mathcal {W}_i,d_{\mathcal {W}_i},\mu_{\mathcal {W}_i} \right) \right\rbrace_{i=1}^5$ using $\Phi_{{D}_{ind}}$ with $\beta = 0.01$ are displayed in \Cref{tab:comparison indep}. Apparently, $\Phi_{{D}_{ind}}$ keeps its prespecified significance level of $\alpha=0.05$, but develops significantly less power than $\Phi_{DoD}^*$ in the finite sample setting.

\begin{table}
	\centering
	\begin{tabular}{|c|c|c|c|c|c|}
		 \hline\multicolumn{6}{|c|}{$\Phi_{{D}_{ind}}$\rule{0pt}{10pt}} \\
		\hline 	\rule{0pt}{10pt} Sample Size & $r_1={\sqrt{2}}/{2}$ &$r_2=0.65$& $r_3=0.6$ & $r_4=0.55$&$r_5=0.5$  \\\hline

		100  &0.036  & 0.040    &0.048 	& 0.050	  & 0.177 \\
		250  & 0.041 &  0.043   & 0.043	& 0.179   & 0.799   \\
		500  & 0.051 &   0.045  &0.084	& 0.583   & 0.998 \\
		1000 & 0.043 &   0.044  &0.231	& 0.974   & 1 \\\hline
	\end{tabular}
	\medskip
	\caption{\textbf{Comparison of different metric measure spaces III:} The empirical power of the test based on $\widehat{D}_{\beta,ind}$ (1000 applications) for the comparison of the metric measure spaces represented in \Cref{fig:mmspacevisiualization}.} \label{tab:comparison indep}
\end{table}

\noindent Furthermore, we investigate the influence of $\beta$ on our results. To this end, we repeat the previous comparisons with $n=250$  and $\beta=0,0.01,0.05,0.25$. The results of the corresponding comparisons are displayed in \Cref{tab:resfordiffbeta}. It highlights that the test $\Phi_{DoD}^*$ holds its level for all $\beta$. Furthermore, we observe a decrease in power with increasing $\beta$, i.e., increasing degree of trimming. This is due to the fact that excluding too many large distances will no longer show small differences in the diameter.
\begin{table}\centering
	\begin{tabular}{|c|c|c|c|c|c|}
			\hline\multicolumn{6}{|c|}{$\Phi_{DoD}^*$\rule{0pt}{10pt}} \\
		\hline\rule{0pt}{10pt}
		$\beta$ & $r_1={\sqrt{2}}/{2}$ &$r_2=0.65$& $r_3=0.6$ & $r_4=0.55$ &  $r_5=0.5$  \\\hline
		0 & 0.048   &   0.058   &   0.228   & 0.776 & 0.997 \\
		0.01  &  0.051   &   0.065   &  0.232   &    0.736   &     0.995   \\
		0.05 & 0.049 & 0.059& 0.189 & 0.676 & 0.998 \\
		0.25 & 0.045 & 0.061 & 0.156 & 0.579&  0.979\\\hline
	\end{tabular}
	\medskip
	\caption{\textbf{The influence of $\beta$:} The empirical power of the DoD-test $\Phi_{DoD}^*$ (1000 replications) for the comparison of the metric measure spaces represented in \Cref{fig:mmspacevisiualization} for different $\beta$.}\label{tab:resfordiffbeta}
\end{table}

\noindent To conclude this subsection, we remark that in the above simulations the quantiles required for the applications of $\Phi_{DoD}^*$ were always estimated based on samples of $\muV$. Evidently, this slightly affects the results obtained, but we found that this influence is not significant.
\section{Structural Protein Comparisons}\label{sec:application}

Next, we apply the DoD-test to compare the protein structures displayed in \Cref{fig: protein visiualization}. First, we compare 5D0U with itself, in order to investigate the actual significance level of the proposed test under $H_0$ in a realistic example. Afterwards, 5D0U is compared with 5JPT and with 6FAA, respectively. However, before we can apply $\Phi_{DoD}^*$, we need to model proteins as metric measure spaces. Thus, we briefly recap some well known facts about proteins to motivate the subsequent approach. A protein is a polypeptide chain made up of amino acid residues linked together in a definite sequence. Tracing the repeated amide, $C^\alpha$ and carbonyl atoms of each amino acid residue, a so called \textit{backbone} can be identified. It is well established that the distances between the $C^\alpha$ {atoms} of the backbone contain most of the information about the protein's structure \cite{rossman1974recognition,kuntz1975approach,jones1986using,holm1993protein}. For the following comparisons, we randomly select $n = 10,50,100,250,500$ from the 650-750 $C^\alpha$ atoms of the respective proteins and assume that the corresponding coordinates are samples of unknown distributions $\left\lbrace \mu_{\X_i}\right\rbrace_{i=1}^3 $ supported on Borel sets $\mathcal{X}_i\subset\R^3$ equipped with the Euclidean distance. Furthermore, we choose $\beta=0.01$, $\alpha=0.05$ and determine for each $n$ the bootstrap quantile  $\xi_{n_B,0.95}^{(R)}$ based on a sample of size $n$ from 5D0U ($R=1000$, $n_B=n$) as illustrated in \Cref{sec:bootsrapping the quantiles}. This allows us to directly apply the test ${\Phi}_{DoD}^*$ on the drawn samples.

\noindent The results of our comparisons are summarized in \Cref{fig:protein results}. It displays the empirical significance level resp. the empirical power of the proposed method as a function of $n$.

\noindent\textbf{5D0U vs 5D0U:} In accordance with the previous simulation study this comparison (see \Cref{fig:protein results}, left) shows that $\Phi_{DoD}^*$ is conservative in this application as well.

\noindent\textbf{5D0U vs 5JPT:} We have already mentioned in \Cref{subsec:applications} that 5D0U and 5JPT are structures of the same protein extracted from two different organisms and thus highly similar (their alignment has a root mean deviation of less than 0.59 \AA). The empirical power for this comparison (\Cref{fig:protein results}, middle) stays for all $n$ below $\alpha = 0.05$ and thus the test does not discriminate between these two protein structures in accordance with our biological knowledge.

\noindent\textbf{5D0U vs 6FAA:} Although the protein structures 5D0U and 6FAA are similar at large parts (their alignment has a root mean square deviation of $0.75$ \AA), the DoD-test is able to discriminate between them with high statistical power. The empirical power (\Cref{fig:protein results}, right) is a strictly monotonically increasing function in $n$ that is greater than 0.63 for $n\geq100$ and approaches 1 for $n=500$ (recall that we use random samples of the $650-750$ $C^\alpha$ atoms).

\begin{figure}
	\centering
	\begin{subfigure}[c]{0.32\textwidth}
		\centering
		\includegraphics[width = \textwidth,height=\textwidth]{Graphics/proteincomphyppowerfortalk.pdf}
	\end{subfigure}
	\begin{subfigure}[c]{0.32\textwidth}
				\centering
		\includegraphics[width =\textwidth,height=\textwidth]{Graphics/proteincompalt1single.pdf}
	\end{subfigure}
\begin{subfigure}[c]{0.32\textwidth}
			\centering
			\includegraphics[width = \textwidth,height=\textwidth]{Graphics/proteincompaltpower.pdf}
		\end{subfigure}

	\caption{\textbf{Protein Structure Comparison:} Empirical significance level for comparing 5D0U with itself (left), empirical power for the comparison of 5D0U with 5JPT (middle) as well as the the empirical power for comparing 5D0U with 6FAA (right). 1000 repetitions of the test ${\Phi}^*_{DoD}$ have been simulated for each $n$.

}
	\label{fig:protein results}
\end{figure}

\noindent Finally, we remark that throughout this section we have always based the quantiles required for testing on samples of the protein structure 5D0U. By the definition of $\Phi_{DoD}^*$ it is evident that this influences the results. If we compared the proteins 6FAA and 5D0U using $\Phi_{DoD}^*$ with quantiles obtained by a sample of 6FAA, the results would change slightly, but remain comparable.

\subsection{Comparison to the DTM-test}\label{subsec:comparisontoBrecheteau}
In this section, we investigate how the test proposed by \citet{brecheteau2019statistical} compares to $\Phi_{DoD}^*$ for protein structure comparison. To put this method in our context, we briefly introduce the method proposed in the latter reference, comment on the underlying theoretical signature and compare the empirical power of the two tests in some simple scenarios.

\noindent We begin with the introduction of the \textit{empirical distance to measure signature}. Let $\mmspaceX$ be a metric measure space with $X_1,\dots,X_n\iid \muX$ and let $\X_n=\left\lbrace X_1,\dots,X_n\right\rbrace $. Then, the \textit{(empirical) distance to measure function} with mass parameter $\kappa={k}/{n}$ is given as
\[\delta_{\X_{n},\kappa}(x)\coloneqq\frac{1}{k}\sum_{i=1}^{k}\dX\left( X^{(i)},x\right),\]
where $X^{(i)}$ denotes the $i$'th nearest neighbor of $x$ in the sample $\X_n$ (for general $\kappa$ see \cite{brecheteau2019statistical}). For $n_S\leq n$ the \textit{empirical distance to measure signature} with mass parameter $\kappa={k}/{n}$ is then defined as
\begin{equation}\label{eq:definition distance to measure}D_{\X_{n},\kappa}\left({n_S}\right)\coloneqq\frac{1}{n_{S}}\sum_{i=1}^{n_S}\delta_{\X_{n},\kappa}(X_i),\end{equation}
which is a discrete probability distribution on $\R$. Let $\mmspaceY$ be a second metric measure space, $Y_1,\dots,Y_n\iid\muY$, let $\Y_n=\{Y_1,\dots,Y_n\}$ and let $D_{\Y_{n},\kappa}\left({n_S}\right)$ be defined analogously to \eqref{eq:definition distance to measure}. Then, given that $\frac{n_S}{n}=o(1)$, \citet{brecheteau2019statistical} constructs an asymptotic level $\alpha$ test for $H_0$ defined in \eqref{eq:nullhypothesis} based on the 1-Kantorovich distance between the respective empirical distance to measure signatures, i.e., on the test statistic
\begin{equation}\label{eq:def of Brestat}T_{n_S,\kappa}(\X_n,\Y_n)\coloneqq\mathcal{K}_1\left( D_{\X_{n},\kappa}\left({n_S}\right),D_{\Y_{n},\kappa}\left({n_S}\right)\right). \end{equation}
The corresponding test, that rejects if \eqref{eq:def of Brestat} exceeds a bootstrapped critical value $q^{DTM}_{\alpha}$, is in the following denoted as $\Phi_{DTM}$. The test statistic $T_{n_S,\kappa}$ is related to the Gromov-Kantorovich distance as follows (see \cite[Prop. 3.2]{brecheteau2019statistical})
\[T_\kappa(\X,\Y)\coloneqq\mathcal{K}_1(D_{\X,\kappa},D_{\Y,\kappa})\leq\frac{2}{\kappa}\mathcal{GK}_1 \left( \X,\Y\right). \]
Here, $D_{\X,\kappa}$ and $D_{\Y,\kappa}$ denote the true \textit{distance to measure signature} (see \cite[Sec. 1]{brecheteau2019statistical} or Section B.6 in the supplementary material \cite{supplement} for a formal definition) of $\mmspaceX$ and $\mmspaceY$, respectively.

\noindent The first step for the comparison of both methods is now to analyze how the respective signatures, the distribution of distances and the distance to measure signature, relate to each other. By the definition of $D_{\X,\kappa}$, which coincides for $n=n_S$ with \eqref{eq:definition distance to measure} for discrete metric measure spaces with $n$ points and the uniform measure, we see that $T_\kappa(\X,\Y)$ puts emphasis on local changes. This allows it to discriminate between the metric measure spaces in Figure 7 of \citet{Memoli2011} for $\kappa>1/4$, whereas $\ptruedodstat\left(\X,\Y \right)$ is always zero for this example. One the other hand, for $\kappa\leq 1/2$, $T_\kappa(\X,\Y)$ cannot distinguish between the metric measure spaces displayed in \Cref{fig:differnt metric measure spaces}, whereas $\ptruedodstat(\X,\Y)$ can become arbitrarily large, if the represented triangles are moved further apart. More precisely, $\ptruedodstat$ scales as the $p$'th power of the distance between the triangles.
\begin{figure}
	\centering
		\includegraphics[scale = 0.4]{Graphics/dreiecke.pdf}

	\caption{\textbf{Different metric measure spaces:} Representation of two different, discrete metric measure spaces that are both equipped with the respective uniform distribution. Left: Three points with the same pairwise distances (dash-dotted lines). Right: Two translated copies that are further than one side length apart.
	}
	\label{fig:differnt metric measure spaces}
\end{figure} Generally, one can show that $\ptruedodstat(\X,\Y)$ and $T_\kappa(\X,\Y)$ are related to different sequences of lower bounds for the Gromov-Kantorovich distance (see \cite[Sec. B.6]{supplement} for more details).

 \noindent The next step of the comparison of both methods consists in comparing their performance for simulated examples. To this end, we repeat the comparisons of $\mmspaceV$ with the spaces $\left\lbrace\left(\mathcal {W}_i,d_{\mathcal {W}_i},\mu_{\mathcal {W}_i} \right) \right\rbrace_{i=1}^5$ as done in \Cref{subsec:bootstrap test}. Furthermore, we simulate the empirical power of $\Phi_{DoD}^*$ in the setting of Section 4.2 of \cite{brecheteau2019statistical}. For both comparisons, we choose a significance level of $\alpha=0.05$. We begin with applying $\Phi_{DTM}$ in the setting of \Cref{subsec:bootstrap test}. By the definition of the test statistic in \eqref{eq:def of Brestat} and the representation of the metric measure spaces in \Cref{fig:mmspacevisiualization}, it is clear that this setting is difficult for the method based on $T_{n_S,\kappa}$. Furthermore, we remark that the test $\Phi_{DTM}$ is not easily applied in the finite sample setting. Although it is an asymptotic test of level $\alpha$, the parameters $n_S$ and $\kappa$ have to be chosen carefully for the test to hold its prespecified significance level for finite samples. In particular, choosing $n_S$ and $\kappa$ large violates the independence assumption underlying the results of \cite{brecheteau2019statistical}.\\ Generally, we found that the choices $\kappa\leq0.1$ and $n_S\leq n/15$ yield reasonable results which we list in  \Cref{tab: comparison brecheteau}. The results show that the DTM-test holds its significance level (for $r_1$ both spaces are the same) and develops a significant amount of power for the cases $r_4$ and $r_5$. As to be expected it struggles to discriminate $\mmspaceV$ and $\left(\mathcal {W}_3,d_{\mathcal {W}_3},\mu_{\mathcal {W}_3} \right)$, as for this task especially the large distances are important. Here, $\Phi_{DoD}^*$ clearly outperforms $\Phi_{DTM}$.

 \begin{table}
 	\centering
 	\begin{tabular}{|c|c|c|c|c|c|}\hline
 		\multicolumn{6}{|c|}{$\kappa=0.05$, $\alpha=0.05$\rule{0pt}{10pt}} \\
 		\hline 	\rule{0pt}{10pt} Sample Size & $r_1={\sqrt{2}}/{2}$ &$r_2=0.65$& $r_3=0.6$ & $r_4=0.55$&$r_5=0.5$  \\\hline

 		100  & 0.039 &     0.054	 &0.049 	&0.064& 0.096  \\
 		250  & 0.053 &  0.049   &0.070 	&0.144&  0.379   \\
 		500  & 0.065 &  0.076   &0.128	&0.361& 0.853  \\
 		1000 & 0.072 & 		0.088 &0.259	&0.740&  1\\\hline
 		\multicolumn{6}{|c|}{$\kappa=0.1$, $\alpha=0.05$\rule{0pt}{10pt}} \\
 		\hline\rule{0pt}{10pt}	Sample Size & $r_1={\sqrt{2}}/{2}$ &$r_2=0.65$& $r_3=0.6$ & $r_4=0.55$&$r_5=0.5$\\\hline
 		100 &  0.067&     0.047	 & 0.070&0.083&  0.170 \\
 		250  &   0.066  &   0.069  & 0.094&0.163& 0.533    \\
 		500  &  0.064 &   0.081  &0.147 &0.430&   0.926  \\
 		1000 & 0.064 & 	0.091	 &  0.255    &0.790&1  \\\hline
 	\end{tabular}
 	\medskip
 	\caption{\textbf{Comparison of different metric measure spaces II:} The empirical power of the test based on $T_{n_S,\kappa}$ (1000 applications) for the comparison of the metric measure spaces represented in \Cref{fig:mmspacevisiualization} for different $n$ and $\kappa$ ($n_S=n/15$).}\label{tab: comparison brecheteau}
 \end{table}

\noindent In a further example, we investigate how well $\Phi_{DoD}^*$ and $\Phi_{DTM}$ discriminate between different spiral types (see \Cref{fig:spirals}). These spirals are constructed as follows. Let $R\sim U[0,1]$ be uniformly distributed and independent of $S,S'\iid N(0,1)$. Choose a significance level of $\alpha = 0.05$ and let $\beta=0.01$. For $v=10,15,20,30,40,100$ we simulate samples of
\begin{equation}
	\label{eq:spiral creation} (R\sin(vR)+0.03S,R\cos(vR)+0.03S')\sim \mu_v
\end{equation}
and considers these to be samples from a metric measure spaces equipped with the Euclidean metric.

\begin{figure}
	\centering
	\begin{subfigure}[c]{0.32\textwidth}
		\centering
		\includegraphics[width = \textwidth,height=\textwidth]{Graphics/Spiral10.pdf}
	\end{subfigure}
	\begin{subfigure}[c]{0.32\textwidth}
	\centering
	\includegraphics[width = \textwidth,height=\textwidth]{Graphics/Spiral15.pdf}
\end{subfigure}
	\begin{subfigure}[c]{0.32\textwidth}
	\centering
	\includegraphics[width = \textwidth,height=\textwidth]{Graphics/Spiral20.pdf}
\end{subfigure}

	\caption{\textbf{Different metric measure spaces II:} Representation of samples created by \eqref{eq:spiral creation} for $v=10,15,20$ (from left to right).
	}
	\label{fig:spirals}
\end{figure}
We apply $\Phi_{DoD}^*$ with quantiles based on $\mu_v$ in order to compare $\mu_v$ with $\mu_v$ (based on different samples) and $\mu_v$ with $\mu_{10}$, $v=15,\dots,100$. The results presented in \Cref{tab:galaxy comparison} show that $\Phi_{DoD}^*$ holds its significance level and always discriminates between $\mu_{10}$ and $\mu_v$ in this setting. The reported values from \cite{brecheteau2019statistical} are also listed for the ease of readability. They show that the additional subsampling in the definition of \eqref{eq:def of Brestat} leads to a loss of power in this example. Moreover, for $\Phi_{DTM}$ the results always depend on the choice of the parameters.
\begin{table}\centering	\begin{tabular}{|c|c|c|c|c|c|}\hline
		\multicolumn{6}{|c|}{$\Phi_{DoD}^*$\rule{0pt}{10pt}} \\
			\hline\rule{0pt}{10pt}
		$v$ & 15 &20& 30&40&100  \\\hline
		\rule{0pt}{10pt} Type-I error & 0.036   & 0.051   & 0.051&0.054&0.048    \\
		\rule{0pt}{10pt}  Emp. power & 1   & 1	& 1&1&1  \\\hline
		\multicolumn{6}{|c|}{$\Phi_{DTM}$\rule{0pt}{10pt}} \\
	\hline\rule{0pt}{10pt}
$v$ & 15 &20& 30&40&100  \\\hline
\rule{0pt}{10pt} Type-I error&  0.043&0.049&0.050&0.051&0.050\\
\rule{0pt}{10pt}  Emp. power &0.525&0.884&0.987&0.977&0.985\\\hline
\end{tabular}
	\medskip
	\caption{\textbf{Spiral Comparison:} Empirical significance level and power of  $\Phi_{DoD}^*$ and  $\Phi_{DTM}$ for the comparisons the metric measure spaces represented in \Cref{fig:spirals}.}\label{tab:galaxy comparison}
\end{table}

\noindent Finally, we come to the protein structure comparison. We repeat the previous comparisons of 5D0U, 5JPT and 6FAA for a significance level $\alpha=0.05$, $n=100,250,500$, $n_S=N/5$ and $\kappa=0.05,0.1$. The results are reported in \Cref{tab:protein comparison brecheteau}. We see that also $\Phi_{DTM}$ approximately holds its significance level and is more sensitive to small local changes such as slight shifts of structural elements for small $\kappa$.

 However, the evident differences between 5D0U and 6FAA are detected much better by ${\Phi}_{DoD}^*$ (see \Cref{fig:protein results}).
\begin{table}\centering
	\begin{tabular}{|c|c|c|c|}\hline
		\multicolumn{4}{|c|}{$\kappa=0.05$, $\alpha=0.05$\rule{0pt}{10pt}} \\
		\hline\rule{0pt}{10pt}
		$n$ & 5D0U vs 5D0U &5D0U vs 5JPT& 5D0U vs 6FAA  \\\hline

		100 & 0.055   & 0.068   & 0.109    \\
		250 & 0.049   & 0.080   & 0.297     \\
		500 & 0.037   & 0.090	& 0.690  \\\hline
\multicolumn{4}{|c|}{$\kappa=0.1$, $\alpha=0.05$\rule{0pt}{10pt}} \\
		\hline\rule{0pt}{10pt}
$n$ & 5D0U vs 5D0U &5D0U vs 5JPT& 5D0U vs 6FAA  \\\hline
	100 & 0.068 &   0.061   &   0.166    \\
	250  & 0.056&   0.084   &  0.420     \\
	500 & 0.047 &   0.104   & 0.760  \\\hline
\end{tabular}
	\medskip
	\caption{\textbf{Protein Comparison II:} The empirical power of the Test proposed by \citet{brecheteau2019statistical} (1000 applications) for the comparison of proteins represented in \Cref{fig: protein visiualization} for different $n$ and $\kappa$ ($n_S=n/5$).}\label{tab:protein comparison brecheteau}
\end{table}

\subsection{Discussion}
We conclude this section with some remarks on the way we have modeled proteins as metric measure spaces in this section. The flexibility of metric measure spaces offers possible refinements which might be of interest for further investigation. For example, we have treated all $C^\alpha$ atoms as equally important, although it appears to be reasonable for some applications to put major emphasis on the cores of the proteins. Further, one could have included that the error of measurement that is in general higher for some parts of the protein by adjusting the measure on the considered space accordingly. Finally, we remark that throughout this section we have considered proteins as rigid objects and shown that this allows us to efficiently discriminate between them. However, it is well known that proteins undergo different conformational states. In such a case the usage of the Euclidean metric as done previously will most likely cause $\Phi_{DoD}^*$ to discriminate between the different conformations, as the Euclidean distance is not suited for the matching of flexible objects \cite{elad2003bending}. Depending on the application one might want to take this into account by adopting a different metric reflecting (estimates of the) corresponding intrinsic distances and to modify the theory developed. Conceptually, this is straight forward but beyond the scope of this illustrative example.


TITLE: On the Computational Complexity of Reciprocal
QUESTION [1 upvotes]: Let $N$ be a positive integer.
I would like to determine $\mathcal{O}(\frac{1}{N})$.
Let $n$ denote the number of bits in $(N)_{2}$, the binary representation of $N$.
If ordinary long division is used, am I correct in assuming that the calculation of the reciprocal of $N$ will be $\mathcal{O}(n)$? My reasoning is this---
In the case of dividing the integer $a$ by the integer $b$, the Big-O time complexity associated the decimal expansion of the fraction $\frac{a}{b}$ is (I am presuming), $len(a) \cdot len(b)$, where $len$ is the number of bits in the binary form of the integers $a$ and $b$, respectively. Hence, for $\left(\frac{1}{N}\right)_{2} = \frac{1}{n}$, $\mathcal{O}(1/N) = len1 \cdot lenN$ = $n$.
Is this reasoning correct?
Incidentally, the $N$s I have in mind are very, very large. I expect that this does not matter in terms of obtaining a big-$\mathcal{O}$ estimate, but please advise me if it does.
Many thanks.

REPLY [3 votes]: Assuming "if ordinary long division is used," computing $1/N$ in binary representation far enough "to produce the exact repetend" will take up to $\mathcal O(nN)$ bit operations.
Consider the complexity of a single step of the usual long division algorithm, carried out we presume in binary arithmetic.  We will subtract one $n$-bit operand from another, which means $n$ subtract-with-borrow operations.
We then need to bound the length of the repetend -- the repeating sequence of the binary representation of the reciprocal $1/N$ -- because that relates the number of subtraction steps required by the long division.  We cannot be sure a priori how many such steps are necessary, and one might argue that in the steps where the trial dividend bit is zero, no actual subtraction is necessary.  On the other hand we are looking for an upper bound, and furthermore checking whether zero or one is right trial dividend bit is a comparison of two $n$-bit quantities, so one may need to carry out the subtraction in order to know whether or not it is needed.
Interestingly the length $k$ of the repeating sequence is the multiplicative order of $2$ modulo the largest odd divisor of $N$.  One would generally have removed any even factor of $N$ to begin with (the trailing zeros of its binary representation, so a known quantity) and thus reducing to the case $N$ itself is odd.  We will assume so for the rest of the discussion.
This is often discussed in the context of a repeating decimal expansion here on Math.SE.  See for example this previous Question and Ross Millikan's Answer, tying the length of the repeating decimal part $k$ to the minimal positive integer such that $10^k \equiv 1 \bmod N$.
As a practical matter, although one can separately determine that length in advance, one can simply carry out the long division until a remainder of one is obtained.  That's where our division $1/N$ started, so if we reach that point again, all the steps will repeat afterwards.
Now how big can $k$ be?  As the multiplicative order of $2$ in $\mathbb Z/N\mathbb Z$ divides Euler's totient function $\varphi(N)$, that gives us an upper bound.  In fact Artin's conjecture on primitive roots implies that for infinitely many prime values of $N$, this multiplicative order $k$ will be $N-1$.  (Recall the well-known decimal case of $1/7$ having a repetend length six... because $10^6 \equiv 1 \bmod 7$.)  For more information see the Wikipedia article Full repetend prime.


TITLE: $\displaystyle \log_a(3)=q$ & $\displaystyle \log_a(2)=p$ Express $log_a 72$ in terms of p & q
QUESTION [1 upvotes]: $\displaystyle \log_a(3)=q$ & $\displaystyle \log_a(2)=p$ Express $log_a 72$ in terms of p & q
Currently I have tried nothing as I cannot even figure out where to begin a demonstration kindly will help much
Many thanks :)

REPLY [1 votes]: Observe the following rules of logarithm:
$$ \log_n ab = \log_n a + \log_n b$$
$$ \log_n a^b =b\log_n a $$
First you need to simplify the logarithms by factoring 72 into multiples of 2 and 3:
\begin{align} \log_a 72 &= \log_a (2^3 \times 3^2) \\ &= \log_a2^3 + \log_a 3^2\\ &= 3\log_a 2 + 2\log_a3\\ &= 3p + 2q\end{align}


TITLE: The answer of a recursive equation: $T(n) = T(n /\log(n)) + 1$
QUESTION [0 upvotes]: How to solve:
$$T(n) = T(n / \log(n)) + 1$$
I tried the recursive solution to reach $T(1)$, but I failed. The reason was that I could not find out after how many recursion I would reach $T(1)$.

REPLY [0 votes]: First of all, it isn't $T(1)$ you are even approaching. Rearrange the equation:
$$T\left(\frac n{\log n}\right) = T(n) - 1$$
And note that each starting value $n = x_k$ results in a sequence $$x_{k+1} = \frac{x_k}{\log x_k}$$
If we examine the function $y = \frac x{\log x}, x > 1$, then $$y' = \frac {\log x - 1}{\log^2 x}$$
The denominator is positive, so $y' < 0$ when $\log x < 1$ and $y' > 0$ when $\log x > 1$. I.e., the function is decreasing when $x < e$ and increasing when $x > e$. Its minimum will be at $e$. Note that $y(e) = e$.
So only when $x_k = e$ is $x_{k+1} = e$. Any non-$e$ starting $x_0$ will give you a sequence where $x_{k+1} \ne x_k$ for every $k$. Further because the minimum value of $y$ is $e$, we can say that no matter what $x_0 > 1, x_0 \ne e$ we start with, $x_1 > e$, and from then on the sequence decreases towards $e$, but never actually arrives at that value.  (When $x_0 \le 0, x_1$ cannot be calculated. When $0 < x_0 \le 1, x_1 \le 0$, so $x_2$ cannot be calculated.)
So you cannot calculate values for this function by knowing $T(1)$, or even $T(e)$. You never get to that point by recursion. You could calculate values if you knew every $T(x)$ for $x$ in some neighborhood of $e$. But from the recursion formula alone, the best you can say is $$\liminf_{n \to e+} T(n) = -\infty$$