Law of the logarithm for the maximum interpoint distance constructed by high-dimensional random matrix

Haibin Zhang School of Mathematics, Jilin University, Changchun 130012, China Yong Zhang School of Mathematics, Jilin University, Changchun 130012, China Xue Ding The corresponding address: [email protected] School of Mathematics, Jilin University, Changchun 130012, China

Abstract

Suppose $\left\{X_{i,k};1\leq i\leq p,1\leq k\leq n\right\}$ is an array of i.i.d. real random variables. Let $\left\{p=p_{n};n\geq 1\right\}$ be positive integers. Consider the maximum interpoint distance $M_{n}=\max_{1\leq i<j\leq p}\left\|\boldsymbol{X}_{i}-\boldsymbol{X}_{j}\right\|_{2}$ where $\boldsymbol{X}_{i}$ and $\boldsymbol{X}_{j}$ denote the $i$ -th and $j$ -th rows of the $p\times n$ matrix $\mathcal{M}_{p,n}=\left(X_{i,k}\right)_{p\times n}$ , respectively. This paper shows the laws of the logarithm for $M_{n}$ under two high-dimensional settings: the polynomial rate and the exponential rate. The proofs rely on the moderation deviation principle of the partial sum of i.i.d. random variables, the Chen–Stein Poisson approximation method and Gaussian approximation.

Keywords Maximum interpoint distance, law of the logarithm, Chen–Stein Poisson approximation, moderation deviation, Gaussian approximation

Mathematics Subject Classification: Primary 60F15; secondary 60B12.

1 Introduction

Consider a $n$ -dimensional population represented by a random vector $\boldsymbol{X}$ with mean $\boldsymbol{\mu}$ and covariance matrix $\boldsymbol{\Sigma}_{n}=\boldsymbol{I}_{n}$ , where $\boldsymbol{I}_{n}$ is the $n\times n$ identity matrix. Let $\mathcal{M}_{p,n}=\left(\boldsymbol{X}_{1},\dots,\boldsymbol{X}_{p}\right)^{\prime}=\left(X_{i,k}\right)_{1\leq i\leq p,1\leq k\leq n}$ be a $p\times n$ random matrix whose rows are an independent and identically distributed (i.i.d.) random sample of size $p$ from the population $\boldsymbol{X}$ . Write $\left\|\cdot\right\|_{2}$ for the Euclidean norm on $\mathbb{R}^{n}$ . Let

M_{n}=\max_{1\leq i<j\leq p}\left\|\boldsymbol{X}_{i}-\boldsymbol{X}_{j}\right\|_{2}

(1)

denote the maximum interpoint distance or diameter. It is clear that the resulting value of $M_{n}$ will be maximized if we choose two vectors $\boldsymbol{X}_{i}$ and $\boldsymbol{X}_{j}$ with nearly opposing directions and nearly the largest magnitudes, that is, $M_{n}$ is mainly obtained by outliers. Therefore, this makes $M_{n}$ less useful for goodness of fit tests, but may be appropriate for detecting outliers.

In the past thirty years, several authors mainly studied the limiting distribution of the largest interpoint distance $M_{n}$ . For the multidimensional situation, Matthews and Rukhin [15] assumed that $\boldsymbol{X}_{1},\dots,\boldsymbol{X}_{p}$ are independent standard normal random vectors in $\mathbb{R}^{n}$ and obtained the asymptotic distribution of $M_{n}$ . Henze and Klein [7] generalized the result of Matthews and Rukhin [15] by embedding the multivariate normal distribution into the symmetric Kotz type distribution and corrected some errors. Jammalamadaka and Janson [9] considered a more general spherically symmetric distribution and proved that $M_{n}$ with a suitable normalization asymptotically obeys a Gumbel type distribution.

If the distribution of $\boldsymbol{X}$ has an unbounded support, Henze and Lao [8] proved that the limiting distribution of $M_{n}$ is none of the three types of classical extreme-value distributions (Gumbel, Weibull and Fréchet distributions) when the distribution function $F$ of $|\boldsymbol{X}|$ satisfies $1-F(s)=s^{-\alpha}L(s)$ as $s\to\infty$ for some $\alpha>0$ and some slowly varying function $L$ . Demichel et al. [4] obtained the asymptotic behavior of $M_{n}$ when the random vector $\boldsymbol{X}$ in $\mathbb{R}^{n}$ has an elliptical distribution.

In the bounded case, Appel et al. [2] discovered if $\boldsymbol{X}$ has a uniform distribution in a planar set with unique major axis and sub- $\sqrt{x}$ decay of its boundary at the endpoints, then the limiting distribution of $M_{n}$ is a convolution of two independent Weibull distributions. Furthermore, Appel and Russo [1] investigated the case where i.i.d. points are uniformly distributed on the surface of a unit hypersphere in $\mathbb{R}^{n}$ and derived the limiting distribution of the maximum pairwise distance. Mayer and Molchanov [16] proved that the limiting distribution of $M_{n}$ is a Weibull distribution when $p$ i.i.d. points are uniformly distributed in the unit $n$ -dimensional ball. Lao [11] further assumed that $\boldsymbol{X}$ obeys some distributions in the unit square, the uniform distribution in the unit hypercube, and the uniform distribution in a regular convex polygon. Jammalamadaka and Janson [9] obtained a Gumbel limit distribution for $M_{n}$ if $\boldsymbol{X}_{1},\dots,\boldsymbol{X}_{p}$ are i.i.d. $\mathbb{R}^{n}$ -valued random vectors with a spherically symmetric distribution. Schrempp [19] relaxed the condition to that random points are in a $n$ -dimensional ellipsoid with a unique major axis. Furthermore, Schrempp [20] considered the case where random points are in a $n$ -dimensional set with a unique diameter and a smooth boundary at the poles. Tang et al. [22] assumed $\boldsymbol{X}_{1},\dots,\boldsymbol{X}_{p}$ are a random sample from a $n$ -dimensional population with independent sub-exponential components and obtained the limiting distribution of $M_{n}$ . Heiny and Kleemann [6] showed that $M_{n}$ converges weakly to a Gumbel distribution under some moment assumptions and corresponding conditions on the growth rate of $p$ .

The aforementioned papers mainly focus on the asymptotic distribution of $M_{n}$ as well as relaxing the range of $p$ relative to $n$ . The logarithmic law for $M_{n}$ remains largely unknown. In this paper, we assume that the sample size $p=p_{n}$ depends on the population dimension $n$ . We will study the strong limiting theorems for the maximum interpoint distance $M_{n}$ under two high-dimensional cases. They are the polynomial rate with $p_{n}\to\infty$ and $0<c_{1}\leq p_{n}/n^{\tau}\leq c_{2}<\infty$ and the exponential rate with $p_{n}\to\infty$ and $\log p_{n}=o(n^{\beta})$ where $c_{1}$ , $c_{2}$ , $\tau$ and $\beta$ are positive constants. Furthermore, we generalize the result for $M_{n}$ to the maximum interpoint $l^{q}$ -norm distance and perform a Monte Carlo simulation to validate our main results.

The laws of the logarithm for different statistics have previously been studied by some authors, including Jiang [10] (sample correlation matrix), Li and Rosalsky [12] (sample correlation matrix), and Ding [5] (random tensor). In addition, we refer to Li [13], Modarres [17], Modarres and Song [18], and Song and Modarres [21] for several other investigates on interpoint distance.

The plan of this paper is as follows. The main results will be stated in Section 2. In Section 3, we show some technical lemmas and prove the main results. The $l^{q}$ -norm distance and simulation results are given in Section 4.

2 Main results

Throughout this paper, let $\mathcal{M}_{p,n}=(X_{i,k})_{1\leq i\leq p,1\leq k\leq n}$ be a $p\times n$ random matrix where $\{X_{i,k};1\leq i\leq p,1\leq k\leq n\}$ are i.i.d. random variables with mean $EX_{1,1}=\mu$ and variance $\operatorname{Var}\left(X_{1,1}\right)=\sigma^{2}>0$ , let $\boldsymbol{X}_{1},\boldsymbol{X}_{2},\dots,\boldsymbol{X}_{p}$ be the $p$ rows of $\mathcal{M}_{p,n}$ . And some notations will be used in this paper. The symbol $\overset{P}{\rightarrow}$ implies convergence in probability, $\overset{d}{\rightarrow}$ means convergence in distribution, and $\to\text{a.s.}$ means almost sure convergence. For two sequences of positive numbers $\left\{x_{n}\right\}$ and $\left\{y_{n}\right\}$ , $x_{n}=O\left(y_{n}\right)$ implies $\limsup_{n\to\infty}|x_{n}/y_{n}|<\infty$ , $x_{n}=o\left(y_{n}\right)$ means $\lim_{n\to\infty}x_{n}/y_{n}=0$ . We write $x_{n}\sim y_{n}$ if $\lim_{n\to\infty}x_{n}/y_{n}=1$ , and $x_{n}\lesssim y_{n}$ if there exists a universal constant $c>0$ such that $\limsup_{n\to\infty}x_{n}/y_{n}\leq c$ . In addition, $C$ is a constant and may vary from line to line.

We first study the law of the logarithm for $M_{n}$ under the assumption that $p$ is a polynomial power of $n$ .

Theorem 2.1.

Assume

		$\displaystyle(i)\ 0<c_{1}\leq p/n^{\tau}\leq c_{2}<\infty\ \text{for}\text{ any}\ \tau>0;$
		$\displaystyle(ii)\ E\|X_{1,1}\|^{8\tau+8+\epsilon}<\infty\ \text{for}\ \text{some}\ \epsilon>0;$
		$\displaystyle(iii)\ \mathrm{Corr}(\|X_{1,1}-X_{2,1}\|^{2},\|X_{1,1}-X_{3,1}\|^{2})<1/3;$

where $c_{1}$ and $c_{2}$ are constants not depending on $n$ . Then, the following holds as $n\to\infty$ :

\frac{M_{n}^{2}-2nE|X_{1,1}|^{2}}{\sqrt{2(E|X_{1,1}|^{4}+(E|X_{1,1}|^{2})^{2})n\log{p}}}\to 2\quad\text{a.s.}

(2)

Then, we will consider that $p$ is an exponential power of $n$ .

Theorem 2.2.

Assume

		$\displaystyle(i)\ Ee^{t_{0}\|X_{1,1}\|^{2\alpha}}<\infty\ \text{for some}\ 0<\alpha\leq 1/2,\ t_{0}>0;$
		$\displaystyle(ii)\ \log{p}=o\left(n^{\frac{\alpha}{2-\alpha}}\right);$
		$\displaystyle(iii)\ \mathrm{Corr}(\|X_{1,1}-X_{2,1}\|^{2},\|X_{1,1}-X_{3,1}\|^{2})<1/3.$

Then, (2) holds as $\to\infty$ .

If $\boldsymbol{X}$ obeys $N_{n}\left(\boldsymbol{0},\boldsymbol{I}_{n}\right)$ , then $E|X_{1,1}|^{2}=1$ and $E|X_{1,1}|^{4}=3$ . Therefore, Theorems 2.1 and 2.2 have the following implication.

Corollary 2.3.

Let $\boldsymbol{X}_{1},\dots,\boldsymbol{X}_{p}$ be a random sample from the standard multivariate normal population. Assume $\log{p}=o(n^{\beta})$ for any $\beta\in(0,1/3]$ as $n\to\infty$ . Then, the following holds as $n\to\infty$ :

\frac{M_{n}^{2}-2n}{2\sqrt{2n\log{p}}}\to 2\quad\text{a.s.}

Remark 2.4.

Note that the results of Theorems 2.1 and 2.2 still hold for arbitrary mean $E\boldsymbol{X}=\mu\boldsymbol{e}$ where $\boldsymbol{e}=\left(1,\dots,1\right)^{\prime}\in\mathbb{R}^{n}$ , since $M_{n}$ is invariant under translation of the vectors $\boldsymbol{X}_{1},\dots,\boldsymbol{X}_{p}$ . Therefore, without loss of generality, we assume $\{X_{i,k};1\leq i\leq p,1\leq k\leq n\}$ are i.i.d. random variables with mean $EX_{1,1}=\mu=0$ in the proofs. By some calculations, we have

		$\displaystyle\mathrm{Corr}(\|X_{1,1}-X_{2,1}\|^{2},\|X_{1,1}-X_{3,1}\|^{2})$
	$\displaystyle=$	$\displaystyle\frac{\mathrm{Cov}(\|X_{1,1}-X_{2,1}\|^{2},\|X_{1,1}-X_{3,1}\|^{2})}{\mathrm{Var}(\|X_{1,1}-X_{2,1}\|^{2})}$
	$\displaystyle=$	$\displaystyle\frac{E\|X_{1,1}\|^{4}-(E\|X_{1,1}\|^{2})^{2}}{2(E\|X_{1,1}\|^{4}+(E\|X_{1,1}\|^{2})^{2})}.$

So the condition $\mathrm{Corr}(|X_{1,1}-X_{2,1}|^{2},|X_{1,1}-X_{3,1}|^{2})<1/3$ is equivalent to $E|X_{1,1}|^{4}<5(E|X_{1,1}|^{2})^{2}$ as shown by Tang et al. [22].

Remark 2.5.

In the proof of Theorem 2.1, distinct techniques are employed compared to earlier works like Jiang [10] and Ding [5], which utilized the moderate deviation of the partial sum of i.i.d. random variables. Instead we use the Gaussian approximation (Zaĭtsev [23], Theorem 1.1) in this paper.

3 Proofs

3.1 Some technical tools

We first show the Chen–Stein Poisson approximation method, which is a special case of Theorem 1 from Arratia et al. [3].

Lemma 3.1.

Let $I$ be an index set and $\left\{B_{\alpha};\alpha\in I\right\}$ be a set of subsets of $I$ , that is, $B_{\alpha}\subset I$ for each $\alpha\in I$ . Let $\left\{\eta_{\alpha};\alpha\in I\right\}$ be random variables. For a given $t\in\mathbb{R}$ , set $\lambda=\sum_{\alpha\in I}P\left(\eta_{\alpha}>t\right)$ . Then we have

\left\lvert P\left(\max\limits_{\alpha\in I}\eta_{\alpha}\leq t\right)-e^{-\lambda}\right\rvert\leq\left(1\wedge\lambda^{-1}\right)\left(b_{1}+b_{2}+b_{3}\right),

where

	$\displaystyle b_{1}$	$\displaystyle=\sum\limits_{\alpha\in I}\sum\limits_{\beta\in B_{\alpha}}P\left(\eta_{\alpha}>t\right)P\left(\eta_{\beta}>t\right),\quad b_{2}=\sum\limits_{\alpha\in I}\sum\limits_{\alpha\neq\beta\in B_{\alpha}}P\left(\eta_{\alpha}>t,\eta_{\beta}>t\right),$
	$\displaystyle b_{3}$	$\displaystyle=\sum_{\alpha\in I}E\lvert P\left\{\eta_{\alpha}>t\mid\sigma\left(\eta_{\beta};\beta\notin B_{\alpha}\right)\right\}-P\left(\eta_{\alpha}>t\right)\rvert,$

and $\sigma\left(\eta_{\beta};\beta\notin B_{\alpha}\right)$ is the $\sigma$ -algebra generated by $\left\{\eta_{\beta};\beta\notin B_{\alpha}\right\}$ . In particular, if $\eta_{\alpha}$ is independent of $\left\{\eta_{\beta};\beta\notin B_{\alpha}\right\}$ for each $\alpha$ , then $b_{3}=0$ .

The following lemma is about the moderate deviation of the partial sum of i.i.d. random variables (Linnik [14]).

Lemma 3.2.

Suppose that $\left\{\zeta,\zeta_{k};k=1,\dots,n\right\}$ is a sequence of i.i.d. random variables with $E\zeta=0$ and $E\zeta^{2}=1$ . Define $S_{n}=\sum_{k=1}^{n}\zeta_{k}$ .

(1) If $Ee^{t_{0}|\zeta|^{\alpha}}<\infty$ for some $0<\alpha\leq 1$ and $t_{0}>0$ . Then

\lim_{n\rightarrow\infty}\frac{1}{x_{n}^{2}}\log P\left(\frac{S_{n}}{\sqrt{n}}\geq x_{n}\right)=-\frac{1}{2}

for any $x_{n}\rightarrow\infty$ , $x_{n}=o\left(n^{\frac{\alpha}{2(2-\alpha)}}\right)$ .

(2) If $Ee^{t_{0}|\zeta|^{\alpha}}<\infty$ for some $0<\alpha\leq 1/2$ and $t_{0}>0$ . Then

\frac{P\left(\frac{S_{n}}{\sqrt{n}}\geq x_{n}\right)}{1-\Phi(x_{n})}\rightarrow 1

holds uniformly for $0\leq x_{n}\leq o\left(n^{\frac{\alpha}{2(2-\alpha)}}\right)$ .

3.2 Proof of Theorem 2.1

Now we are in a position to prove Theorem 2.1.

Proof.

Review Remark 2.4. Then, without loss of generality, we prove the theorem by assuming $\{X_{i,k};1\leq i\leq p,1\leq k\leq n\}$ are i.i.d. random variables with mean $EX_{1,1}=\mu=0$ . Recall (1). Write

\displaystyle M_{n}^{2}=\max_{1\leq i<j\leq p_{n}}\left\|\boldsymbol{X}_{i}-\boldsymbol{X}_{j}\right\|_{2}^{2}=\max_{1\leq i<j\leq p_{n}}\sum_{k=1}^{n}\left|X_{i,k}-X_{j,k}\right|^{2}.

(3)

Define

\eta_{ijk}:=\frac{\left|X_{i,k}-X_{j,k}\right|^{2}-E|X_{1,1}-X_{2,1}|^{2}}{\sqrt{\mathrm{Var}(|X_{1,1}-X_{2,1}|^{2})}}=\frac{\left|X_{i,k}-X_{j,k}\right|^{2}-2E|X_{1,1}|^{2}}{\sqrt{2(E|X_{1,1}|^{4}+(E|X_{1,1}|^{2})^{2})}}.

It is obvious that

\displaystyle E\eta_{ijk}=0\quad\text{and}\quad\text{Var}\left(\eta_{ijk}\right)=1

for each $k$ . Then, we find that

\max_{1\leq i<j\leq p_{n}}\sum_{k=1}^{n}\eta_{ijk}=\frac{M_{n}^{2}-2nE|X_{1,1}|^{2}}{\sqrt{2(E|X_{1,1}|^{4}+(E|X_{1,1}|^{2})^{2})}}.

(4)

Define

\hat{\eta}_{ijk}:=\eta_{ijk}I_{\{|\eta_{ijk}|\leq n^{s}\}}-E(\eta_{ijk}I_{\{|\eta_{ijk}|\leq n^{s}\}}),

(5)

where $0<s<1/2$ . To prove Theorem 2.1, it is sufficient to show that

\limsup_{n\to\infty}\frac{\max_{1\leq i<j\leq p_{n}}\sum_{k=1}^{n}\hat{\eta}_{ijk}}{\sqrt{n\log{p_{n}}}}\leq 2\quad\text{a.s.},

(6)

\liminf_{n\to\infty}\frac{\max_{1\leq i<j\leq p_{n}}\sum_{k=1}^{n}\hat{\eta}_{ijk}}{\sqrt{n\log{p_{n}}}}\geq 2\quad\text{a.s.}

(7)

and

\lim_{n\to\infty}\frac{\max_{1\leq i<j\leq p_{n}}\left|\sum_{k=1}^{n}\left(\eta_{ijk}-\hat{\eta}_{ijk}\right)\right|}{\sqrt{n\log{p_{n}}}}=0\quad\text{a.s.}

(8)

We will complete the proof with three steps.

Step 1: proof of (6). Given $\varepsilon\in(0,1)$ , set $m_{\tau,\varepsilon}=2/(\tau\varepsilon)$ . For any integer $m>m_{\tau,\varepsilon}$ , we have

	$\displaystyle\max_{n^{m}<l\leq(n+1)^{m}}\max_{1\leq i<j\leq p_{l}}\sum_{k=1}^{l}\hat{\eta}_{ijk}\leq$	$\displaystyle\max_{1\leq i<j\leq p_{(n+1)^{m}}}\max_{n^{m}<l\leq(n+1)^{m}}\sum_{k=1}^{l}\hat{\eta}_{ijk}$		(9)
	$\displaystyle\leq$	$\displaystyle\max_{1\leq i<j\leq p_{(n+1)^{m}}}\sum_{k=1}^{n^{m}}\hat{\eta}_{ijk}+\Psi_{n^{m}},$		(9)

where

	$\displaystyle\Psi_{n^{m}}$	$\displaystyle=\max_{1\leq i<j\leq p_{(n+1)^{m}}}\max_{n^{m}<l\leq(n+1)^{m}}\left\|\sum_{k=1}^{l}\hat{\eta}_{ijk}-\sum_{k=1}^{n^{m}}\hat{\eta}_{ijk}\right\|$		(10)
		$\displaystyle=\max_{1\leq i<j\leq p_{(n+1)^{m}}}\max_{1\leq h<(n+1)^{m}-n^{m}}\left\|\sum_{k=1}^{h}\hat{\eta}_{ijk}\right\|.$		(10)

Set $c_{n1}=\sqrt{\left(4+\varepsilon\right)\log{p_{n^{m}}}}$ and $\delta_{n1}=1/(\log{p_{n^{m}}})$ . Then, we have

\displaystyle P\left(\max_{1\leq i<j\leq p_{(n+1)^{m}}}\sum_{k=1}^{n^{m}}\hat{\eta}_{ijk}>\sqrt{\left(4+\varepsilon\right)n^{m}\log{p_{n^{m}}}}\right)\leq p_{(n+1)^{m}}^{2}\cdot P\left(\frac{1}{\sqrt{n^{m}}}\sum_{k=1}^{n^{m}}\hat{\eta}_{12k}>c_{n1}\right).

Note that $|\hat{\eta}_{ijk}|\leq n^{s}$ . By Theorem 1.1 from Zaĭtsev [23], there exists a random variable $\xi\sim N(0,\text{Var}(\hat{\eta}_{ijk}))$ such that

P\left(\frac{1}{\sqrt{n^{m}}}\sum_{k=1}^{n^{m}}\hat{\eta}_{12k}>c_{n1}\right)\geq P\left(\xi>c_{n1}+\delta_{n1}\right)-C\text{exp}\left(-C\frac{\sqrt{n^{m}}\delta_{n1}}{n^{sm}}\right),

(11)

P\left(\frac{1}{\sqrt{n^{m}}}\sum_{k=1}^{n^{m}}\hat{\eta}_{12k}>c_{n1}\right)\leq P\left(\xi>c_{n1}-\delta_{n1}\right)+C\text{exp}\left(-C\frac{\sqrt{n^{m}}\delta_{n1}}{n^{sm}}\right).

(12)

For the exponential term, we have

p_{(n+1)^{m}}^{2}\cdot\text{exp}\left(-C\frac{\sqrt{n^{m}}\delta_{n1}}{n^{sm}}\right)\leq\text{exp}\left(2m\tau C\log{(n+1)}-\frac{Cn^{(m-2sm)/2}}{\log{p_{n^{m}}}}\right)

(13)

as $n\to\infty$ . By the formula that $\lim_{x\to\infty}P\left(N\left(0,1\right)\geq x\right)=\frac{1}{\sqrt{2\pi}x}e^{-x^{2}/2}$ , we get

	$\displaystyle~{}p_{(n+1)^{m}}^{2}\cdot P\left(\xi>c_{n1}\pm\delta_{n1}\right)$	(14)
$\displaystyle\leq$	$\displaystyle~{}p_{(n+1)^{m}}^{2}\cdot P\left(\frac{\xi}{\sqrt{\text{Var}(\hat{\eta}_{ijk})}}>c_{n1}\pm\delta_{n1}\right)$
$\displaystyle\sim$	$\displaystyle~{}p_{(n+1)^{m}}^{2}\cdot\left[1-\Phi\left(c_{n1}\pm\delta_{n1}\right)\right]$
$\displaystyle\sim$	$\displaystyle~{}\frac{p_{(n+1)^{m}}^{2}}{\sqrt{2\pi}\left(c_{n1}\pm\delta_{n1}\right)}e^{-\frac{\left(c_{n1}\pm\delta_{n1}\right)^{2}}{2}}$
$\displaystyle\sim$	$\displaystyle~{}\frac{p_{(n+1)^{m}}^{2}}{\sqrt{2\pi}c_{n1}}e^{-\frac{c_{n1}^{2}}{2}}=o\left(\frac{1}{n^{m\tau\varepsilon/2}}\right)$

as $n\to\infty$ . We use the fact that $\text{Var}(\hat{\eta}_{ijk})\leq\text{Var}(\eta_{ijk})=1$ in the above inequality. By (11)–(14), we can obtain

\sum_{n=1}^{\infty}P\left(\max_{1\leq i<j\leq p_{(n+1)^{m}}}\sum_{k=1}^{n^{m}}\hat{\eta}_{ijk}>\sqrt{\left(4+\varepsilon\right)n^{m}\log{p_{n^{m}}}}\right)<\infty

as $n\to\infty$ since $m>m_{\varepsilon}$ . By the Borel–Cantelli lemma, we arrive at

\limsup_{n\to\infty}\frac{\max_{1\leq i<j\leq p_{(n+1)^{m}}}\sum_{k=1}^{n^{m}}\hat{\eta}_{ijk}}{\sqrt{n^{m}\log{p_{n^{m}}}}}\leq\sqrt{4+\varepsilon}\quad\text{a.s.}

(15)

Trivially, $\frac{\varepsilon}{2}\sqrt{n^{m}\log{p_{n^{m}}}}>\sqrt{\left(4+\varepsilon\right)((n+1)^{m}-n^{m})\log{p_{n^{m}}}}$ due to $0<c_{1}\leq p/n^{\tau}\leq c_{2}<\infty$ for any $\tau>0$ as $n$ is sufficiently large. By Markov inequality, we have

		$\displaystyle\min_{1\leq h<(n+1)^{m}-n^{m}}P\left(\left\|\sum_{k=1}^{(n+1)^{m}-n^{m}}\hat{\eta}_{12k}-\sum_{k=1}^{h}\hat{\eta}_{12k}\right\|\leq\frac{\varepsilon}{2}\sqrt{n^{m}\log{p_{n^{m}}}}\right)$
	$\displaystyle=$	$\displaystyle 1-\max_{1\leq h<(n+1)^{m}-n^{m}}P\left(\left\|\sum_{k=1}^{(n+1)^{m}-n^{m}}\hat{\eta}_{12k}-\sum_{k=1}^{h}\hat{\eta}_{12k}\right\|>\frac{\varepsilon}{2}\sqrt{n^{m}\log{p_{n^{m}}}}\right)$
	$\displaystyle\geq$	$\displaystyle 1-\max_{1\leq h<(n+1)^{m}-n^{m}}\frac{C\left((n+1)^{m}-n^{m}-h\right)}{\varepsilon^{2}n^{m}\log{p_{n^{m}}}}$
	$\displaystyle\geq$	$\displaystyle 1-\frac{C\left((n+1)^{m}-n^{m}\right)}{\varepsilon^{2}n^{m}\log{p_{n^{m}}}}\geq 1/2$

as $n\to\infty$ . Then, by (10), Ottaviani’s inequality and the same argument as in (11)–(14), we obtain

		$\displaystyle~{}P\left(\Psi_{n^{m}}>\varepsilon\sqrt{n^{m}\log{p_{n^{m}}}}\right)$
	$\displaystyle\leq$	$\displaystyle~{}p_{(n+1)^{m}}^{2}\cdot P\left(\max_{1\leq h<(n+1)^{m}-n^{m}}\left\|\sum_{k=1}^{h}\hat{\eta}_{12k}\right\|>\varepsilon\sqrt{n^{m}\log{p_{n^{m}}}}\right)$
	$\displaystyle\leq$	$\displaystyle~{}p_{(n+1)^{m}}^{2}\cdot P\left(\left\|\sum_{k=1}^{(n+1)^{m}-n^{m}}\hat{\eta}_{12k}\right\|>\frac{\varepsilon}{2}\sqrt{n^{m}\log{p_{n^{m}}}}\right)$
	$\displaystyle\leq$	$\displaystyle~{}p_{(n+1)^{m}}^{2}\cdot P\left(\left\|\sum_{k=1}^{(n+1)^{m}-n^{m}}\hat{\eta}_{12k}\right\|>\sqrt{\left(4+\varepsilon\right)((n+1)^{m}-n^{m})\log{p_{n^{m}}}}\right)$
	$\displaystyle=$	$\displaystyle~{}p_{(n+1)^{m}}^{2}\cdot P\left(\left\|\sum_{k=1}^{(n+1)^{m}-n^{m}}\frac{\hat{\eta}_{12k}}{\sqrt{(n+1)^{m}-n^{m}}}\right\|>\sqrt{\left(4+\varepsilon\right)\log{p_{n^{m}}}}\right)$
	$\displaystyle\lesssim$	$\displaystyle~{}C\cdot p_{(n+1)^{m}}^{2}\cdot\left[1-\Phi\left(\sqrt{\left(4+\varepsilon\right)\log{p_{n^{m}}}}\right)\right]$
	$\displaystyle\sim$	$\displaystyle~{}\frac{C\cdot p_{(n+1)^{m}}^{2}}{\sqrt{2\pi\left(4+\varepsilon\right)\log{p_{n^{m}}}}}e^{-\frac{\left(4+\varepsilon\right)\log{p_{n^{m}}}}{2}}$
	$\displaystyle=$	$\displaystyle~{}o\left(\frac{1}{n^{m\tau\varepsilon/2}}\right)$

for sufficient large $n$ . Since $m>m_{\varepsilon}$ , we see

\sum_{n=1}^{\infty}P\left(\Psi_{n^{m}}>\varepsilon\sqrt{n^{m}\log{p_{n^{m}}}}\right)<\infty

as $n\rightarrow\infty$ . Therefore, by the Borel–Cantelli lemma again,

\limsup_{n\to\infty}\frac{\Psi_{n^{m}}}{\sqrt{n^{m}\log{p_{n^{m}}}}}\leq\varepsilon\quad\text{a.s.}

(16)

Review (9)–(10) and (15)–(16). We obtain that

	$\displaystyle\limsup_{n\to\infty}\frac{\max_{1\leq i<j\leq p_{n}}\sum_{k=1}^{n}\hat{\eta}_{ijk}}{\sqrt{n\log{p_{n}}}}$	$\displaystyle\leq\limsup_{n\to\infty}\frac{\max_{n^{m}<l\leq(n+1)^{m}}\max_{1\leq i<j\leq p_{l}}\sum_{k=1}^{l}\hat{\eta}_{ijk}}{\sqrt{n^{m}\log{p_{n^{m}}}}}$
		$\displaystyle\leq\sqrt{4+\varepsilon}+\varepsilon\quad\text{a.s.}$

Choosing $\varepsilon>0$ small enough, we then get (6).

Step 2: proof of (7). Given $\varepsilon\in(0,1)$ , set $c_{n2}=\sqrt{\left(4-\varepsilon\right)\log{p_{n}}}$ . Set

I=\left\{(i,j);1\leq i<j\leq p_{n}\right\}.

For $\alpha=(i,j)\in I$ , define

X_{\alpha}=\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\hat{\eta}_{ijk}

and

B_{\alpha}=\left\{\left(k,l\right)\in I;\ \left\{k,l\right\}\cap\left\{i,j\right\}\neq\emptyset,\text{but}\left(k,l\right)\neq\alpha\right\}.

Note that $X_{\alpha}$ is independent of $\left\{X_{\beta};\beta\notin B_{\alpha}\right\}$ . By Lemma 3.1, we have

P\left(\max_{\alpha\in I}X_{\alpha}\leq c_{n2}\right)\leq e^{-\lambda_{1}}+b_{1}+b_{2},

(17)

where

\displaystyle\lambda_{1}=\sum_{\alpha\in I}P\left(X_{\alpha}>c_{n2}\right)=\frac{p_{n}\left(p_{n}-1\right)}{2}P\left(\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\hat{\eta}_{12k}>c_{n2}\right),

\displaystyle b_{1}=\sum_{\alpha\in I}\sum_{\beta\in B_{\alpha}}P\left(X_{\alpha}>c_{n2}\right)P\left(X_{\beta}>c_{n2}\right)\leq\frac{p_{n}\left(p_{n}-1\right)}{2}\cdot\left(2p_{n}\right)\cdot P\left(\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\hat{\eta}_{12k}>c_{n2}\right)^{2}

and

	$\displaystyle b_{2}$	$\displaystyle=\sum_{\alpha\in I}\sum_{\beta\in B_{\alpha}}P\left(X_{\alpha}>c_{n2},X_{\beta}>c_{n2}\right)$
		$\displaystyle\leq\frac{p_{n}\left(p_{n}-1\right)}{2}\cdot\left(2p_{n}\right)\cdot P\left(\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\hat{\eta}_{12k}>c_{n2},\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\hat{\eta}_{13k}>c_{n2}\right).$

We first calculate $\lambda_{1}$ . By the same argument as in (11)–(14), we have

$\displaystyle\lambda_{1}=$	$\displaystyle~{}\frac{p_{n}\left(p_{n}-1\right)}{2}P\left(\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\hat{\eta}_{12k}>c_{n2}\right)$	(18)
$\displaystyle\sim$	$\displaystyle~{}\frac{p_{n}\left(p_{n}-1\right)}{2\sqrt{2\pi}c_{n2}}e^{-\frac{c_{n2}^{2}}{2}}$
$\displaystyle=$	$\displaystyle~{}o\left(n^{\tau\varepsilon/2}\right)$

as $n\to\infty$ . Then, it follows from (18) that

$\displaystyle b_{1}\leq$	$\displaystyle~{}p_{n}^{3}\cdot P\left(\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\hat{\eta}_{12k}>c_{n2}\right)^{2}$	(19)
$\displaystyle\sim$	$\displaystyle~{}\frac{p_{n}^{3}}{2\pi c_{n2}^{2}}e^{-c_{n2}^{2}}$
$\displaystyle=$	$\displaystyle~{}o\left(\frac{1}{n^{\tau(1-\varepsilon)}}\right)$

as $n\to\infty$ .

Finally, we estimate $b_{2}$ . Set $\delta_{n2}=1/\sqrt{\log{p_{n}}}$ . By Theorem 1.1 from Zaĭtsev [23], there exist two normal random variables $\xi_{1}$ and $\xi_{2}$ such that

	$\displaystyle b_{2}\leq$	$\displaystyle~{}p_{n}^{3}\cdot P\left(\min\left\{\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\hat{\eta}_{12k},\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\hat{\eta}_{13k}\right\}>c_{n2}\right)$		(20)
	$\displaystyle\leq$	$\displaystyle~{}p_{n}^{3}\cdot\left[P\left(\min\left\{\xi_{1},\xi_{2}\right\}>c_{n2}-\delta_{n2}\right)+C\text{exp}\left(-C\frac{\sqrt{n}\delta_{n2}}{n^{s}}\right)\right],$		(20)

where $\{\xi_{1},\xi_{2}\}\sim N(0,\text{Var}(\hat{\eta}_{12k}))$ and $\text{Cov}(\xi_{1},\xi_{2})=\text{Cov}(\hat{\eta}_{12k},\hat{\eta}_{13k}):=\rho_{n}$ . For the exponential term,

p_{n}^{3}\cdot\text{exp}\left(-C\frac{\sqrt{n}\delta_{n2}}{n^{s}}\right)\leq\text{exp}\left(3\tau C\log{n}-Cn^{\frac{1}{2}-s}(\log{p_{n}})^{-\frac{1}{2}}\right)

(21)

as $n$ is sufficiently large. Since $\text{Var}(\xi_{1})=\text{Var}(\xi_{2})=\text{Var}(\hat{\eta}_{12k})\leq\text{Var}(\eta_{12k})=1$ , we have

	$\displaystyle~{}p_{n}^{3}\cdot P\left(\min\left\{\xi_{1},\xi_{2}\right\}>c_{n2}-\delta_{n2}\right)$	(22)
$\displaystyle\leq$	$\displaystyle~{}p_{n}^{3}\cdot P\left(\xi_{1}+\xi_{2}>2(c_{n2}-\delta_{n2})\right)$
$\displaystyle\leq$	$\displaystyle~{}p_{n}^{3}\cdot P\left(\frac{\xi_{1}+\xi_{2}}{\sqrt{2\text{Var}(\hat{\eta}_{12k})+2\rho_{n}}}>\frac{2(c_{n2}-\delta_{n2})}{\sqrt{2+2\rho_{n}}}\right)$
$\displaystyle\sim$	$\displaystyle~{}\frac{\sqrt{2+2\rho_{n}}\cdot p_{n}^{3}}{2\sqrt{2\pi}c_{n2}}e^{-\frac{c_{n2}^{2}}{1+\rho_{n}}}$
$\displaystyle=$	$\displaystyle~{}o\left(n^{\left(3-\frac{4-\varepsilon}{1+\rho_{n}}\right)\tau}\right)$

as $n\to\infty$ . By some calculations, we have

	$\displaystyle\rho_{n}$	$\displaystyle=\text{Cov}\left(\hat{\eta}_{12k},\hat{\eta}_{13k}\right)$
		$\displaystyle=\text{Cov}\left(\eta_{12k},\eta_{13k}\right)-E\left(\eta_{12k}\eta_{13k}I_{\{\max\{\|\eta_{12k}\|,\|\eta_{13k}\|\}>n^{s}\}}\right)-\left[E\left(\eta_{12k}I_{\{\|\eta_{12k}\|>n^{s}\}}\right)\right]^{2}$
		$\displaystyle\to\text{Cov}\left(\eta_{12k},\eta_{13k}\right)=\text{Corr}(\|X_{1,1}-X_{2,1}\|^{2},\|X_{1,1}-X_{3,1}\|^{2})$

as $n\to\infty$ . Therefore, if $\text{Corr}(|X_{1,1}-X_{2,1}|^{2},|X_{1,1}-X_{3,1}|^{2})<1/3$ , then $3-\frac{4-\varepsilon}{1+\rho_{n}}<0$ as $n\to\infty$ . Next, from (17)–(22), we obtain that

P\left(\max_{1\leq i<j\leq p_{n}}\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\hat{\eta}_{ijk}\leq c_{n2}\right)=P\left(\max_{\alpha\in I}X_{\alpha}\leq c_{n2}\right)\leq o\left(n^{-\varepsilon^{\prime}}\right)

as $n$ is sufficiently large, where $\varepsilon^{\prime}>0$ depends on $\varepsilon$ and $\text{Corr}(|X_{1,1}-X_{2,1}|^{2},|X_{1,1}-X_{3,1}|^{2})$ . Take an integer $m>1/\varepsilon^{\prime}$ such that

\sum_{n=1}^{\infty}P\left(\max_{1\leq i<j\leq p_{n^{m}}}\frac{1}{\sqrt{n^{m}}}\sum_{k=1}^{n^{m}}\hat{\eta}_{ijk}\leq\sqrt{\left(4-\varepsilon\right)\log{p_{n^{m}}}}\right)\leq\sum_{n=1}^{\infty}o\left(n^{-m\varepsilon^{\prime}}\right)<\infty

as $n\to\infty$ . Then, by the Borel–Cantelli lemma,

\liminf_{n\to\infty}\frac{\max_{1\leq i<j\leq p_{n^{m}}}\sum_{k=1}^{n^{m}}\eta_{ijk}}{\sqrt{n^{m}\log{p_{n^{m}}}}}>\sqrt{4-\varepsilon}\quad\text{a.s.}

(23)

Recalling (10), we find

\inf_{n^{m}<l\leq(n+1)^{m}}\max_{1\leq i<j\leq p_{l}}\sum_{k=1}^{l}\hat{\eta}_{ijk}\geq\max_{1\leq i<j\leq p_{n^{m}}}\sum_{k=1}^{n^{m}}\hat{\eta}_{ijk}-\Psi_{n^{m}}.

Combining the above inequality, (16) and (23), we obtain that

		$\displaystyle\liminf_{n\to\infty}\frac{\max_{1\leq i<j\leq p_{n}}\sum_{k=1}^{n}\eta_{ijk}}{\sqrt{n\log{p_{n}}}}$
	$\displaystyle\geq$	$\displaystyle\liminf_{n\to\infty}\frac{\inf_{n^{m}<l\leq(n+1)^{m}}\max_{1\leq i<j\leq p_{l}}\sum_{k=1}^{l}\eta_{ijk}}{\sqrt{n^{m}\log{p_{n^{m}}}}}$
	$\displaystyle\geq$	$\displaystyle\sqrt{4-\varepsilon}-\varepsilon\quad\text{a.s.}$

Then, (7) follows from the arbitrariness of $\varepsilon$ .

Step 3: proof of (8). Reviewing (5), we have

E\left|\eta_{12k}-\hat{\eta}_{12k}\right|^{4\tau+4+\epsilon}\lesssim E\left[|\eta_{12k}|^{4\tau+4+\epsilon}I_{\{|\eta_{12k}|\leq n^{s}\}}\right]<\infty

and

	$\displaystyle\text{Var}\left(\eta_{12k}-\hat{\eta}_{12k}\right)$	$\displaystyle=\text{Var}\left(\eta_{12k}I_{\{\|\eta_{12k}\|>n^{s}\}}\right)$
		$\displaystyle\leq E\left(\eta_{12k}^{2}I_{\{\|\eta_{12k}\|>n^{s}\}}\right)$
		$\displaystyle\leq\frac{E\left(\|\eta_{12k}\|^{4\tau+4+\epsilon}I_{\{\|\eta_{12k}\|>n^{s}\}}\right)}{n^{s(4\tau+2+\epsilon)}}$
		$\displaystyle\leq Cn^{-s(4\tau+2+\epsilon)}$

as $n\to\infty$ due to $E|X_{1,1}|^{8\tau+8+\epsilon}<\infty$ for some $\epsilon>0$ . Then, we see from Fuk–Nagaev inequality that, for $\varepsilon>0$ ,

		$\displaystyle\sum_{n=1}^{\infty}P\left(\max_{1\leq i<j\leq p_{n}}\left\|\sum_{k=1}^{n}\left(\eta_{ijk}-\hat{\eta}_{ijk}\right)\right\|>\varepsilon\sqrt{n\log p_{n}}\right)$
	$\displaystyle\leq$	$\displaystyle\sum_{n=1}^{\infty}p_{n}^{2}\cdot P\left(\left\|\sum_{k=1}^{n}\left(\eta_{12k}-\hat{\eta}_{12k}\right)\right\|>\varepsilon\sqrt{n\log p_{n}}\right)$
	$\displaystyle\lesssim$	$\displaystyle\sum_{n=1}^{\infty}\frac{np_{n}^{2}\cdot E\left\|\eta_{12k}-\hat{\eta}_{12k}\right\|^{4\tau+4+\epsilon}}{\left(\varepsilon\sqrt{n\log p_{n}}\right)^{4\tau+4+\epsilon}}+\sum_{n=1}^{\infty}p_{n}^{2}\cdot\text{exp}\left(-C\frac{\varepsilon^{2}\log p_{n}}{\text{Var}\left(\eta_{12k}-\hat{\eta}_{12k}\right)}\right)$
	$\displaystyle\lesssim$	$\displaystyle\sum_{n=1}^{\infty}\frac{1}{n^{1+\epsilon/2}}+\sum_{n=1}^{\infty}\text{exp}\left(2\tau C\log n-Cn^{s(4\tau+2+\epsilon)}\log p_{n}\right)<\infty$

as $n\to\infty$ under the assumption that $0<c_{1}\leq p/n^{\tau}\leq c_{2}<\infty$ for any $\tau>0$ . By the Borel–Cantelli lemma, we get

\lim_{n\to\infty}\frac{\max_{1\leq i<j\leq p_{n}}\left|\sum_{k=1}^{n}\left(\eta_{ijk}-\hat{\eta}_{ijk}\right)\right|}{\sqrt{n\log{p_{n}}}}\leq\varepsilon\quad\text{a.s.}

By choosing $\varepsilon>0$ small enough, the proof of (8) is completed. ∎

3.3 Proof of Theorem 2.2

Proof.

We continue to use the notations in the proof of Theorem 2.1. Note that

	$\displaystyle Ee^{t_{0}\|\eta_{ijk}\|^{\alpha}}\leq$	$\displaystyle~{}E~{}\text{exp}\left(Ct_{0}\left\|X_{i,k}^{2}+X_{j,k}^{2}+\sigma^{2}\right\|^{\alpha}\right)$
	$\displaystyle\leq$	$\displaystyle~{}E~{}\text{exp}\left(Ct_{0}\|X_{i,k}\|^{2\alpha}+Ct_{0}\|X_{j,k}\|^{2\alpha}+Ct_{0}\sigma^{2\alpha}\right)$
	$\displaystyle=$	$\displaystyle~{}C\cdot E~{}\text{exp}\left(2Ct_{0}\|X_{i,k}\|^{2\alpha}\right)<\infty$

due to $Ee^{t_{0}|X_{1,1}|^{2\alpha}}<\infty$ for some $0<\alpha\leq 1/2$ and $t_{0}>0$ . Then, by Lemma 3.2, we have

	$\displaystyle\sum_{n=1}^{\infty}P\left(\max_{1\leq i<j\leq p_{n}}\sum_{k=1}^{n}\eta_{ijk}>\sqrt{(4+\varepsilon)n\log{p_{n}}}\right)$	(24)
$\displaystyle\leq$	$\displaystyle\sum_{n=1}^{\infty}p_{n}^{2}\cdot P\left(\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\eta_{12k}>\sqrt{(4+\varepsilon)\log{p_{n}}}\right)$
$\displaystyle\sim$	$\displaystyle\sum_{n=1}^{\infty}\frac{p_{n}^{2}}{\sqrt{(4+\varepsilon)\log{p_{n}}}}e^{-\frac{(4+\varepsilon)\log{p_{n}}}{2}}$
$\displaystyle\leq$	$\displaystyle\sum_{n=1}^{\infty}\frac{1}{p_{n}^{\varepsilon/2}}=\sum_{n=1}^{\infty}o\left(\frac{1}{e^{\frac{\varepsilon}{2}n^{\frac{\alpha}{2-\alpha}}}}\right)<\infty$

as $n\to\infty$ since $\log{p}=o(n^{\frac{\alpha}{2-\alpha}})$ . Next, by the Borel–Cantelli lemma, one has

\limsup_{n\to\infty}\frac{\max_{1\leq i<j\leq p_{n}}\sum_{k=1}^{n}\eta_{ijk}}{\sqrt{n\log{p_{n}}}}\leq\sqrt{4+\varepsilon}\quad\text{a.s.}

(25)

Review the proof of (7), the definitions of $c_{n2}$ , $I$ and $B_{\alpha}$ . For each $\alpha=(i,j)\in I$ , set $Z_{\alpha}=\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\eta_{ijk}$ . By Lemma 3.1, we have

P\left(\max_{\alpha\in I}Z_{\alpha}\leq c_{n2}\right)\leq e^{-\lambda_{2}}+u_{1}+u_{2},

where

	$\displaystyle\lambda_{2}$	$\displaystyle=\frac{p_{n}\left(p_{n}-1\right)}{2}P\left(\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\eta_{12k}>c_{n2}\right),$
	$\displaystyle u_{1}$	$\displaystyle\leq p_{n}^{3}\cdot P\left(\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\eta_{12k}>c_{n2}\right)^{2},$
	$\displaystyle u_{2}$	$\displaystyle\leq p_{n}^{3}\cdot P\left(\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\eta_{12k}>c_{n2},\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\eta_{13k}>c_{n2}\right).$

By Lemma 3.2 and the same argument as in (24), we have

\lambda_{2}\sim\frac{p_{n}\left(p_{n}-1\right)}{2\sqrt{2\pi}c_{n2}}e^{-\frac{c_{n2}^{2}}{2}}=o\left(p_{n}^{\frac{\varepsilon}{2}}\right)=o\left(e^{\frac{\varepsilon}{2}n^{\frac{\alpha}{2-\alpha}}}\right)

as $n\to\infty$ . Furthermore, one can get that

u_{1}\leq\frac{p_{n}^{3}}{2\pi c_{n2}^{2}}e^{-c_{n2}^{2}}\leq\frac{1}{p_{n}^{1-\varepsilon}}=o\left(\frac{1}{e^{(1-\varepsilon)n^{\frac{\alpha}{2-\alpha}}}}\right)

for sufficiently large $n$ . Write

\eta_{12k}+\eta_{13k}=\frac{|X_{1,1}-X_{2,1}|^{2}+|X_{1,1}-X_{3,1}|^{2}-4E|X_{1,1}|^{2}}{\sqrt{2(E|X_{1,1}|^{4}+(E|X_{1,1}|^{2})^{2})}}.

By some calculations, we see

	$\displaystyle E\left(\eta_{12k}+\eta_{13k}\right)$	$\displaystyle=0,$
	$\displaystyle\text{Var}\left(\eta_{12k}+\eta_{13k}\right)$	$\displaystyle=2+2\text{Corr}(\|X_{1,1}-X_{2,1}\|^{2},\|X_{1,1}-X_{3,1}\|^{2}):=\tilde{\sigma}^{2}$

for each $k$ . Moreover, we know $Ee^{t_{0}|\eta_{12k}+\eta_{13k}|^{\alpha}}<\infty$ for some $0<\alpha\leq 1/2$ and $t_{0}>0$ . By Lemma 3.2, we then have that

	$\displaystyle u_{2}\leq$	$\displaystyle~{}p_{n}^{3}\cdot P\left(\frac{1}{\sqrt{n}}\sum_{k=1}^{n}\frac{\eta_{12k}+\eta_{13k}}{\tilde{\sigma}}>\frac{2c_{n2}}{\tilde{\sigma}}\right)$
	$\displaystyle\sim$	$\displaystyle~{}\frac{\tilde{\sigma}\cdot p_{n}^{3}}{2\sqrt{2\pi}c_{n2}}e^{-\frac{2(4-\varepsilon)\log{p_{n}}}{\tilde{\sigma}^{2}}}$
	$\displaystyle\leq$	$\displaystyle~{}p_{n}^{3-\frac{2(4-\varepsilon)}{\tilde{\sigma}^{2}}}$

as $n\to\infty$ . If $\text{Corr}(|X_{1,1}-X_{2,1}|^{2},|X_{1,1}-X_{3,1}|^{2})<1/3$ , then $3-\frac{2(4-\varepsilon)}{\tilde{\sigma}^{2}}<0$ and

\sum_{n=1}^{\infty}P\left(\max_{\alpha\in I}Z_{\alpha}\leq c_{n2}\right)\leq\sum_{n=1}^{\infty}\frac{1}{p_{n}^{\varepsilon^{\prime\prime}}}=\sum_{n=1}^{\infty}o\left(\frac{1}{e^{\varepsilon^{\prime\prime}n^{\frac{\alpha}{2-\alpha}}}}\right)<\infty

as $n\to\infty$ for some constant $\varepsilon^{\prime\prime}>0$ depending on $\varepsilon$ and $\text{Corr}(|X_{1,1}-X_{2,1}|^{2},|X_{1,1}-X_{3,1}|^{2})$ . Therefore, we see from the Borel–Cantelli lemma that

\liminf_{n\to\infty}\frac{\max_{1\leq i<j\leq p_{n}}\sum_{k=1}^{n}\eta_{ijk}}{\sqrt{n\log{p_{n}}}}>\sqrt{4-\varepsilon}\quad\text{a.s.}

Combining the above inequality, (4) and (25), the desired conclusion follows from the arbitrariness of $\varepsilon$ . ∎

4 Applications

4.1 $l^{q}$ -norm

Instead of studying the Euclidean norm distance, we will consider a more general distance, that is, $l^{q}$ -norm distance in $\mathbb{R}^{n}$ . For a $n$ -dimensional random vector $\boldsymbol{X}$ , define the $l^{q}$ -norm of $\boldsymbol{X}$ by

\left\|\boldsymbol{X}\right\|_{q}=\left(\sum_{k=1}^{n}|X_{k}|^{q}\right)^{1/q},

where $q\geq 1$ . And the maximum interpoint $l^{q}$ -norm distance is denoted by

M_{n,q}=\max_{1\leq i<j\leq p}\left\|\boldsymbol{X}_{i}-\boldsymbol{X}_{j}\right\|_{q}=\max_{1\leq i<j\leq p}\left(\sum_{k=1}^{n}|X_{i,k}-X_{j,k}|^{q}\right)^{1/q}.

Similarly to Theorem 2.1, one can deduce the law of the logarithm for $M_{n,q}$ as follows.

Theorem 4.1.

Assume

		$\displaystyle(i)\ 0<c_{1}\leq p/n^{\tau}\leq c_{2}<\infty\ \text{for}\text{ any}\ \tau>0;$
		$\displaystyle(ii)\ E\|X_{1,1}\|^{q(4\tau+4+\epsilon)}<\infty\ \text{for}\ \text{some}\ \epsilon>0;$
		$\displaystyle(iii)\ \mathrm{Corr}(\|X_{1,1}-X_{2,1}\|^{q},\|X_{1,1}-X_{3,1}\|^{q})<1/3;$

where $c_{1}$ and $c_{2}$ are constants not depending on $n$ . Then, the following holds as $n\to\infty$ :

\frac{M_{n,q}^{q}-nE\left(|X_{1,1}-X_{2,1}|^{q}\right)}{\sqrt{\mathrm{Var}(|X_{1,1}-X_{2,1}|^{q})n\log{p}}}\to 2\quad\text{a.s.}

(26)

Proof.

Reviewing the proof of Theorem 2.1, Theorem 4.1 follows from changing $\eta_{ijk}$ to

\eta_{ijk}=\frac{|X_{i,k}-X_{j,k}|^{q}-E\left(|X_{1,1}-X_{2,1}|^{q}\right)}{\sqrt{\mathrm{Var}(|X_{1,1}-X_{2,1}|^{q})}}.

It is obvious that

\max_{1\leq i<j\leq p}\sum_{k=1}^{n}\eta_{ijk}=\frac{M_{n,q}^{q}-nE\left(|X_{1,1}-X_{2,1}|^{q}\right)}{\sqrt{\mathrm{Var}(|X_{1,1}-X_{2,1}|^{q})}}.

Then, the proof of Theorem 4.1 is completed. ∎

By Theorem 2.2 and the same method as above, we obtain the following result.

Theorem 4.2.

Assume

		$\displaystyle(i)\ Ee^{t_{0}\|X_{1,1}\|^{q\alpha}}<\infty\ \text{for some}\ 0<\alpha\leq 1/2,\ t_{0}>0;$
		$\displaystyle(ii)\ \log{p}=o\left(n^{\frac{\alpha}{2-\alpha}}\right);$
		$\displaystyle(iii)\ \mathrm{Corr}(\|X_{1,1}-X_{2,1}\|^{2},\|X_{1,1}-X_{3,1}\|^{2})<1/3.$

Then, (26) holds as $\to\infty$ .

4.2 Simulation resluts

In this section, we carry out a Monte Carlo simulation on the law of logarithm for the maximum interpoint distance $M_{n}$ discussed in the previous section, to illustrate the validity of our results. We assume that $\{X_{i,k};1\leq i\leq p,1\leq k\leq n\}$ are i.i.d. $N(0,1)$ -distributed random variables. For each Monte Carlo iteration, we calculate the value of

z=\frac{M_{n}^{2}-2n}{2\sqrt{2n\log{p}}}.

In our simulation, we perform $K=300$ Monte Carlo iterations and work on four different combinations of $(p,n)$ with $(p,n)$ =(150, 100), $(p,n)$ =(200, 200), $(p,n)$ =(500, 250), and $(p,n)$ =(600, 400). Figures 1 and 2 present scatter diagrams that compare the values of $z$ and 2. The observed results indicate that the value of $z$ are uniformly distributed around 2, with no discernible bias between the scatter plots and 2, a trend accentuated by the substantial values of both $p$ and $n$ . This outcome serves as a compelling illustration of the validity of the results derived from the law of logarithm for the maximum interpoint distance $M_{n}$ . The systematic exploration of various $(p,n)$ combinations enriches the understanding of the behavior of $z$ in the context of this simulation, adding depth and credibility to the findings.

Refer to caption — Figure 1: Scatter diagrams corresponding to $(n,p)=(150,100)$ for the left picture and $(n,p)=(200,200)$ for the right. The straight line is $z=2$ .

Acknowledgements

The authors thank anonymous reviewers for giving valuable comments and suggestions in improving the manuscript. This paper was supported by National Natural Science Foundation of China (Grant No. 11771178, 12171198); the Science and Technology Development Program of Jilin Province (Grant No. 20210101467JC); Technology Program of Jilin Educational Department during the ”14th Five-Year” Plan Period (Grant No. JJKH20241239KJ) and Fundamental Research Funds for the Central Universities.

References

[1] Appel, M. J., Russo, R. P.: Limiting distributions for the maximum of a symmetric function on a random point set. J. Theor. Probab., 19(2), 365–375 (2006)
[2] Appel, M. J. B., Najim, C. A., Russo, R. P.: Limit laws for the diameter of a random point set. Adv. Appl. Probab., 34(1), 1–10 (2002)
[3] Arratia, R., Goldstein, L., Gordon, L.: Two moments suffice for Poisson approximations: the Chen-Stein method. Ann. Probab., 17, 9–25 (1989)
[4] Demichel, Y., Fermin, A. K., Soulier, P.: The diameter of an elliptical cloud. Electron. J. Probab., 20(27), 1–32 (2015)
[5] Ding, X.: Strong limit theorem for largest entry of large-dimensional random tensor. Random Matrices Theory Appl., doi: 10.1142 (2023)
[6] Heiny, J., Kleemann, C.: Maximum interpoint distance of high-dimensional random vectors. arXiv: 2302.06965 (2023)
[7] Henze, N., Klein, T.: The limit distribution of the largest interpoint distance from a symmetric kotz sample. J. Multivariate Anal., 57(2), 228–239 (1996)
[8] Henze, N., Lao, W.: The limit distribution of the largest interpoint distance for power-tailed spherically decomposable distributions and their affine images. Preprint, Karlsruhe Institute of Technology, (2010)
[9] Jammalamadaka, S. R., Janson, S.: Asymptotic distribution of the maximum interpoint distance in a sample of random vectors with a spherically symmetric distribution. Ann. Appl. Probab., 25(6), 3571–3591 (2015)
[10] Jiang, T.: The asymptotic distributions of the largest entries of sample correlation matrices. Ann. Appl. Probab., 14(2), 865–880 (2004)
[11] Lao, W.: Some weak limit laws for the diameter of random point sets in bounded regions, KIT Scientific Publishing, Karlsruhe, 2010
[12] Li, D., Rosalsky A.: Some strong limit theorems for the largest entries of sample correlation matrices. Ann. Appl. Probab., 16, 423–447 (2006)
[13] Li, J.: Asymptotic distribution-free change-point detection based on interpoint distances for high-dimensional data. J. Nonparametr. Stat., 32(1), 157–184 (2020)
[14] Linnik, J. V.: On the probability of large deviations for sums of independent variables. In Proc. 4th Berkeley Sympos. Math. Statist. and Prob., Vol. II, Univ. California Press, Berkeley, Calif., pp. 289–306 (1961)
[15] Matthews, P. C., Rukhin A. L.: Asymptotic distribution of the normal sample range. Ann. Appl. Probab., 3, 454–466 (1993)
[16] Mayer, M., Molchanov, I.: Limit theorems for the diameter of a random sample in the unit ball. Extremes, 10(3), 129–150 (2007)
[17] Modarres, R.: Multinomial interpoint distances. Statist. Papers, 59(1), 341–360 (2018)
[18] Modarres, R., Song, Y.: Interpoint distances: applications, properties, and visualization. Appl. Stoch. Models Bus. Ind., 36(6), 1147–1168 (2020)
[19] Schrempp, M.: The limit distribution of the largest interpoint distance for distributions supported by a $d$ -dimensional ellipsoid and generalizations. Adv. Appl. Probab., 48(4), 1256–1270 (2015)
[20] Schrempp, M.: Limit laws for the diameter of a set of random points from a distribution supported by a smoothly bounded set. Extremes, 22(1), 167–191 (2019)
[21] Song, Y., Modarres, R.: Interpoint distance test of homogeneity for multivariate mixture models. Int. Stat. Rev., 87(3), 613–638 (2019)
[22] Tang, P., Lu, R., Xie, J.: Asymptotic distribution of the maximum interpoint distance for high-dimensional data. Statist. Probab. Lett., 190, 109567 (2022)
[23] Zaĭtsev, A. Y.: On the Gaussian approximation of convolutions under multidimensional analogues of S. N. Bernstein’s inequality conditions. Probab. Theory Related Fields, 74(4), 535–566 (1987)

		$\displaystyle\mathrm{Corr}(\|X_{1,1}-X_{2,1}\|^{2},\|X_{1,1}-X_{3,1}\|^{2})$
	$\displaystyle=$	$\displaystyle\frac{\mathrm{Cov}(\|X_{1,1}-X_{2,1}\|^{2},\|X_{1,1}-X_{3,1}\|^{2})}{\mathrm{Var}(\|X_{1,1}-X_{2,1}\|^{2})}$
	$\displaystyle=$	$\displaystyle\frac{E\|X_{1,1}\|^{4}-(E\|X_{1,1}\|^{2})^{2}}{2(E\|X_{1,1}\|^{4}+(E\|X_{1,1}\|^{2})^{2})}.$

	$\displaystyle\text{Var}\left(\eta_{12k}-\hat{\eta}_{12k}\right)$	$\displaystyle=\text{Var}\left(\eta_{12k}I_{\{\|\eta_{12k}\|>n^{s}\}}\right)$
		$\displaystyle\leq E\left(\eta_{12k}^{2}I_{\{\|\eta_{12k}\|>n^{s}\}}\right)$
		$\displaystyle\leq\frac{E\left(\|\eta_{12k}\|^{4\tau+4+\epsilon}I_{\{\|\eta_{12k}\|>n^{s}\}}\right)}{n^{s(4\tau+2+\epsilon)}}$
		$\displaystyle\leq Cn^{-s(4\tau+2+\epsilon)}$

	$\displaystyle Ee^{t_{0}\|\eta_{ijk}\|^{\alpha}}\leq$	$\displaystyle~{}E~{}\text{exp}\left(Ct_{0}\left\|X_{i,k}^{2}+X_{j,k}^{2}+\sigma^{2}\right\|^{\alpha}\right)$
	$\displaystyle\leq$	$\displaystyle~{}E~{}\text{exp}\left(Ct_{0}\|X_{i,k}\|^{2\alpha}+Ct_{0}\|X_{j,k}\|^{2\alpha}+Ct_{0}\sigma^{2\alpha}\right)$
	$\displaystyle=$	$\displaystyle~{}C\cdot E~{}\text{exp}\left(2Ct_{0}\|X_{i,k}\|^{2\alpha}\right)<\infty$

Law of the logarithm for the maximum interpoint distance constructed by high-dimensional random matrix

Abstract

1 Introduction

2 Main results

Theorem 2.1.

Theorem 2.2.

Corollary 2.3.

Remark 2.4.

Remark 2.5.

3 Proofs

3.1 Some technical tools

Lemma 3.1.

Lemma 3.2.

3.2 Proof of Theorem 2.1

Proof.

3.3 Proof of Theorem 2.2

Proof.

4 Applications

4.1 lql^{q}-norm

Theorem 4.1.

Proof.

Theorem 4.2.

4.2 Simulation resluts

Acknowledgements

References

4.1 $l^{q}$ -norm