# Least Squares-Based Permutation Tests in Time Series

Joseph P. Romano111Supported by NSF Grant MMS-1949845.
Departments of Statistics and Economics
Stanford University
<EMAIL_ADDRESS>Marius A. Tirlea222Supported by NSF Grant MMS-1949845.
Department of Statistics
Stanford University
<EMAIL_ADDRESS>
###### Abstract

This paper studies permutation tests for regression parameters in a time
series setting, where the time series is assumed stationary but may exhibit an
arbitrary (but weak) dependence structure. In such a setting, it is perhaps
surprising that permutation tests can offer any type of inference guarantees,
since permuting of covariates can destroy its relationship with the response.
Indeed, the fundamental assumption of exchangeability of errors required for
the finite-sample exactness of permutation tests, can easily fail. However, we
show that permutation tests may be constructed which are asymptotically valid
for a wide class of stationary processes, but remain exact when
exchangeability holds. We also consider the problem of testing for no monotone
trend and we construct asymptotically valid permutation tests in this setting
as well.

Keywords: Hypothesis Testing, Permutation Tests, Regression, Trend.

##  1 Introduction

In every quantitative field, an issue of critical importance is the assessment
of the relationship between explanatory variables and a response variable. The
classical method most frequently used to undertake such an analysis is that of
ordinary least squares (OLS) regression, which involves construction of a
feature matrix $X$ and a response vector $Y$, and computation of the sample
regression coefficient $\hat{\beta}$ as an estimate of the unconditional
linear regression coefficient $\beta$ between the covariates $X$ and the
response variable $Y$. The computation of $\hat{\beta}$ is often accompanied
by a test of the null hypothesis

$H_{0}:\beta=0\,\,,$

since it is often of great interest to determine which of the regression
coefficients differ significantly from 0. In general, such tests compare the
sum of the squared residuals to a reference null distribution, and in doing so
make parametric distributional assumptions both on the pairs of samples
$(X_{i},\,Y_{i})$, often assuming that the $(X_{i},\,Y_{i})$ are jointly
Gaussian, and also often assume that the pairs of samples are independent. In
the context of time series analysis, neither of these assumptions hold in
general, and so any accompanying inference from such a hypothesis test may be
wildly incorrect.

In addition, OLS regression is often used to test for monotone trend in time
series analysis: namely, for a sequence $\\{X_{i}:i\in[n]\\}$, a regression of
the sequence $\\{X_{i}:i\in[n]\\}$ against index $\\{i:i\in[n]\\}$ is
performed, and a univariate $t$-test is performed to assess whether or not the
resulting regression coefficient is significantly different from 0. However,
there is an implicit assumption under the null hypothesis that the $X_{i}$ are
i.i.d., and so such a test can lead to rejection of the null hypothesis of “no
monotone trend”, for some definition thereof, on account of the violation of
independence, as opposed to because there is truly some monotone trend.

In this paper, we propose nonparametric testing methods for both the classical
regression null hypothesis of no significance

$H_{0}:\beta=0\,\,,$

and for the linear regression null hypothesis of no monotone trend

$H_{0}^{(m)}:\\{X_{i}:i\in[n]\\}\text{ exhibits no monotone trend,}$

where the definition of a lack of monotone trend will be stated precisely.

The problems described above have been studied extensively in different
contexts. Durbin, (1960) estimates regression parameters in a time series
setting, Tsay, (1984) considers a linear model in which the errors are
distributed according to an autoregressive process, Tran et al., (1996)
consider recovery of a regression function in a regression setting with time-
dependent errors, Kedem and Fokianos, (2002) discusses several different
methods for regression in a time series context, and Wang et al., (2008) and
Wang and Keilegom, (2007) consider a nonparametric test in the context of time
series regression analysis.

In the setting of permutation-based tests for linear regression, Anderson and
Robinson, (2001) produce a permutation test based on partial correlations,
Nyblom, (2015) discusses several regression-based permutation tests, DiCiccio
and Romano, (2017) discuss testing for correlation and regression
coefficients, and, in a more empirical setting, Hemerik et al., (2021)
performs an empirical analysis of permutation testing in a high-dimensional
linear regression problem. In Romano and Tirlea, (2022), permutation tests are
developed for testing autocorrelations in a time series setting.

The goal of this paper is to develop a framework for the use of permutation
testing as a valid method for testing the two aforementioned hypotheses, which
preserves the exactness property under the randomization hypothesis, but is
also asymptotically valid for a large class of weakly dependent sequences.
Permutation tests (as a special case of randomization tests) provide exact
level $\alpha$ tests when the randomization hypothesis holds; see Lehmann and
Romano, (2022), Chapter 17. As such, they offer a means of valid inference in
some complex semi-parametric and nonparametric settings. However, the problem
is they often fail if the randomization hypothesis does not hold. For example,
when testing a null hypothesis that a regression coefficient is 0, the
randomization hypothesis holds for permutations of the regressors when the
regressors are independent of the response. But of course, the regression
coefficient may be 0 even under dependence, in which case Type 1 error rates
can be severely inflated, even asymptotically. But a growing literature as
described in Section 1 of Romano and Tirlea, (2022) shows that asymptotic
validity can be recovered for certain (studentized) choice of test statistics,
while preserving exactness in finite samples when the randomization hypothesis
holds. The challenge in the context of this paper is that we are allowing the
regressors and response to be dependent, but we are also allowing observations
across time to be dependent. In such settings, it is not clear that
permutations should offer a valid approach to inference, but our findings are
indeed positive.

Section 2 provides several useful preliminary definitions and results.. The
main results relating to the null hypothesis $H_{0}$ are given in Section 3,
in which we give conditions for the asymptotic validity of the permutation
test when $\\{X_{i}:i\in[n]\\}$ is a stationary, $\alpha$-mixing sequence,
satisfying relatively standard technical moment and mixing conditions. Section
4 gives the main results for the asymptotic validity of the permutation test
for the hypothesis of no monotone trend. Section 5 provides simulations
illustrating the results. On account of the technical nature of showing the
results in the aforementioned sections, the majority of the proofs are
deferred to the supplement.

##  2 Preliminaries

In this section, we establish notation and definitions which will be used in
Section 3, in addition to providing a useful central limit theorem. We begin
with a brief discussion of $\alpha$-mixing. Let $\\{X_{n},\,n\in\mathbb{Z}\\}$
be a stationary sequence of random variables, adapted to the filtration
$\\{\mathcal{F}_{n}\\}$. Let $\mathcal{G}_{n}=\sigma\left(X_{r}:\,r\geq
n\right)$. For $n\in\mathbb{N}$, let $\alpha_{X}(n)$ be Rosenblatt’s
$\alpha$-mixing coefficient, defined as

$\alpha_{X}(n)=\sup_{A\in\mathcal{F}_{0},\,B\in\mathcal{G}_{n}}\left|\mathbb{P}(A\cap
B)-\mathbb{P}(A)\mathbb{P}(B)\right|\,\,.$ (2.1)

We say that $\\{X_{n}\\}$ is $\alpha$-mixing if $\alpha_{X}(n)\to 0$ as
$n\to\infty$.

Exact permutation tests (and randomization tests more generally) can be
constructed when the randomization hypothesis holds (Lehmann and Romano,
(2022), Chapter 17). In our setting, the randomization hypothesis refers to
the assertion that transformations of the data by certain permutations leaves
the underlying distribution unchanged, if the null hypothesis holds.
Therefore, it is important to define the action of a permutation on pairs
$\\{(Y_{i},\,X_{i}):i\in[n]\\}\subset\mathbb{R}\times\mathbb{R}^{p}$. To be
sure, the randomization hypothesis will not generally hold in our setting, and
the main problem becomes how to adapt a permutation test so that it is at
least asymptotically valid while retaining the exactness property when the
randomization hypothesis holds.

Let $S_{n}$ be the symmetric of all permutations of $[n]=\\{1,\ldots,n\\}$. We
say that $\pi_{n}\in S_{n}$ acts on $\\{Z_{i}=(Y_{i},\,X_{i}):i\in[n]\\}$ by
row-wise permutation of the $X_{i}$, i.e.

$Z_{\pi_{n}}=((Y_{1},\,X_{\pi_{n}(1),\,1},\,\dots,\,X_{\pi_{n}(1),\,p}),\,\dots,\,(Y_{n},\,X_{\pi_{n}(n),\,1},\,\dots,\,X_{\pi_{n}(n),\,p}))\,\,.$

In the context of linear regression, the interpretation of the action of this
permutation is that we permute the rows of the feature matrix $X$ prior to
computation of the regression coefficient. Note also that, in the case of the
action of a random permutation $\Pi_{n}\sim\text{Unif}(S_{n})$ on $Z_{n}$,
this definition of the action of a permutation is equivalent to the action of
two i.i.d. random permutations on the $Y_{i}$ and $X_{j}$, since, for
$\Pi_{n},\,\Pi_{n}^{\prime}\sim\text{Unif}(S_{n})$, with $\Pi_{n}$ and
$\Pi_{n}^{\prime}$ independent

$(\Pi_{n}^{\prime})^{-1}\Pi_{n}\overset{d}{=}\Pi_{n}\,\,.$

By a similar argument to Lemma S.3.1 in Romano and Tirlea, (2022), in the
setting in which the sequence $\\{Z_{i}:i\in[n]\\}$ is $\alpha$-mixing, the
randomization hypothesis holds if and only if the sequences
$\\{Y_{n}:n\in\mathbb{N}\\}$ and $\\{X_{n}:n\in\mathbb{N}\\}$ are independent
and the $X_{i}$ are exchangeable, which, in the setting of stationary and
$\alpha$-mixing sequences, is equivalent to the $X_{i}$ being i.i.d. If such
independence holds, the usual OLS regression parameter vector $\beta$ is 0
(assuming that the second moment of $X$ is finite so that $\beta$ is well-
defined), and permutation tests are exact. However, $\beta$ can be 0 without
the randomization hypothesis holding, and we still wish to construct valid
procedures in such settings.

In Section 3, it is necessary to compare the limiting sample distribution of
the test statistic to the permutation distribution in order to obtain an
asymptotically valid testing procedure. We therefore provide the following
result, which follows from a straightforward application of the Cramér-Wold
device, Slutsky’s theorem and the central limit theorem due to Neumann,
(2013).

######  Theorem 2.1.

Let $\\{X_{n}:n\in\mathbb{N}\\}$ be a stationary sequence of
$\mathbb{R}^{p}$-valued random variables, with mean vector $\mu_{X}$ and
positive definite covariance matrix $\Sigma_{X}$, and let
$\\{Y_{n}:n\in\mathbb{N}\\}$ be a stationary sequence of $\mathbb{R}$-valued
random variables, with mean $\mu_{Y}$ and variance $\sigma_{Y}^{2}>0$. For
each $n$, let $Z_{n}=(Y_{n},\,X_{n,\,1},\,\dots,\,X_{n,\,p})$. Suppose that,
for some $\delta>0$,

$\lVert Z_{1}\rVert_{8+4\delta}<\infty$

and

$\sum_{n\geq 1}\alpha_{Z}(n)^{\frac{\delta}{2+\delta}}<\infty\,\,.$

Let $\bar{X}_{n}$ be the coordinate-wise sample mean of the $X_{i}$, and let
$\bar{Y}_{n}$ be the sample mean of the $Y_{i}$. Let

$\hat{\beta}_{n}=\left[\frac{1}{n}\sum_{i=1}^{n}(X_{i}-\bar{X}_{n})(X_{i}-\bar{X}_{n})^{T}\right]^{-1}\left(\frac{1}{n}\sum_{i=1}^{n}(Y_{i}-\bar{Y}_{n})(X_{i}-\bar{X}_{n})\right)$

be the least squares coefficient of the regression of $Y$ on $X$, and let
$\beta$ be the unconditional regression coefficient of $Y_{1}$ on $X_{1}$,
i.e.

$\beta=\Sigma_{X}^{-1}\text{Cov}(Y_{1},X_{1})\,\,.$ (2.2)

Let $\Gamma\in\mathbb{R}^{p\times p}$ such that

$\displaystyle\Gamma=\text{Var}(X_{1}(Y_{1}-X_{1}^{T}\beta))+2\sum_{n\geq
2}\text{Cov}(X_{1}(Y_{1}-X_{1}^{T}\beta),\,X_{n}(Y_{n}-X_{n}^{T}\beta))$ (2.3)

Suppose that $\Gamma$ is positive definite. Then, as $n\to\infty$,

$\sqrt{n}(\hat{\beta}_{n}-\beta)\overset{d}{\to}N(0,\,\Sigma_{X}^{-1}\Gamma\Sigma_{X}^{-1})\,\,.$

A similar result to Theorem 2.1 has been shown in Chapter 5 of White, (2000),
with slightly different conditions on the sequence
$\\{Z_{n}=(Y_{n},\,X_{n}):n\in\mathbb{N}\\}$. It is provided in this section
to make explicit the limiting distribution of the sample least squares
coefficient $\hat{\beta}_{n}$.

Having obtained the above result, we may now begin direct comparison of the
limiting sample distribution and the permutation distribution.

##  3 Testing for regression coefficients

In this section, we consider the problem of testing the null hypothesis

$H_{0}:\beta=0\,\,,$

where $\beta=\beta(Y,\,X)$ is the unconditional regression coefficient defined
in (2.2), in the setting where the sequence
$\\{(Y_{i},\,X_{i}):i\in\mathbb{N}\\}\subset\mathbb{R}\times\mathbb{R}^{p}$ is
stationary and $\alpha$-mixing. As discussed in Section 2, when the
randomization hypothesis holds, one may construct permutation tests of the
hypothesis $H_{0}$ with exact level $\alpha$ in finite samples.

However, if the randomization hypothesis does not hold, the test may not be
valid even asymptotically, i.e. the rejection probability may not be equal to
or even close to $\alpha$ in the limit as $n\to\infty$. Our goal is therefore
to construct a permutation testing procedure, based on an appropriately chosen
test statistic, which has asymptotic rejection probability equal to $\alpha$,
and which retains the finite sample exactness property under the additional
assumption that the randomization hypothesis holds.

In a similar fashion to Romano and Tirlea, (2022), we wish to consider a
permutation test based on the sample regression coefficient $\hat{\beta}_{n}$.
As in that paper, our overarching goal is show that, for an appropriately
studentized version of $\hat{\beta}_{n}$, under the null hypothesis
$H_{0}:\beta=0$, the asymptotic distribution of the test statistic is
asymptotically pivotal, i.e. does not depend on the underlying process
$\\{(Y_{n},\,X_{n})\\}$, and that the corresponding permutation distribution
$\hat{R}_{n}$ has a limiting distribution which is the same as the limiting
distribution of the test statistic.

We begin with analysis of the unstudentized permutation distribution. As in
Romano and Tirlea, (2022), we initially assume that the $Y_{i}$ and $X_{i}$
are bounded. We may then apply Hoeffding’s combinatorial central limit theorem
(Hoeffding,, 1951) conditional on the data $\\{(Y_{i},\,X_{i})\\}$, checking
that appropriate moment conditions on the sample variances are satisfied. We
may then relax the boundedness constraint on the sequence using a standard
truncation argument, thereby obtaining the following result.

######  Theorem 3.1.

Under the assumptions of Theorem 2.1, let $\hat{R}_{n}$ be the permutation
distribution based on the test statistic $\sqrt{n}\hat{\beta}_{n}$. Then, as
$n\to\infty$,

$\sup_{t\in\mathbb{R}^{p}}\left|\hat{R}_{n}(t)-F_{\sigma_{Y}^{2}\Sigma_{X}^{-1}}(t)\right|\overset{p}{\to}0\,\,.$

where, for a positive definite matrix $M\in\mathbb{R}^{p\times p}$, $F_{M}$ is
the multivariate c.d.f. of a $N(0,\,M)$ random variable.

######  Remark 3.1.

There is some subtlety required in the proof of the convergence of a
multivariate permutation distribution compared to the analogous univariate
setting. In both cases, for any subsequence $\\{n_{j}:j\in\mathbb{N}\\}$, we
find a subsequence $\\{n_{j_{k}}:k\in\mathbb{N}\\}\subset\\{n_{j}\\}$ such
that we may apply an appropriate combinatorial central limit theorem with
probability 1; in the case of the first-order sample autocorrelation, this is
the theorem of Wald and Wolfowitz, (1943); here, we apply the central limit
theorem (CLT) due to Hoeffding, (1951).

However, due to the requirement of an application of the Cramér-Wold device in
order to show convergence in the multivariate setting of Theorem 3.1, we have
the additional requirement that the set $A$ of probability 1 on which we apply
the univariate CLT of Hoeffding, (1951) is the same set for any choice of
vector $t\in\mathbb{R}^{p}$. If we were to essentially repeat the proof in the
univariate setting separately for $\sqrt{n}t^{T}\hat{\beta}_{n}$ for each
$t\in\mathbb{R}^{p}$, we would have no guarantee that the univariate
convergence in distribution holds simultaneously for all $t\in\mathbb{R}^{p}$,
since the intersection of an uncountable family of sets of measure 1 may not
have measure 1. Therefore we would be unable to apply the Cramér-Wold device
with probability 1, and so the result of Theorem 3.1 would not hold. For
further details, please see the proof of the Theorem in the Appendix.

We observe that, as in the setting of Romano and Tirlea, (2022), while the
limiting distribution of the sample regression coefficient and the limiting
permutation distribution are both multivariate Gaussian with mean zero under
the null hypothesis $H_{0}$, the variances of these two distributions are not,
in general, equal. We therefore proceed to construct an appropriate
studentizing factor; to this end, we present the following result.

######  Lemma 3.1.

In the setting of Theorem 2.1, for each $i,\,n\in\mathbb{N}$ such that $i\leq
n$, let

$\hat{\epsilon}_{i,\,n}=Y_{i}-X_{i}^{T}\hat{\beta}_{n}\,\,.$

Let $\\{b_{n}:n\in\mathbb{N}\\}\subset\mathbb{N}$ be a nondecreasing sequence
such that $b_{n}\to\infty$ as $n\to\infty$ and $b_{n}=o(\sqrt{n})$. For each
$n$, for each $(i,\,j)\in[n]\times[n]$, let

$\displaystyle\hat{\gamma}_{n,\,i,\,j}$
$\displaystyle=\frac{1}{n}\sum_{l=1}^{n}\left(X_{l,\,i}\hat{\epsilon}_{l,\,n}-\frac{1}{n}\sum_{k=1}^{n}X_{k,\,i}\hat{\epsilon}_{k,\,n}\right)\left(X_{l,\,j}\hat{\epsilon}_{l,\,n}-\frac{1}{n}\sum_{k=1}^{n}X_{k,\,j}\hat{\epsilon}_{k,\,n}\right)$
$\displaystyle\hat{\tau}_{n,\,i,\,j}$
$\displaystyle=\frac{2}{n}\sum_{k=1}^{b_{n}}\sum_{l=1}^{\min\\{n-k,\,n-b_{n}\\}}\left(X_{l,\,i}\hat{\epsilon}_{l,\,n}-\frac{1}{n}\sum_{r=1}^{n}X_{r,\,i}\hat{\epsilon}_{r,\,n}\right)\left(X_{l+k,\,j}\hat{\epsilon}_{l+k,\,n}-\frac{1}{n}\sum_{r=1}^{n}X_{r,\,j}\hat{\epsilon}_{r,\,n}\right)$

Let $\hat{\Gamma}_{n}\in\mathbb{R}^{p\times p}$ be such that

$\hat{\Gamma}_{i,\,j}=\hat{\gamma}_{n,\,i,\,j}+\hat{\tau}_{n,\,i,\,j}\,\,.$

Let $\Pi_{n}\sim\text{Unif}(S_{n})$, independent of $\\{Z_{i}:i\in[n]\\}$, and
let

$\hat{\Gamma}_{\Pi_{n}}=\hat{\Gamma}_{n}((Y_{1},\,X_{\Pi_{n}(1)}),\,\dots,\,(Y_{n},\,X_{\Pi_{n}(n)}))$

Then, as $n\to\infty$, we have that

$\displaystyle\hat{\Gamma}_{n}$ $\displaystyle\overset{p}{\to}\Gamma$
$\displaystyle\hat{\Gamma}_{\Pi_{n}}$
$\displaystyle\overset{p}{\to}\sigma_{Y}^{2}\Sigma_{X}\,\,.$

######  Remark 3.2.

We observe that the estimator $\hat{\Gamma}_{n}$ is quite similar to the
Newey-West estimator (Newey and West, (1987), and similar in spirit to the
heteroskedasticity-consistent estimator of White, (1980). Indeed, an analogous
proof to the one of Lemma 3.1 shows that the Newey-West estimator of variance
satisfies the same consistency properties as the chosen estimator
$\hat{\Gamma}_{n}$.

Combining Theorem 2.1, Theorem 3.1, and Lemma 3.1 with an application of
Slutsky’s theorem and the multivariate Slutsky theorem for randomization
distributions (Chung and Romano, (2016), Lemma A.5), we have the following
result.

######  Theorem 3.2.

Let $\\{X_{n}:n\in\mathbb{N}\\}$ be a stationary sequence of
$\mathbb{R}^{p}$-valued random variables, with mean vector $\mu_{X}$ and
positive definite covariance matrix $\Sigma_{X}$, and let
$\\{Y_{n}:n\in\mathbb{N}\\}$ be a stationary sequence of $\mathbb{R}$-valued
random variables, with mean $\mu_{Y}$ and variance $\sigma_{Y}^{2}>0$. For
each $n$, let $Z_{n}=(Y_{n},\,X_{n,\,1},\,\dots,\,X_{n,\,p})$. Suppose that,
for some $\delta>0$,

$\lVert Z_{1}\rVert_{8+4\delta}<\infty$

and

$\sum_{n\geq 1}\alpha_{Z}(n)^{\frac{\delta}{2+\delta}}<\infty\,\,.$

Let $\hat{\beta}_{n}$ be the least squares regression coefficient defined in
(2.1) and let $\beta$ be the unconditional regression coefficient of $Y_{1}$
on $X_{1}$ defined in (2.2). For each $n\in\mathbb{N},\,i\in[n]$, let

$\hat{\epsilon}_{i,\,n}=Y_{i}-X_{i}^{T}\hat{\beta}_{n}\,\,.$

Let $\\{b_{n}:n\in\mathbb{N}\\}\subset\mathbb{N}$ be a nondecreasing sequence
such that $b_{n}\to\infty$ as $n\to\infty$ and $b_{n}=o(\sqrt{n})$. For each
$n$, for each $(i,\,j)\in[n]\times[n]$, let

$\displaystyle\hat{\gamma}_{n,\,i,\,j}$
$\displaystyle=\frac{1}{n}\sum_{l=1}^{n}\left(X_{l,\,i}\hat{\epsilon}_{l,\,n}-\frac{1}{n}\sum_{k=1}^{n}X_{k,\,i}\hat{\epsilon}_{k,\,n}\right)\left(X_{l,\,j}\hat{\epsilon}_{l,\,n}-\frac{1}{n}\sum_{k=1}^{n}X_{k,\,j}\hat{\epsilon}_{k,\,n}\right)$
$\displaystyle\hat{\tau}_{n,\,i,\,j}$
$\displaystyle=\frac{2}{n}\sum_{k=1}^{b_{n}}\sum_{l=1}^{\min\\{n-k,\,n-b_{n}\\}}\left(X_{l,\,i}\hat{\epsilon}_{l,\,n}-\frac{1}{n}\sum_{r=1}^{n}X_{r,\,i}\hat{\epsilon}_{r,\,n}\right)\left(X_{l+k,\,j}\hat{\epsilon}_{l+k,\,n}-\frac{1}{n}\sum_{r=1}^{n}X_{r,\,j}\hat{\epsilon}_{r,\,n}\right)$

Let $\hat{\Gamma}_{n}\in\mathbb{R}^{p\times p}$ be such that

$\hat{\Gamma}_{i,\,j}=\hat{\gamma}_{n,\,i,\,j}+\hat{\tau}_{n,\,i,\,j}\,\,.$

Then the following results hold.

  1. (i)

As $n\to\infty$,

$\left(\hat{\Gamma}_{n}^{-1/2}\hat{\Sigma}_{X}\right)\sqrt{n}(\hat{\beta}_{n}-\beta)\overset{d}{\to}N(0,\,I)\,\,.$

  2. (ii)

Let $\hat{R}_{n}$ be the permutation distribution based on the test statistic
$\left(\hat{\Gamma}_{n}^{-1/2}\hat{\Sigma}_{X}\right)\sqrt{n}\hat{\beta}_{n}$,
with associated group of transformations $S_{n}$, the symmetric group of order
$n$. Then, as $n\to\infty$,

$\sup_{t\in\mathbb{R}^{p}}\left|\hat{R}_{n}(t)-F_{I}(t)\right|\overset{p}{\to}0\,\,,$

where $F_{I}$ is the multivariate c.d.f. of the $p$-dimensional Gaussian
distribution with zero mean and identity variance matrix.

###### Proof.

(i) follows as a result of Theorem 2.1, Lemma 3.1, the continuous mapping
theorem, and Slutsky’s theorem.

As a result of Theorem 3.1, Lemma 3.1, the continuous mapping theorem and the
multivariate Slutsky theorem for randomization distributions, i.e. Lemma A.5
of Chung and Romano, (2016), it follows that, for all $t\in\mathbb{R}^{p}$, as
$n\to\infty$,

$\hat{R}_{n}(t)\overset{p}{\to}F_{I}(t)\,\,.$

Subsequently, the uniform convergence in $t$ follows from the multivariate
version of Polyá’s theorem due to Chandra, (1989), i.e. (ii) holds.

######  Remark 3.3.

As a result of Theorem 3.2, we may construct an asymptotically valid
permutation test of the null hypothesis $H_{0}$ at the nominal level $\alpha$
as follows. Let $P$ be the probability measure induced by the standard
multivariate Gaussian distribution on $\mathbb{R}^{p}$. Let $A$ be any Borel
set in $\mathbb{R}^{p}$ whose boundary has Lebesgue measure zero. If
$P(A)=1-\alpha$, then the test that rejects if

$\left(\hat{\Gamma}_{n}^{-1/2}\hat{\Sigma}_{X}\right)\sqrt{n}\hat{\beta}_{n}\in
A^{C}\,\,,$

where $A^{C}=\\{x\in\mathbb{R}^{p}:x\notin A\\}$, and does not reject
otherwise is asymptotically valid at the nominal level $\alpha$. For instance,
letting $A$ be the ball of an appropriate radius centered at the origin will
correspond to the Chi-squared test of significance in standard OLS regression
theory. Similarly, taking $A$ to be a cube centered at the origin (or more
generally a hyper-rectangle) corresponds, in a traditional regression setting,
to the test which rejects for large values of the maximum. Alternatively, one
may take $A$ to be an ellipsoid centered at the origin, if one wishes to place
more emphasis on a particular coordinate of the unconditional regression
coefficient than the others.

However, it is critical to note that any measurable set $A$ satisfying the
properties described above will induce an asymptotically valid test. To
provide another, more general example, for a continuous function
$g:\mathbb{R}^{p}\to\mathbb{R}$, and a choice of $t\in\mathbb{R}$ such that,
for $Z\sim N_{p}(0,\,I_{p})$,

$\mathbb{P}(g(Z)\leq t)=1-\alpha\,\,,$

we may take $A=g^{-1}((-\infty,\,t])$.

######  Example 3.1.

($VARMA(p,\,q)$ process) Let $d\in\mathbb{N}$, and let
$\\{\epsilon_{n}:n\in\mathbb{N}\\}\subset\mathbb{R}^{d+1}$ be a sequence of
mean zero i.i.d. random variables such that, for some $\delta>0$,

$\lVert\epsilon_{1}\rVert_{8+4\delta}<\infty\,\,.$

Let $B_{0}=I_{d+1}$ be the identity matrix. Let $p,\,q\in\mathbb{N}$, and let
$\\{A_{i}:i\in[q]\\}\subset\mathbb{R}^{(d+1)\times(d+1)}$ and
$\\{B_{j}:j\in[p]\\}\subset\mathbb{R}^{(d+1)\times(d+1)}$ be matrices.

Let
$\\{Z_{n}=(Y_{n},\,X_{n,\,1},\,\dots,\,X_{n,\,d}):n\in\mathbb{N}\\}\subset\mathbb{R}^{d+1}$
satisfy the following vector autoregressive moving average $(VARMA)$ equation,
i.e. for all $n\in\mathbb{N}$ such that $n\geq p+1$,

$\sum_{j=0}^{p}B_{j}Z_{n-j}=\sum_{i=0}^{q}A_{i}\epsilon_{n-i}\,\,,$ (3.1)

i.e. $\\{Z_{n}\\}$ is a $VARMA(p,\,q)$ process. Let
$g:\mathbb{C}\to\mathbb{C}$ be the polynomial

$g(z)=\det\left(\sum_{j=0}^{p}B_{j}z^{j}\right)\,\,.$

Suppose that the roots of $g$ lie outside the complex unit circle
$\mathbb{D}=\\{z\in\mathbb{C}:|z|\leq 1\\}$. Then, by Lutkepohl, (2006), there
exists a unique stationary solution to (3.1), i.e. there exists a stationary
sequence $\\{Z_{n}\\}$ satisfying (3.1).

Suppose that, in this setting, the unconditional regression coefficient
$\beta=0$. As long as the $\epsilon_{i}$ have an absolutely continuous density
with respect to the Lebesgue measure on $\mathbb{R}^{d+1}$, it follows that,
by Theorem 1 of Mokkadem, (1988), the sequence $\\{Z_{n}\\}$ is geometrically
$\beta$-mixing, and so the conditions of Theorem 3.2 are satisfied. In
particular, for any $\alpha\in(0,\,1)$, for any choice of null region $A$ as
described in Remark 3.3, the permutation test of the null hypothesis $H_{0}$
with null region $A$ will be asymptotically valid at the nominal level
$\alpha$.

######  Remark 3.4.

Note that Theorem 3.2 also permits for the inclusion of lagged regressor
variables; indeed, consider $\\{(Y_{i},\,X_{i}):i\in[n]\\}$ in the setting of
Theorem 3.2. We may, for instance, introduce a new column to the data matrix
$X$, of the form

$X_{i,\,p+1}=X_{i-1,\,1}\,\,.$

The mixing and moment conditions of Theorem 3.2 still hold for the updated
versions of the $X_{i}$, and so we may perform analogous inference with the
inclusion of this new regressor.

######  Example 3.2.

(Ljung-Box permutation test) Let $\\{T_{n}:n\in\mathbb{N}\\}$ be a real-
valued, stationary, $\alpha$-mixing sequence satisfying the moment and mixing
conditions of Theorem 3.2. Let $p\in\mathbb{N}$, and, for each
$n\in\mathbb{N}$ and $j\in[p]$, let

$\displaystyle Y_{n}$ $\displaystyle=\frac{T_{n+p}}{\hat{\sigma}_{T}}$
$\displaystyle X_{n,\,j}$
$\displaystyle=\frac{T_{n+p-j}}{\hat{\sigma}_{T}}\,\,,$

where $\hat{\sigma}_{T}$ is the sample variance of $\\{T_{i}:i\in[n]\\}$. The
sequence $\\{Z_{n}=\hat{\sigma}_{T}(Y_{n},\,X_{n}):n\in\mathbb{N}\\}$
satisfies the mixing and moment conditions of Theorem 3.2, and
$\hat{\sigma}_{T}$ is invariant under permutations. Hence we may apply Remark
3.4, to construct a permutation test analogous to the Ljung-Box test. To be
precise, consider a hypothesis test of the hypothesis

$H:\rho_{1}=\dots=\rho_{p}=0\,\,,$

where $\rho_{j}$ is the $j$th order autocorrelation of the sequence
$\\{T_{n}:n\in\mathbb{N}\\}$. Let

$\hat{\rho}_{n}=(\hat{\rho}_{n,\,1},\,\dots,\,\hat{\rho}_{n,\,p})\,\,,$

where $\hat{\rho}_{n,\,j}$ is the $j$th sample autocorrelation of the sequence
$\\{T_{i}:i\in[n+p]\\}$. Since the sample variance of the $T_{i}$ is invariant
under permutations, by Theorem 3.2, the permutation test based on the test
statistic

$\sqrt{n}\hat{\Gamma}_{n}^{-1/2}\hat{\rho}_{n}\,\,,$

which rejects for large values of the statistic

$n\hat{\rho}_{n}^{T}\hat{\Gamma}_{n}^{-1}\hat{\rho}_{n}\,\,,$

is an asymptotically valid test of $H$ at the nominal level $\alpha$. While
this is not exactly of the same form as the Ljung-Box test, this is similar,
in the sense that the test statistic is a quadratic form of the sample
autocorrelations.

######  Example 3.3.

(Testing for cross-correlations) Let
$\\{(\tilde{Y}_{n},\,\tilde{X}_{n}):n\in\mathbb{N}\\}$ be as in Theorem 3.2.
Consider a test of the null hypothesis

$H:\rho_{\tilde{Y},\,\tilde{X}_{1}}=\dots=\rho_{\tilde{Y},\,\tilde{X}_{p}}=0\,\,,$

where, for each $j\in[p]$,
$\rho(\tilde{Y},\,\tilde{X}_{j})=\text{corr}(\tilde{Y}_{1},\,\tilde{X}_{1,\,j})$.

As in Example 3.2, since, for each $j\in[p]$, the coordinate-wise $j$th sample
variance

$\hat{\sigma}_{n,\,j}^{2}=\frac{1}{n}\sum_{i=1}^{n}(\tilde{X}_{i,\,j}-\bar{\tilde{X}}_{n,\,j})^{2}$

is permutation invariant, we may construct a test of $H$ based on
permutations. Indeed, for each $i\in[n]$ and $j\in[p]$, let

$\displaystyle Y_{i}$
$\displaystyle=\frac{\tilde{Y}_{i}}{\hat{\sigma}_{n,\,Y}}$ $\displaystyle
X_{i,\,j}$ $\displaystyle=\frac{\tilde{X}_{i}}{\hat{\sigma}_{n,\,j}}\,\,.$

Also, let

$\hat{\rho}_{n}=(\hat{\rho}_{n,\,1},\,\dots,\,\hat{\rho}_{n,\,p})\,\,,$

where, for each $j\in[p]$, $\hat{\rho}_{n,\,j}$ is the sample correlation
between $\\{Y_{i}:i\in[n]\\}$ and $\\{X_{i,\,j}:i\in[n]\\}$. We have that the
permutation test based on the test statistic

$\sqrt{n}\hat{\Gamma}_{n}^{-1/2}\hat{\rho}_{n}\,\,,$

which rejects for large values of the test statistic

$n\hat{\rho}_{n}^{T}\hat{\Gamma}_{n}^{-1}\hat{\rho}_{n}\,\,,$

will result in an asymptotically valid two-sided test of $H$ at the nominal
level $\alpha$. Note also that, by Remark 3.4, such a test may also be used to
test whether lagged cross-correlations of the form

$\rho_{\tilde{Y},\tilde{X}_{j},\,r}=\text{corr}(\tilde{Y}_{1},\,\tilde{X}_{1+r,\,j})$

are significantly different from zero.

##  4 Testing for monotone trend using least squares

In this section, we consider the nonparametric regression model

$Y_{n,\,i}=X_{n,\,i}+\lambda_{n,\,i}\,\,,$

where $\\{X_{n,\,i}:n\in\mathbb{N}\\}$ is a row-wise stationary triangular
array of $\alpha$-mixing real-valued random variables, and
$\\{\lambda_{n,\,i}:n\in\mathbb{N},\,i\in[n]\\}$ is a triangular array of
real-valued constants such that

$\lambda_{n,\,i}=g\left(\frac{i}{n}\right)$

for some continuous monotone function $g$. In particular, we focus on testing
the null hypothesis that the triangular array $\\{Y_{n,\,i}\\}$ does not
exhibit any monotone trend, i.e.

$H_{0}^{(m)}:g(x)\equiv C\text{ for all }x\in[0,\,1]\,\,.$

using a permutation testing procedure based on a possibly studentized version
of the sample regression coefficient obtained when regressing the sequence
$\\{Y_{i}:i\in[n]\\}$ on the index $\\{i:i\in[n]\\}$, i.e.

$\hat{\beta}_{n}=\frac{1}{\sum_{i=1}^{n}\left(i-\frac{n+1}{2}\right)^{2}}\sum_{i=1}^{n}\left(i-\frac{n+1}{2}\right)(Y_{i}-\bar{Y}_{n})\,\,.$

Under the additional assumption that the triangular array $\\{X_{n,\,i}\\}$ is
row-wise i.i.d., the randomization hypothesis holds, and so the permutation
test based on any test statistic will be finite-sample exact at the nominal
level $\alpha$. However, in the more general setting of $\alpha$-mixing
sequences, the test may not be exact in finite samples, or indeed
asymptotically valid as $n\to\infty$. This leads to issues of a lack of Type 1
and Type 3 error control, where the permutation test may reject even when the
$\lambda_{n,\,i}$ are constant, on account of the triangular array of errors
$X_{n,\,i}$ not being independent and identically distributed.

Before we may commence closer examination of these issues, we provide some
preliminary definitions and results, in addition to a brief discussion of the
choice of problem setting.

###  4.1 Preliminaries

In this section, we establish some preliminary notation, in addition to
providing some simple preliminary results and a central limit theorem for the
limiting distribution of the test statistic.

We begin with some preliminary notation, to be used throughout the remainder
of this section. In the problem setting

$Y_{n,\,i}=X_{n,\,i}+\lambda_{n,\,i}\,\,,$

for each $n\in\mathbb{N}$, let

$\displaystyle\bar{X}_{n}$ $\displaystyle=\frac{1}{n}\sum_{i=1}^{n}X_{n,\,i}$
$\displaystyle\bar{\lambda}_{n}$
$\displaystyle=\frac{1}{n}\sum_{i=1}\lambda_{n,\,i}$
$\displaystyle\bar{Y}_{n}$ $\displaystyle=\frac{1}{n}\sum_{i=1}^{n}Y_{n,\,i}$

We now provide a simple lemma to motivate the choice of test statistic.

######  Lemma 4.1.

Let $g:[0,\,1]\to\mathbb{R}$ be a continuous and nondecreasing. Then

$\int_{0}^{1}xg(x){\rm{d}}x\geq\frac{1}{2}\int_{0}^{1}g(x){\rm{d}}x$

with equality if and only if $g$ is constant.

###### Proof.

Let

$G(x)=\int_{0}^{x}g(u){\rm{d}}u\,\,.$

Note that, since $g$ is continuous and nondecreasing, it follows that
$G(x)\leq xg(x)$ for all $x$, with strict inequality for some $x\in[0,\,1]$
unless $g$ is constant. Integrating by parts, we have that

$\displaystyle\int_{0}^{1}xg(x){\rm{d}}x$
$\displaystyle=\int_{0}^{1}g(x){\rm{d}}x-\int_{0}^{1}G(x){\rm{d}}x$
$\displaystyle\geq\int_{0}^{1}g(x){\rm{d}}x-\int_{0}^{1}xg(x){\rm{d}}x$
$\displaystyle\implies\int_{0}^{1}xg(x){\rm{d}}x$
$\displaystyle\geq\frac{1}{2}\int_{0}^{1}g(x){\rm{d}}x\,\,,$

with equality if and only if $xg(x)=G(x)$ for all $x$, i.e. $g$ is constant.

######  Remark 4.1.

By an identical argument, we have that, for $g$ a continuous and nonincreasing
function on $[0,\,1]$,

$\int_{0}^{1}xg(x){\rm{d}}x\leq\frac{1}{2}\int_{0}^{1}g(x){\rm{d}}x\,\,,$

with equality if and only if $g$ is constant.

######  Remark 4.2.

We observe that

$\displaystyle\mathbb{E}[\hat{\beta}_{n}]$
$\displaystyle=\frac{12}{n(n^{2}-1)}\sum_{i=1}^{n}\left(i-\frac{n+1}{2}\right)(\lambda_{n,\,i}-\bar{\lambda}_{n})$
$\displaystyle=\frac{12}{n^{2}-1}\left(\sum_{i=1}^{n}\frac{i}{n}\cdot\lambda_{i,\,n}-\frac{n+1}{2}\bar{\lambda}_{n}\right)$
$\displaystyle=\frac{12n}{n^{2}-1}\left(\int_{0}^{1}xg(x){\rm{d}}x-\frac{1}{2}\int_{0}^{1}g(x){\rm{d}}x+o(1)\right)\,\,,$

where the last line follows since, for a bounded continuous function $f$, the
Riemann sums of the function $f$ over an interval $[a,\,b]$ converge to the
Lebesgue integral over $[a,\,b]$. In particular, it follows that, to first
order, the mean of the regression coefficient $\hat{\beta}_{n}$ will be
greater than or less than zero if and only if $g$ is strictly monotone
increasing or decreasing, respectively.

We now provide a result furnishing the asymptotic distribution of the test
statistic.

######  Theorem 4.1.

Let $\\{X_{n,\,i}:n\in\mathbb{N},\,i\in[n]\\}$ be a row-wise strictly
stationary, mean zero, $\alpha$-mixing triangular array of real-valued random
variables such that, for all $n\in\mathbb{N}$, for some $\delta>0$ and some
constant $K>0$,

$\mathbb{E}\left[\left|X_{n,\,i}\right|^{2+\delta}\right]\leq K$

and, for some $C>0$,

$\sum_{j=1}^{n-1}\alpha_{X_{n,\,\cdot}}(j)^{\frac{\delta}{2+\delta}}\leq
C\,\,.$

Suppose also that there exists $\tau^{2}>0$ such that, as $n\to\infty$,

$\text{Var}(X_{n,\,1})+2\sum_{i=1}^{n-1}\text{Cov}(X_{n,\,1},\,X_{n,\,1+i})\to\tau^{2}\,\,.$
(4.1)

For each $n\in\mathbb{N}$ and $i\in[n]$, let

$Y_{n,\,i}=X_{n,\,i}+\lambda_{n,\,i}\,\,,$

where $\\{\lambda_{n,\,i}:n\in\mathbb{N},\,i\in[n]\\}\subset\mathbb{R}$ is a
triangular array of constants. Then, as $n\to\infty$,

$\frac{1}{n^{3/2}}\sum_{i=1}^{n}\left(i-\frac{n+1}{2}\right)(Y_{n,\,i}-\bar{Y}_{n})-\frac{1}{n^{3/2}}\left(\sum_{i=1}^{n}i\lambda_{n,\,i}-\frac{n(n+1)}{2}\bar{\lambda}_{n}\right)\overset{d}{\to}N(0,\,\tilde{\tau}^{2})\,\,,$

where

$\tilde{\tau}^{2}=\frac{1}{12}\tau^{2}\,\,.$

######  Remark 4.3.

Since the $\lambda_{n,\,i}$ are a sequence of constants, it follows that
$\text{Var}(X_{n,\,1})=\text{Var}(Y_{n,\,1})$, and, for all $j\geq 2$,
$\text{Cov}(X_{n,\,1},\,X_{n,\,j})=\text{Cov}(Y_{n,\,1},\,Y_{n,\,j})$.

###  4.2 Discussion of the problem setting

In this section, we make some smoothness assumptions on the additive constants
$\lambda_{n,\,i}$; in particular, we assume that the $\lambda_{n,\,i}$ may be
written as

$\lambda_{n,\,i}=g\left(\frac{i}{n}\right)$

for some continuous monotone function $g$, which is accompanied by the
implicit assumption that $g:[0,\,1]\to\mathbb{R}$ is bounded on $[0,\,1]$.
These assumptions are similar to those made on in the setting of Wang et al.,
(2008). The reader may wonder why we have imposed such a restriction on the
triangular array of sequences $\\{Y_{n,\,i}:n\in\mathbb{N},\,i\in[n]\\}$, when
a more natural choice of problem setting would be to consider the sequence

$Y_{n}=X_{n}+\lambda_{n}\,\,,$ (4.2)

for $\\{X_{n}:n\in\mathbb{N}\\}$ a sequence of real-valued, mean zero,
$\alpha$-mixing random variables, and
$\\{\lambda_{n}:n\in\mathbb{N}\\}\subset\mathbb{R}$ a monotone sequence of
constants.

The reasoning behind this is as follows. In essence, without restriction of
the space of additive constants to the form provided, we may not perform a
permutation test which is asymptotically consistent. In order to provide a
pathological example of the issues that may occur without this added
restriction, we provide the following lemma.

######  Lemma 4.2.

Let $n\in\mathbb{N}$, and let $\\{a_{i}:i\in[n]\\}$ and $\\{b_{i}:i\in[n]\\}$
be nonnegative and nondecreasing sequences of real numbers. Then, for all
$\pi_{n}\in S_{n}$,

$\sum_{i=1}^{n}a_{i}b_{\pi_{n}(i)}\leq\sum_{i=1}^{n}a_{i}b_{i}\,\,.$

###### Proof.

We prove the claim by induction on $n$. The lemma holds trivially for $n=1$.
Let $n=2$. We have that

$\displaystyle(a_{2}-a_{1})(b_{2}-b_{1})$ $\displaystyle\geq 0$ $\displaystyle
a_{1}b_{1}+a_{2}b_{2}$ $\displaystyle\geq a_{1}b_{2}+a_{2}b_{1}\,\,,$

and so the claim holds for $n=2$. We now prove the inductive hypothesis. Let
$n\geq 3$, and suppose the claim holds for all $k\in\\{2,\,\dots,\,n-1\\}$.
Let $\pi_{n}\in S_{n}$. Suppose that $\pi_{n}(n)=j$. If $j=n$, the result
follows immediately from the inductive hypothesis.

If $1<j<n$, we may apply the inductive hypothesis to the sequences
$\\{a_{i}:i\in[n-1]\\}$ and
$\\{b_{1},\,\dots,\,b_{j-1},\,b_{j+1},\,\dots,\,b_{n}\\}$, and so

$\displaystyle\sum_{i=1}^{n}a_{i}b_{\pi_{n}(i)}$
$\displaystyle=a_{n}b_{j}+\sum_{i=1}^{n-1}a_{i}b_{\pi_{n}(i)}$
$\displaystyle\leq
a_{n}b_{j}+\sum_{i=1}^{j-1}a_{i}b_{i}+\sum_{i=j+1}^{n-1}a_{i}b_{i+1}\,\,.$

A further application of the inductive hypothesis to the sequences
$\\{a_{j+1},\,\dots,\,a_{n}\\}$ and $\\{b_{j+1},\,\dots,\,b_{n}\\}$ concludes
the proof in this case.

If $j=1$, by the inductive hypothesis applied to the sequences
$\\{a_{1},\,\dots,\,a_{n-1}\\}$ and $\\{b_{2},\,\dots,\,b_{n}\\}$, it follows
that

$\displaystyle\sum_{i=1}^{n}a_{i}b_{\pi_{n}(i)}-\sum_{i=1}^{n}a_{i}b_{i}$
$\displaystyle\leq
a_{n}b_{1}+\sum_{i=1}^{n-1}a_{i}b_{i+1}-\sum_{i=1}^{n}a_{i}b_{i}$
$\displaystyle=\sum_{i=1}^{n-1}a_{i}(b_{i+1}-b_{i})+a_{n}(b_{1}-b_{n})$
$\displaystyle\leq\sum_{i=1}^{n-1}a_{n}(b_{i+1}-b_{i})+a_{n}(b_{1}-b_{n})$
$\displaystyle=0\,\,.$

It therefore follows that the result holds for $k=n$, thus concluding the
proof.

With this lemma in hand, we may now provide an example of the degenerate
behavior that may occur in a more general setting.

######  Example 4.1.

(Deterministic, fast-growing sequence) Consider the setting (4.2) in which
$X_{n}\equiv 0$ for all $n\in\mathbb{N}$, and the constants $\lambda_{n}$
satisfy, as $n\to\infty$,

$\frac{n\sum_{i=1}^{n-1}\lambda_{i}}{\lambda_{n}}=o(1)\,\,.$ (4.3)

For instance, we may consider the sequence defined by $\lambda_{1}=1$, and,
for $n\geq 2$, $\lambda_{n}=\exp(\exp(\lambda_{n-1}))$. For such a sequence,
the sample regression coefficient is equal to

$\hat{\beta}_{n}=\frac{6}{n^{2}}\lambda_{n}(1+o(1))\,\,.$

Let $\Pi_{n}\sim\text{Unif}(S_{n})$. We have that

$\hat{\beta}_{\Pi_{n}}=\frac{12}{n^{3}}\left(\Pi_{n}^{-1}(i)-\frac{n+1}{2}\right)\lambda_{n}(1+o(1))\,\,.$

In particular, it follows that, for $n$ sufficiently large, the permutation
distribution $\hat{R}_{n}$, based on the test statistic $\hat{\beta}_{n}$, is
approximately equal to the uniform distribution on the set
$\\{12(i-(n+1)/2)/n^{3}:i\in[n]\\}$, and so has variance $\sigma^{2}$
approximately equal to

$\sigma^{2}\approx\frac{12}{n^{6}}(n^{2}-1)=\frac{12}{n^{4}}(1+o(1))\,\,.$

In particular, since the permutation test, broadly speaking, rejects for large
values of $\hat{\beta}_{n}/\sigma$, we observe that, in this noiseless
setting, where the sequence $\\{\lambda_{n}\\}$ is clearly increasing, the
permutation test will not reject with probability close to 1 for large values
of $n$, i.e. we do not have asymptotic validity of the permutation test.

Furthermore, this is not an issue which may be easily solved by
studentization. Since the permutation test must be asymptotically valid under
the assumption that $\lambda_{n}\equiv 0$ for all $n$, examination of the
limiting variance (4.1) in Theorem 4.1 reveals that any potential
studentization factor $\hat{\tau}_{n}$ must provide some estimate of the
covariances $\text{Cov}(X_{1},\,X_{1+i})$, and so should be of the form

$\hat{\tau}_{n}^{2}=\frac{1}{n}\sum_{i=1}^{n}(Y_{n,\,i}-\bar{Y}_{n})^{2}+\frac{2}{n}\sum_{i=1}^{b_{n}}\sum_{j=1}^{n-i}(Y_{n,\,j}-\bar{Y}_{n})(Y_{n,\,j+i}-\bar{Y}_{n})\,\,.$

However, as illustrated by Lemma 4.2, this will have a very limited dampening
effect on the ratio of the value of the test statistic and the standard
deviation of the permutation distribution $\hat{\beta}_{n}/\sigma$, and will,
in fact, exacerbate the aformentioned issue, since, by Lemma 4.2, the
studentization factor is maximized for $\pi_{n}=e_{n}$, the identity
permutation.

In essence, the assumptions on the form of the $\lambda_{n,\,i}$ removes the
issues alluded to in the above example, in addition to being similar to the
requirements for convergence of a monotone nonparametric regression estimator
due to Mukerjee, (1988), in the sense that the restrictions prohibit the
existence of extremely high-leverage points in the regression setting under
consideration.

Having motivated the problem setting, we may now begin construction of a
permutation testing framework which is asymptotically valid under the null
hypothesis for weakly dependent sequences, and which is finite-sample exact
for i.i.d. triangular arrays $\\{Y_{n,\,i}\\}$.

###  4.3 The limiting permutation distribution

We begin by considering the limiting permutation distribution $\hat{R}_{n}$
based on an unstudentized version of the test statistic $\hat{\beta}_{n}$. To
this end, we provide the following result.

######  Theorem 4.2.

Let $\\{X_{n,\,i}:n\in\mathbb{N}\\}$ be a strictly stationary, mean zero
$\alpha$-mixing triangular array of real-valued random variables such that,
for some $\delta>0$, there exist constants $K,\,C\in\mathbb{R}^{+}$ such that

$\mathbb{E}\left[\left|X_{n,\,1}\right|^{2+\delta}\right]\leq K$

and

$\sum_{j=1}^{n-1}\alpha_{X_{n,\,\cdot}}(n)^{\frac{\delta}{2+\delta}}\leq
C\,\,.$

Suppose also that there exists $\sigma^{2}>0$ such that, for all
$n\in\mathbb{N}$ and $i\in[n]$,

$\text{Var}(X_{n,\,i})=\sigma^{2}\,\,.$

For each $n\in\mathbb{N}$ and $i\in[n]$, let

$Y_{n,\,i}=X_{n,\,i}+\lambda_{n,\,i}\,\,,$

where $\\{\lambda_{n,\,i}:n\in\mathbb{N},\,i\in[n]\\}\subset\mathbb{R}$ is a
triangular array of constants such that, as $n\to\infty$,

$\frac{1}{n}\sum_{i=1}^{n}(\lambda_{n,\,i}-\bar{\lambda}_{n})^{2}\to 0\,\,.$

Let

$T_{n}=T_{n}(Y_{n,\,1},\,\dots,\,Y_{n,\,n}):=\frac{1}{n^{\frac{3}{2}}}\sum_{i=1}^{n}\left(i-\frac{n+1}{2}\right)(Y_{n,\,i}-\bar{Y}_{n})\,\,.$

Let $\hat{R}_{n}$ be the permutation distribution, based on the test statistic
$T_{n}$, with associated group of transformations $S_{n}$. Then, as
$n\to\infty$,

$\sup_{t\in\mathbb{R}}\left|\hat{R}_{n}(t)-\Phi\left(\frac{\sqrt{12}}{\sigma}t\right)\right|\overset{p}{\to}0\,\,,$

where $\Phi$ is the standard Gaussian distribution.

######  Remark 4.4.

Note that, in this particular problem setting, we have that, as $n\to\infty$,

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}(\lambda_{n,\,i}-\bar{\lambda}_{n})^{2}$
$\displaystyle=\sum_{i=1}^{n}\frac{1}{n}\lambda_{n,\,i}^{2}-\bar{\lambda}_{n}^{2}$
$\displaystyle\to\int_{0}^{1}g(x)^{2}{\rm{d}}x-\left(\int_{0}^{1}g(x){\rm{d}}x\right)^{2}\,\,.$

We have that

$\int_{0}^{1}g(x)^{2}{\rm{d}}x-\left(\int_{0}^{1}g(x){\rm{d}}x\right)^{2}=0\iff
g(x)=C\text{ for all }x\in[0,\,1]\,\,,$

i.e. the permutation distribution only converges under the null hypothesis of
no trend.

We observe that, in general, the variance of the limiting permutation
distribution and the variance of the limiting distribution of the test
statistic are not equal. We therefore proceed to find an appropriate
studentizing factor in order to resolve this issue of mismatched variances,
using a similar argument to the one presented in Section 3 of Romano and
Tirlea, (2022).

######  Lemma 4.3.

Let $\\{X_{n,\,i}:n\in\mathbb{N}\\}$ be a strictly stationary, mean zero
$\alpha$-mixing triangular array of real-valued random variables such that,
for some $\delta>0$, there exist constants $K,\,C\in\mathbb{R}^{+}$ such that

$\mathbb{E}\left[\left|X_{n,\,1}\right|^{4+2\delta}\right]\leq K$

and

$\sum_{j=1}^{n-1}\alpha_{X_{n,\,\cdot}}(n)^{\frac{\delta}{2+\delta}}\leq
C\,\,.$

Suppose also that there exists $\sigma^{2}>0$ such that, for all
$n\in\mathbb{N}$ and $i\in[n]$,

$\text{Var}(X_{n,\,i})=\sigma^{2}\,\,,$

and that there exists $\tau^{2}>0$ such that, as $n\to\infty$,

$\text{Var}(X_{n,\,1})+2\sum_{i=1}^{n-1}\text{Cov}(X_{n,\,1},\,X_{n,\,1+i})\to\tau^{2}\,\,.$

Let $\\{b_{n}:n\in\mathbb{N}\\}\subset\mathbb{R}$ be a sequence such that
$b_{n}=o(\sqrt{n})$ and, as $n\to\infty$, $b_{n}\to\infty$. Let

$\hat{\tau}_{n}^{2}=\frac{1}{n}\sum_{i=1}^{n}(X_{n,\,i}-\bar{X}_{n})^{2}+\frac{2}{n}\sum_{i=1}^{b_{n}}\sum_{j=1}^{n-i}(X_{n,\,j}-\bar{X}_{n})(X_{n,\,j+i}-\bar{X}_{n})\,\,.$

Let $\Pi_{n}\sim\text{Unif}(S_{n})$, independent of the row
$\\{X_{n,\,i}:i\in[n]\\}$. Then the following results hold.

  1. (i)

As $n\to\infty$,

$\hat{\tau}_{n}^{2}\overset{p}{\to}\tau^{2}\,\,.$

  2. (ii)

As $n\to\infty$,

$\hat{\tau}_{\Pi_{n}}^{2}\overset{p}{\to}\sigma^{2}\,\,.$

Finally, by combining Theorem 4.1, Theorem 4.2, and Lemma 4.3 with an
application of Slutsky’s theorem and Slutsky’s theorem for randomization
distributions (Chung and Romano, (2013), Theorem 5.2), we obtain the following
result.

######  Theorem 4.3.

Let $\\{X_{n,\,i}:n\in\mathbb{N}\\}$ be a strictly stationary, mean zero
$\alpha$-mixing triangular array of real-valued random variables such that,
for some $\delta>0$, there exist constants $K,\,C\in\mathbb{R}^{+}$ such that

$\mathbb{E}\left[\left|X_{n,\,1}\right|^{4+2\delta}\right]\leq K$

and

$\sum_{j=1}^{n-1}\alpha_{X_{n,\,\cdot}}(n)^{\frac{\delta}{2+\delta}}\leq
C\,\,.$

Suppose also that there exists $\sigma^{2}>0$ such that, for all
$n\in\mathbb{N}$ and $i\in[n]$,

$\text{Var}(X_{n,\,i})=\sigma^{2}\,\,,$

and that there exists $\tau^{2}>0$ such that, as $n\to\infty$,

$\text{Var}(X_{n,\,1})+2\sum_{i=1}^{n-1}\text{Cov}(X_{n,\,1},\,X_{n,\,1+i})\to\tau^{2}\,\,.$

Let $\\{b_{n}:n\in\mathbb{N}\\}\subset\mathbb{R}$ be a sequence such that
$b_{n}=o(\sqrt{n})$ and, as $n\to\infty$, $b_{n}\to\infty$. Let

$\hat{\tau}_{n}^{2}=\frac{1}{n}\sum_{i=1}^{n}(X_{n,\,i}-\bar{X}_{n})^{2}+\frac{2}{n}\sum_{i=1}^{b_{n}}\sum_{j=1}^{n-i}(X_{n,\,j}-\bar{X}_{n})(X_{n,\,j+i}-\bar{X}_{n})\,\,.$

Let

$\hat{\beta}_{n}=\frac{1}{\sum_{i=1}^{n}\left(i-\frac{n+1}{2}\right)^{2}}\sum_{i=1}^{n}\left(i-\frac{n+1}{2}\right)\left(X_{n,\,i}-\bar{X}_{n}\right)\,\,.$

Then the following results hold.

  1. (i)

As $n\to\infty$,

$\frac{n^{3/2}\hat{\beta}_{n}}{\sqrt{12}\hat{\tau}_{n}}\overset{d}{\to}N(0,\,1)\,\,.$

  2. (ii)

Let $\hat{R}_{n}$ be the permutation distribution, based on the test statistic
$n^{3/2}\hat{\beta}_{n}/(\sqrt{12}\hat{\tau}_{n})$, with associated group of
transformations $S_{n}$. Then, as $n\to\infty$,

$\sup_{t\in\mathbb{R}}\left|\hat{R}_{n}(t)-\Phi(t)\right|\overset{p}{\to}0\,\,,$

where $\Phi$ is the standard Gaussian c.d.f.

###### Proof.

(i) follows immediately from Theorem 4.1, Lemma 4.3, and Slutsky’s theorem.
(ii) follows from Theorem 4.2, Lemma 4.3, and Theorem 5.2 of Chung and Romano,
(2013).

######  Remark 4.5.

As a consequence of Theorem 4.3, the one-sided permutation test of
$H_{0}^{(m)}$, based on the test statistic
$n^{3/2}\hat{\beta}_{n}/(\sqrt{12}\hat{\tau}_{n})$ is asymptotically valid at
the nominal level $\alpha$.

######  Example 4.2.

($ARMA$ process) Let $\\{X_{n}:\,n\in\mathbb{N}\\}\subset\mathbb{R}$ satisfy
the equation

$\sum_{i=0}^{p}B_{i}X_{t-i}=\sum_{k=0}^{q}A_{k}\epsilon_{k}\,\,,$ (4.4)

where the $\epsilon_{k}$ are independent and identically distributed, and
$\mathbb{E}\epsilon_{k}=0$, i.e. $X$ is an ARMA$(p,\,q)$ process. Let

$P(z):=\sum_{i=0}^{p}B_{i}z^{i}\,\,.$ (4.5)

If the equation $P(z)=0$ has no solutions inside the unit circle
$\\{z\in\mathbb{C}:\left|z\right|\leq 1\\}$, there exists a unique stationary
solution to (4.4). By Mokkadem, (1988), Theorem 1, if the distribution of the
$\epsilon_{k}$ is absolutely continuous with respect to Lebesgue measure on
$\mathbb{R}$, and if, for some $\delta>0$,

$\mathbb{E}\left[\left|\epsilon_{1}\right|^{4+2\delta}\right]>0\,\,,$ (4.6)

we have that the sequence $\\{X_{n}:,\,n\in\mathbb{N}\\}$ satisfies the
conditions of Theorem 4.3, as long as

$\tau^{2}:=\text{Var}(X_{1})+2\sum_{n\geq 1}\text{Cov}(X_{1},X_{1+n})$ (4.7)

is finite and positive. Therefore, asymptotically, the rejection probability
of the permutation test applied to such a sequence will be equal to the
nominal level $\alpha$.

Having shown that this permutation test is asymptotically valid, we may now
consider the power of this test against local alternatives. Therefore, by an
application of Theorem 4.1, we have the following.

######  Theorem 4.4.

In the setting of Theorem 4.3, let
$\\{\lambda_{n,\,i}:n\in\mathbb{N},\,i\in[n]\\}\subset\mathbb{R}$ be a
triangular array of strictly increasing constants. Let

$Y_{n,\,i}=X_{n,\,i}+\lambda_{n,\,i}\,\,.$

Let $\mathbb{P}_{n}$ be the measure induced by the row
$\\{X_{n,\,i}:i\in[n]\\}$, and let $\mathbb{Q}_{n}$ be the measure induced by
the row $\\{Y_{n,\,i}:i\in[n]\\}$. Suppose that $\\{\mathbb{Q}_{n}\\}$ is
contiguous to $\\{\mathbb{P}_{n}\\}$. Suppose further that, as $n\to\infty$,

$\frac{1}{n^{3/2}}\left(\sum_{i=1}^{n}i\lambda_{i}-\frac{n(n+1)}{2}\bar{\lambda}_{n}\right)\to\nu\,\,,$

for some $\nu\in(0,\,\infty)$. Let $\phi_{n}$ be the test function
corresponding to the permutation test of Theorem 4.3 conducted at the nominal
level $\alpha\in(0,\,1)$ on the data $\\{X_{n,\,i}:i\in[n]\\}$. Then, as
$n\to\infty$, under $\mathbb{Q}_{n}$,

$\mathbb{E}_{\mathbb{Q}_{n}}\phi_{n}\to
1-\Phi\left(z_{1-\alpha}-\frac{\nu\sqrt{12}}{\tau}\right)\,\,,$

where $\tau$ is as in (4.1), and $z_{1-\alpha}$ is the $(1-\alpha)$ quantile
of the standard Gaussian distribution.

######  Example 4.3.

(Local $AR(1)$ alternatives) Let $\rho\in(-1,\,1)$, and let
$\\{\epsilon_{n}:n\in\mathbb{N}\\}$ be an i.i.d. sequence of standard Gaussian
random variables. Let $\\{X_{n}:n\in\mathbb{N}\\}$ be the unique stationary
sequence satisfying the equation, for $n\geq 1$,

$X_{n+1}=\rho X_{n}+\epsilon_{n}\,\,,$

i.e. $\\{X_{n}\\}$ is an $AR(1)$ process. Clearly, the sequence $\\{X_{n}\\}$
has finite moments of every order. In order for $\\{X_{n}\\}$ to satisfy the
conditions of Theorem 4.3, by Example 4.2 it suffices to show that $\tau^{2}$,
as defined in (4.7), is strictly positive. We have that, for $n\geq 1$,

$\displaystyle\text{Var}(X_{1})$ $\displaystyle=\frac{1}{1-\rho^{2}}$
$\displaystyle\text{Cov}(X_{1},\,X_{1+n})$
$\displaystyle=\frac{\rho^{n}}{1-\rho^{2}}\,\,,$

and so

$\displaystyle\tau^{2}$
$\displaystyle=\frac{1}{1-\rho^{2}}\left(1+2\sum_{n\geq 1}\rho^{k}\right)$
$\displaystyle=\frac{1}{(1-\rho)^{2}}\,\,.$

Let $h>0$. Consider the triangular array, for $n\in\mathbb{N}$ and $i\in[n]$,

$\lambda_{n,\,i}=\frac{hi}{n^{3/2}}\,\,.$

Note that, in this setting, the triangular array $\\{\lambda_{n,\,i}\\}$
corresponds to the sequence of functions $\\{g_{n}:n\in\mathbb{N}\\}$ given by
$g_{n}:[0,\ ,1]\to\mathbb{R}$,

$g_{n}(x)=\frac{1}{\sqrt{n}}x\,\,.$

Consider the one-sided permutation test of the null hypothesis $H_{0}^{(m)}$.
In the setting of Theorem 4.4, let $X_{n,\,i}=X_{i}$, and let
$Y_{n,\,i}=X_{n,\,i}+\lambda_{n,\,i}$. Let
$\\{\mathbb{P}_{n}:n\in\mathbb{N}\\}$ and
$\\{\mathbb{Q}_{n}:n\in\mathbb{N}\\}$ be as defined in Theorem 4.4. Let
$l_{n}$ be the corresponding log-likelihood ratio. Let $\mu$ be Lebesgue
measure on $\mathbb{R}$. We have that

$\displaystyle l_{n}:$
$\displaystyle=\log\left(\frac{{\rm{d}}\mathbb{Q}_{n}}{{\rm{d}}\mathbb{P}_{n}}\right)$
$\displaystyle=\log\left(\frac{{\rm{d}}\mathbb{Q}_{n}}{{\rm{d}}\mu}(Y_{n,\,1},\,\dots,\,Y_{n,\,n})\right)-\log\left(\frac{{\rm{d}}\mathbb{P}_{n}}{{\rm{d}}\mu}(X_{n,\,1},\,\dots,\,X_{n,\,n})\right)$
$\displaystyle=\frac{1}{2(1-\rho^{2})}\left[-\left(X_{n,\,1}-\lambda_{n,\,1}\right)^{2}-\sum_{i=2}^{n}\left(X_{n,\,i}-\rho
X_{n,\,i-1}-\rho\lambda_{n,\,i-1}-\lambda_{n,\,i}\right)^{2}+X_{n,\,1}^{2}+\sum_{i=2}^{n}\left(X_{n,\,i}-\rho
X_{n,\,i-1}\right)^{2}\right]$
$\displaystyle=\frac{1}{2(1-\rho^{2})}\left[2\lambda_{n,\,1}X_{1}+2\sum_{i=2}^{n}(X_{i}-\rho
X_{i-1})(\lambda_{n,\,i}-\rho\lambda_{n,\,i-1})-\lambda_{n,\,1}^{2}-\sum_{i=2}^{n}(\lambda_{n,\,i}-\rho\lambda_{n,\,i-1})^{2}\right]$
$\displaystyle=\frac{1}{1-\rho^{2}}\left[\left(\lambda_{n,\,1}(1+\rho^{2})-\rho\lambda_{n,\,2}\right)X_{1}+\sum_{i=2}^{n-1}\left((1+\rho^{2})\lambda_{n,\,i}-\rho(\lambda_{n,\,i-1}+\lambda_{n,\,i+1})\right)X_{i}+X_{n}(\lambda_{n,\,n}-\rho\lambda_{n,\,n-1})\right]-$
$\displaystyle-\frac{1}{2(1-\rho^{2})}\left[\lambda_{n,\,1}^{2}-\sum_{i=2}^{n}(\lambda_{n,\,i}-\rho\lambda_{n,\,i-1})^{2}\right]$
$\displaystyle=\frac{1}{(1-\rho^{2})}\left[-\frac{1}{2}\left(\lambda_{n,\,1}^{2}-\sum_{i=2}^{n}(\lambda_{n,\,i}-\rho\lambda_{n,\,i-1})^{2}\right)+\sum_{i=2}^{n}(1-\rho)^{2}\lambda_{n,\,i}X_{i}\right]+o_{p}(1)\,\,.$

Letting $\lambda_{n,\,0}=0$, we have that

$\displaystyle\sum_{i=1}^{n}(\lambda_{n,\,i}-\rho\lambda_{n,\,i-1})^{2}$
$\displaystyle=\sum_{i=1}^{n}\frac{h^{2}i^{2}}{n^{3}}-2\rho\sum_{i=1}^{n}\frac{h^{2}i(i-1)}{n^{3}}+\rho^{2}\sum_{i=1}^{n-1}\frac{h^{2}i^{2}}{n^{3}}$
$\displaystyle=\frac{h^{2}}{n^{3}}\left(\frac{n(n+1)(2n+1)}{6}-2\rho\cdot\frac{n(n^{2}-1)}{3}+\rho^{2}\frac{(n-1)n(2n-1)}{6}\right)$
$\displaystyle=\frac{h^{2}}{3}(1-\rho)^{2}\left(1+o(1)\right)\,\,.$

By an analogous argument to the one presented in the proof of Theorem 4.1, we
have that

$\sum_{i=1}^{n}\lambda_{n,\,i}X_{i}\overset{d}{\to}N\left(0,\,\frac{h^{2}}{3}\tau^{2}\right)\,\,.$

In particular, it follows that, under $\mathbb{P}_{n}$, by Slutsky’s theorem,

$l_{n}\overset{d}{\to}N\left(-\frac{h^{2}}{6}(1-\rho)^{2},\,\frac{h^{2}}{3}(1-\rho)^{2}\right)\,\,.$

Therefore, by Le Cam’s First Lemma (see Lehmann and Romano, (2022), Theorem
14.3.1 and Corollary 14.3.1), we have that $\\{\mathbb{Q}_{n}\\}$ and
$\\{\mathbb{P}_{n}\\}$ are mutually contiguous. Therefore we may apply Theorem
4.4 in this setting. It remains to compute $\nu$ as defined in Theorem 4.4; we
have that

$\displaystyle\frac{1}{n^{3/2}}\left(\sum_{i=1}^{n}i\lambda_{n,\,i}-\frac{n(n+1)}{2}\bar{\lambda}_{n}\right)$
$\displaystyle=\frac{h}{n^{3}}\left(\frac{1}{3}n^{3}-\frac{1}{4}n^{3}\right)+o(1)$
$\displaystyle=\frac{h}{12}+o(1)\,\,.$

It therefore follows that, in this setting, the local limiting power function
of the nominal level $\alpha$ one-sided permutation test is given by

$\mathbb{E}_{\mathbb{Q}_{n}}[\phi_{n}]\to
1-\Phi\left(z_{1-\alpha}-\frac{h(1-\rho)^{2}}{\sqrt{12}}\right)\,\,,$

as $n\to\infty$.

##  5 Simulation results

In this section, we provide Monte Carlo simulations illustrating our results.
Subsection 5.1 provides simulation results of the performance of the
multivariate least squares permutation test for the unconditional regression
coefficient, and Subsection 5.2 illustrates the performance of the OLS-based
test for monotone trend. In both sections, we consider tests conducted at the
nominal level $\alpha=0.05$. The simulation results confirm that the two
permutation tests are valid in that, in large samples, the rejection
probability under the null hypothesis is approximately equal to $\alpha$.

###  5.1 Testing for regression coefficients

In this subsection, we provide simulation results for tests of significance in
the OLS regression setting. In particular, we provide a comparison of the
performance of the two-sided studentized permutation test for significance
against the classical two-sided Chi-squared test for significance. As a
review, in classical OLS theory, we assume the approximate distribution

$\sqrt{n}(\hat{\beta}_{n}-\beta)\sim
N\left(0,\,\sigma_{Y}^{2}\Sigma_{X}^{-1}\right)\,\,.$

Subsequently, the classical Chi-squared test computes the statistic

$C_{n}=C_{n}((Y_{1},\,X_{1}),\,\dots\,(Y_{n},\,X_{n}))=\frac{n}{\hat{\sigma}_{Y}^{2}}\hat{\beta}_{n}^{T}\hat{\Sigma}_{X}^{-1}\hat{\beta}_{n}\,\,,$

and, under the null hypothesis $H_{0}$, $R_{n}$ is approximately distributed
according to the $\chi_{p}^{2}$ distribution, and so the test compares $R_{n}$
to the $(1-\alpha)$ quantile of the $\chi_{p}^{2}$ distribution in order to
reject or not reject the null hypothesis. We compare the simulated rejection
probabilities of the studentized permutation test with the choice of spherical
rejection region $A$ in Remark 3.3; to be precise, we consider the permutation
test based on the test statistic

$\tilde{C}_{n}=n\hat{\beta}_{n}^{T}\hat{\Sigma}_{X}\hat{\Gamma}_{n}^{-1}\hat{\Sigma}_{X}\hat{\beta}_{n}\,\,.$

Note that, as a result of Theorem 3.2, under $H_{0}$, the permutation
distribution based on the unstudentized sample regression coefficient
$\sqrt{n}\hat{\beta}_{n}$ converges weakly in probability to the same limiting
distribution as $\sqrt{n}\hat{\beta}_{n}$ under the additional assumption that
the sequence $\\{X_{n}:n\in\mathbb{N}\\}$ is i.i.d. and independent of
$\\{Y_{n}:n\in\mathbb{N}\\}$. It follows that the unstudentized permutation
test will exhibit the same limiting behavior as the classic Chi-squared test
of significance, and so we omit simulation of its rejection probabilities in
the following analysis.

In this simulation, we consider the following two settings. In Table 5.1, we
consider processes of the following form. Let $p,\,m\in\mathbb{N}$. Let
$\\{\xi_{n}:n\in\mathbb{N}\\}$ and
$\\{\xi_{n,\,i}^{\prime}:n\in\mathbb{N},\,i\in[p+1]\\}$ be two independent
sequences of i.i.d. standard Gaussian random variables. For each
$n\in\mathbb{N}$, let

$T_{n}=\prod_{j=0}^{m-1}\xi_{n+j}\,\,.$

For each $n\in\mathbb{N}$ and $i\in[p]$, let

$\displaystyle Y_{n}=T_{n}\xi^{\prime}_{n,\,p+1}$ $\displaystyle
X_{n,\,i}=T_{n}\xi^{\prime}_{n,\,i}\,\,.$

We observe that the sequence
$\\{Z_{n}=(Y_{n},\,X_{n}):n\in\mathbb{N}\\}\subset\mathbb{R}^{p+1}$ is
$m$-dependent and stationary, and also that the $Z_{i}$ have finite moments of
every order. In particular, it follows that the conditions of Theorem 3.2
apply, and, since $\text{Cov}(Y_{1},\,X_{1})=0$, we have that $\beta=0$.
Therefore the asymptotic rejection probability of such a test in this
situation should be equal to the nominal level $\alpha$.

$m$ | $n$ | 50 | 100 | 500 | 1,000 | 10,000
---|---|---|---|---|---|---
0 | Stud. Perm. | 0.043 | 0.051 | 0.067 | 0.047 | 0.049
Classical Chi-Sq. | 0.045 | 0.039 | 0.046 | 0.053 | 0.054
1 | Stud. Perm. | 0.139 | 0.158 | 0.121 | 0.098 | 0.070
Classical Chi-Sq. | 0.677 | 0.716 | 0.772 | 0.800 | 0.833
2 | Stud. Perm. | 0.222 | 0.218 | 0.211 | 0.176 | 0.082
Classical Chi-Sq. | 0.802 | 0.857 | 0.915 | 0.934 | 0.951
3 | Stud. Perm. | 0.287 | 0.286 | 0.281 | 0.258 | 0.113
Classical Chi-Sq. | 0.848 | 0.890 | 0.957 | 0.983 | 0.985
Table 5.1: Monte Carlo simulation results for null rejection probabilities for
tests of $H_{0}:\beta=0$, in an $m$-dependent Gaussian product setting with
$p=3$.

We observe that, in the case of $m=0$, the classical OLS assumptions hold, and
it follows that the classical Chi-squared test controls the probability of
Type 1 error at the nominal level $\alpha$. However, for $m>0$, we observe
that the classical Chi-squared test has rejection probabilities far exceeding
the nominal level $\alpha=0.05$. The performance of the studentized
permutation test is significantly better in comparison although, for larger
values of $m$, the simulated rejection probability is still above the nominal
level $\alpha$. However, we observe that the simulated rejection probabilities
approach the nominal level as the sample size $n$ increases, and it is
expected that the performance would improve for larger values of $n$. To
illustrate this further, Figure 5.1 plots the empirical distribution of the
test statistic for different values of $n$.

---
Figure 5.1: Plots of the empirical c.d.f.s of the studentized test statistic
$n\hat{\beta}_{n}^{T}\hat{\Sigma}_{X}\hat{\Gamma}_{n}^{-1}\hat{\Sigma}_{X}\hat{\beta}_{n}$
for different values of $n$, in the $m$-dependent setting with $m=3$ and
$p=3$.

Additionally, Table 5.2 provides simulations in a $VAR(2)$ setting described
in Example 3.1. To be precise, let $\rho\in(-1,\,1)$, and let

$\displaystyle Q$
$\displaystyle=\begin{pmatrix}\frac{1}{\sqrt{3}}&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{6}}\\\
\frac{1}{\sqrt{3}}&-\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{6}}\\\
\frac{1}{\sqrt{3}}&0&-\frac{2}{\sqrt{6}}\end{pmatrix}$ $\displaystyle D$
$\displaystyle=\begin{pmatrix}\rho&0&0\\\ 0&\rho&0\\\ 0&0&-\rho\end{pmatrix}$
$\displaystyle R$ $\displaystyle=QDQ^{T}$

Let $\\{\epsilon_{n}:n\in\mathbb{N}\\}\subset\mathbb{R}^{3}$ be an i.i.d.
sequence of standard trivariate Gaussian random variables, and let
$\\{X_{n}:n\in\mathbb{N}\\}\subset\mathbb{R}^{3}$ be the stationary process
satisfying the $VAR(2)$ equation, for all $n\geq 3$,

$X_{n}=RX_{n-2}+\epsilon_{n}\,\,.$

The sequence $\\{X_{n}\\}$ is indeed stationary since, by construction, the
matrix $Q$ is orthogonal, and so $D$ is exactly the matrix of the eigenvalues
of $R$. Having appropriately defined $\\{X_{n}\\}$, let

$Y_{n}=X_{n+1,\,1}\,\,.$

By Example 3.1, the sequence $\\{X_{n}\\}$ satisfies the conditions of Theorem
3.2. Since the $\alpha$-mixing coefficients of the sequence
$\\{Z_{n}=(Y_{n},\,X_{n}):n\in\mathbb{N}\\}$ satisfy, for all
$n\in\mathbb{N}$, $\alpha_{Z}(n)=\alpha_{X}(n-1)$, and the $Z_{i}$ form a
stationary sequence with finite moments of every order, it follows that we may
apply the result of Theorem 3.2 in this setting. Also, since $X_{2n-1}$ and
$X_{2n}$ are independent for all $n\in\mathbb{N}$ by construction, it follows
that, in this case, the unconditional regression coefficient $\beta=0$, and so
the limiting rejection probability of the studentized permutation test
converges to the nominal level $\alpha$.

$\rho$ | $n$ | 50 | 100 | 500 | 1,000 | 10,000
---|---|---|---|---|---|---
-0.8 | Stud. Perm. | 0.037 | 0.079 | 0.044 | 0.072 | 0.051
Classical Chi-Sq. | 0.206 | 0.214 | 0.228 | 0.255 | 0.221
-0.5 | Stud. Perm. | 0.053 | 0.032 | 0.044 | 0.072 | 0.036
Classical Chi-Sq. | 0.051 | 0.062 | 0.053 | 0.053 | 0.076
0.5 | Stud. Perm. | 0.069 | 0.062 | 0.045 | 0.054 | 0.046
Classical Chi-Sq. | 0.136 | 0.147 | 0.180 | 0.175 | 0.162
0.8 | Stud. Perm. | 0.072 | 0.086 | 0.059 | 0.148 | 0.049
Classical Chi-Sq. | 0.379 | 0.443 | 0.477 | 0.503 | 0.491
Table 5.2: Monte Carlo simulation results for null rejection probabilities for
tests of $H_{0}:\beta=0$, in a $VAR(2)$ setting, with $p=3$.

For each situation, 1,000 simulations were performed. Within each simulation,
the permutation test was calculated by randomly sampling 2,000 permutations.

We provide a brief discussion of several computation choices to be made when
performing the aforementioned testing procedure. By the results of Lemma 3.1,
for large values of $n$, the estimates $\hat{\Gamma}_{n}$ and
$\hat{\Sigma}_{X}$ will be strictly positive definite with high probability.
However, for smaller values of $n$, it may be the case that the numerical
minimal eigenvalue of $\hat{\Gamma}_{n}$ may be nonpositive, or that, at least
numerically, $\hat{\Sigma}_{X}$ may be non-positive definite, either when
computing the test statistic or the permutation distribution. The solution to
this issue implemented in the above simulations is as follows. When computing
the estimates $\hat{\Gamma}_{n}$ and $\hat{\Sigma}_{X}$, we perform a singular
value decomposition of the matrix in question, and truncate the estimated
eigenvalues at some sufficiently small numerical lower bound $\epsilon>0$. We
observe that, an appropriately small choice of $\epsilon$, i.e. for
$\lambda_{\text{min}}(A)$ denoting the minimal eigenvalue of the matrix $A$,
choosing
$\epsilon<\min\\{\lambda_{\text{min}}(\Gamma),\,\lambda_{\text{min}}(\Sigma_{X})\\}$
will still allow the result of Lemma 3.1 to hold, i.e. any inference based on
this choice of truncated studentization is still asymptotically valid. In
practice, however, the suitability of a choice of $\epsilon$ for a particular
numerical application is determined by the distribution of the sequence
$\\{Z_{n}=(Y_{n},\,X_{n}):n\in\mathbb{N}\\}$ under analysis, For the above
simulation, a constant value of $\epsilon=10^{-4}$ was used.

A further choice is that of the truncation sequence
$\\{b_{n},\,n\in\mathbb{N}\\}$ used in the definition of $\hat{\Gamma}_{n}$.
Any sequence $\\{b_{n}\\}$ such that, as $n\to\infty$, $b_{n}\to\infty$ and
$b_{n}=o\left(\sqrt{n}\right)$ is theoretically justified by Theorem 3.2,
although, in a specific setting, some choices of $\\{b_{n}\\}$ will lead to
more numerical stability than others. In the above simulation, $\\{b_{n}\\}$
was taken to be $[n^{1/3}]+1$, where $[x]$ denotes the integer part of $x$.

###  5.2 Testing for monotone trend using least squares

We now turn our attention to simulations involving the least squares test of
the null hypothesis $H_{0}^{(m)}$ of no monotone trend, against the
alternative

$K:g\text{ is strictly increasing.}$

Under the assumption that the sequence $\\{X_{i}:i\in[n]\\}$ is i.i.d., the
randomization hypothesis holds, and so the unstudentized least squares
permutation test will be exact in finite samples and asymptotically valid.
However, in general, the randomization hypothesis does not hold under
$H_{0}^{(m)}$, and so the unstudentized local Mann-Kendall permutation test
will not be exact or even asymptotically valid. However, by the result of
Theorem 4.2, the studentized local Mann-Kendall permutation test will be
asymptotically valid at the nominal level $\alpha$.

In order to illlustrate this behavior, we provide a comparison of the
simulated rejection probabilities of the studentized and unstudentized one-
sided least squares permutation tests for lack of monotone trend in two
different settings. For both of the following situations, 1,000 simulations
were performed. Within each simulation, the permutation test was calculated by
randomly sampling 2,000 permutations.

In Table 5.3, we consider processes of the following form. Let
$m\in\mathbb{N}$. Let $\\{Z_{n}:n\in\mathbb{N}\\}$ be an i.i.d. sequence of
standard Gaussian random variables. For each $n\in\mathbb{N}$, let

$X_{n}=\prod_{j=1}^{m-1}Z_{n+j}$

We observe that the sequence $\\{X_{n}:n\in\mathbb{N}\\}$ is stationary and
$m$-dependent, and has finite moments of every order. In particular, the
triangular array $X_{n,\,i}=X_{i}$ satisfies the conditions of Theorem 4.3,
and so the one-sided studentized permutation test will be asymptotically valid
at the nominal level $\alpha$.

$m$ | $n$ | 20 | 50 | 100 | 500 | 1000
---|---|---|---|---|---|---
0 | Stud. Perm. | 0.054 | 0.046 | 0.047 | 0.039 | 0.045
Unstud. Perm. | 0.047 | 0.049 | 0.051 | 0.045 | 0.046
1 | Stud. Perm. | 0.046 | 0.051 | 0.059 | 0.047 | 0.051
Unstud. Perm. | 0.056 | 0.044 | 0.052 | 0.046 | 0.061
2 | Stud. Perm. | 0.031 | 0.048 | 0.061 | 0.049 | 0.047
Unstud. Perm. | 0.057 | 0.055 | 0.066 | 0.056 | 0.045
3 | Stud. Perm. | 0.041 | 0.034 | 0.058 | 0.047 | 0.042
Unstud. Perm. | 0.064 | 0.048 | 0.055 | 0.048 | 0.043
Table 5.3: Monte Carlo simulation results for null rejection probabilities for
tests of $H_{0}^{(m)}$, in an $m$-dependent Gaussian product setting.

While the simulation results of Table 5.3 support the theoretical asymptotic
validity of the studentized permutation test, we also observe that the
unstudentized permutation test exhibits similar Type 1 error control. This may
be explained as follows: for any choice of $m\in\mathbb{N}$, for all
$i,\,j\in\mathbb{N}$ such that $i\neq j$, we have that

$\displaystyle\text{Var}(X_{i})$ $\displaystyle=1$
$\displaystyle\text{Cov}(X_{i},\,X_{j})$ $\displaystyle=0\,\,.$

It follows that, in this particular setting, the limiting variances of the
test statistic and the limiting permutation distribution match, and so the
unstudentized permutation test is also asymptotically valid.

In Table 5.4, we consider a more traditional $AR(1)$ setting: namely, for
$\rho\in(-1,\,1)$ and $\\{\epsilon_{n}:n\in\mathbb{N}\\}$ a sequence of i.i.d.
standard Gaussian random variables, let $\\{X_{n}:n\in\mathbb{N}\\}$ be the
unique stationary sequence satisfying the equation, for all $n\in\mathbb{N}$,

$X_{n+1}=\rho X_{n}+\epsilon_{n+1}\,\,.$

By Example 4.2, the sequence $\\{X_{n}\\}$ satisfies the conditions of Theorem
4.3, and so the rejection probability of the studentized permutation test
converges to the nominal level $\alpha$ as $n\to\infty$.

$\rho$ | $n$ | 20 | 50 | 100 | 500 | 1000
---|---|---|---|---|---|---
-0.6 | Stud. Perm. | 0.191 | 0.064 | 0.140 | 0.056 | 0.041
Unstud. Perm. | 0.006 | 0.001 | 0.000 | 0.001 | 0.000
-0.2 | Stud. Perm. | 0.064 | 0.065 | 0.057 | 0.049 | 0.050
Unstud. Perm. | 0.027 | 0.017 | 0.027 | 0.020 | 0.023
0.2 | Stud. Perm. | 0.030 | 0.048 | 0.041 | 0.045 | 0.044
Unstud. Perm. | 0.089 | 0.100 | 0.085 | 0.088 | 0.089
0.6 | Stud. Perm. | 0.011 | 0.025 | 0.041 | 0.049 | 0.043
Unstud. Perm. | 0.181 | 0.215 | 0.214 | 0.200 | 0.180
Table 5.4: Monte Carlo simulation results for null rejection probabilities for
tests of $H_{0}^{(m)}$, in an $AR(1)$ setting.

We observe that, while the studentized permutation test exhibits Type 1 error
control at the nominal level $\alpha$ for all choices of $\rho$, this is not
the case for the unstudentized permutation test. Indeed, for $\rho>0$, the
rejection probability of the unstudentized permutation test is significantly
higher than the nominal level $\alpha$, i.e. we do not have Type 1 error
control. While, for $\rho<0$, the unstudentized permutation test does control
Type 1 error, the rejection probability is observed to be significantly below
the nominal level $\alpha$. This can lead to issues of Type 2 error against
local alternatives of the form described in Example 4.3, for which this test
will have power less than $\alpha$.

As in Subsection 5.1, there are several computational choices to be made in
practice. In particular, on account of the same numerical issues involving the
studentization factor $\hat{\tau}_{n}^{2}$, we truncate the variance estimate
at the lower bound $\epsilon=10^{-6}$. Similarly, we must choose a truncation
sequence $\\{b_{n}:n\in\mathbb{N}\\}$ to be used in the definition of
$\hat{\tau}_{n}^{2}$. In the above simulations, the choice $b_{n}=[n^{1/3}]+1$
was used.

##  6 Conclusions

When the fundamental assumption of exchangeability does not necessarily hold,
permutation tests are invalid unless strict conditions on underlying
parameters of the problem are satisfied. For instance, the permutation test of
$H_{0}:\beta=0$ based on the standard OLS sample regression coefficient is
asymptotically valid only when $\Sigma_{X}^{-1}\Gamma\Sigma_{X}^{-1}$, as
defined in (2.3), is equal to $\sigma^{2}_{Y}\Sigma_{X}^{-1}$. Hence rejecting
the null must be interpreted correctly, since rejection of the null with this
permutation test does not necessarily imply that the unconditional regression
coefficient $\beta$ is different from zero.

Similar issues occur in using least squares-based tests for lack of monotone
trend. Unless the assumption of exchangeability holds, a permutation test of
$H_{0}^{(m)}$ based on the sample regression coefficient $\hat{\beta}_{n}$ is
only asymptotically valid if $\tau^{2}$, as defined in (4.1), is equal to the
limiting variance of the random variables in the corresponding triangular
array, i.e. if $\tau^{2}=\lim_{n\to\infty}\text{Var}(X_{n,\,1})$. Otherwise, a
rejection of the null hypothesis $H_{0}^{(m)}$ may not necessarily imply that
the function $g$ is strictly monotone, in the sense that it may be the case
that $g$ is constant and the permutation test will reject the null hypothesis.

We provide a testing procedure that allows one to obtain asymptotic rejection
probability $\alpha$ in a permutation test setting. A significant advantage of
this test is that it achieves finite-sample exactness under the assumption of
exchangeability, which is only the case in classical OLS tests of significance
under the assumption of i.i.d. and Gaussianity, as well as achieving
asymptotic level $\alpha$ in a much wider range of settings than classical
tests of significance in OLS settings. Similarly, we provide a testing
procedure for the null hypothesis $H_{0}^{(m)}$ which is asymptotically valid
in a wide range of weakly dependent settings.

Correct implementation of a permutation test is crucial if one is interested
in confirmatory inference via hypothesis testing; indeed, proper error control
of Type 1, 2 and 3 errors can be obtained for tests of significance in linear
regression or in least-squared based tests for monotone trend by basing
inference on test statistics which are asymptotically pivotal. A framework has
been provided for tests in both of these problem settings.

## References

  * Anderson and Robinson, (2001) Anderson, M. J. and Robinson, J. (2001).  Permutation tests for linear models.  Australian & New Zealand Journal of Statistics, 43(1):75–88.
  * Chandra, (1989) Chandra, P. T. (1989).  Multidimensional Polya’s theorem.  Bulletin of the Calcutta Mathematical Society, 81:227–231.
  * Chung and Romano, (2013) Chung, E. and Romano, J. P. (2013).  Exact and asymptotically robust permutation tests.  Ann. Statist., 41(2):484–507.
  * Chung and Romano, (2016) Chung, E. and Romano, J. P. (2016).  Multivariate and multiple permutation tests.  Journal of Econometrics, 193(1):76–91.
  * DiCiccio and Romano, (2017) DiCiccio, C. J. and Romano, J. P. (2017).  Robust permutation tests for correlation and regression coefficients.  Journal of the American Statistical Association, 112(519):1211–1220.
  * Durbin, (1960) Durbin, J. (1960).  Estimation of parameters in time-series regression models.  Journal of the Royal Statistical Society. Series B (Methodological), 22(1):139–153.
  * Hemerik et al., (2021) Hemerik, J., Thoresen, M., and Finos, L. (2021).  Permutation testing in high-dimensional linear models: an empirical investigation.  Journal of Statistical Computation and Simulation, 91(5):897–914.
  * Hoeffding, (1951) Hoeffding, W. (1951).  A combinatorial central limit theorem.  The Annals of Mathematical Statistics, 22(4):558 – 566.
  * Kedem and Fokianos, (2002) Kedem, B. and Fokianos, K. (2002).  Regression Models for Time Series Analysis.  Wiley Series in Probability and Statistics. John Wiley & Sons, Nashville, TN.
  * Lehmann and Romano, (2022) Lehmann, E. L. and Romano, J. P. (2022).  Testing Statistical Hypotheses.  Springer texts in statistics. Springer Nature, 4 edition.
  * Lutkepohl, (2006) Lutkepohl, H. (2006).  New Introduction to Multiple Time Series Analysis.  Springer, Berlin, Germany, 1 edition.
  * Mokkadem, (1988) Mokkadem, A. (1988).  Mixing properties of ARMA processes.  Stochastic Processes and their Applications, 29(2):309 – 315.
  * Mukerjee, (1988) Mukerjee, H. (1988).  Monotone nonparametric regression.  The Annals of Statistics, 16(2):741 – 750.
  * Neumann, (2013) Neumann, M. H. (2013).  A central limit theorem for triangular arrays of weakly dependent random variables, with applications in statistics.  ESAIM: PS, 17:120–134.
  * Newey and West, (1987) Newey, W. K. and West, K. D. (1987).  A simple, positive semi-definite, heteroskedasticity and autocorrelation consistent covariance matrix.  Econometrica, 55(3):703–708.
  * Nyblom, (2015) Nyblom, J. (2015).  Permutation Tests in Linear Regression, pages 69–90.  Springer International Publishing, Cham.
  * Romano and Tirlea, (2022) Romano, J. P. and Tirlea, M. A. (2022).  Permutation testing for dependence in time series.  Journal of Time Series Analysis, 43:781 – 807.
  * Tran et al., (1996) Tran, L., Roussas, G., Yakowitz, S., and Van, B. T. (1996).  Fixed-design regression for linear time series.  The Annals of Statistics, 24(3):975 – 991.
  * Tsay, (1984) Tsay, R. S. (1984).  Regression models with time series errors.  Journal of the American Statistical Association, 79(385):118–124.
  * Wald and Wolfowitz, (1943) Wald, A. and Wolfowitz, J. (1943).  An exact test for randomness in the non-parametric case based on serial correlation.  Ann. Math. Statist., 14(4):378–388.
  * Wang et al., (2008) Wang, L., Akritas, M. G., and Keilegom, I. V. (2008).  An ANOVA-type nonparametric diagnostic test for heteroscedastic regression models.  Journal of Nonparametric Statistics, 20(5):365–382.
  * Wang and Keilegom, (2007) Wang, L. and Keilegom, I. V. (2007).  Nonparametric test for the form of parametric regression with time series errors.  Statistica Sinica, 17(1):369–386.
  * White, (1980) White, H. (1980).  A heteroskedasticity-consistent covariance matrix estimator and a direct test for heteroskedasticity.  Econometrica, 48(4):817–838.
  * White, (2000) White, H. (2000).  Asymptotic Theory for Econometricians.  Economic Theory, Econometrics, and Mathematical Economics. Academic Press, San Diego, CA, 2 edition.