CHANGEPOINT DETECTION USING NONPARAMETRIC PROCEDURES

Sivanandan Balakumar

Abstract. This study investigates the detection of a changepoint due to location or scale or both location and scale changes in a sequence of univariate random variables. Two changepoint models, namely, the single change and the continuous change are considered and the appropriate test statistics are derived. The proposed test statistics are functions of two linear rank statistics, of which one is odd–translation invariant, sensitive to location shift and the other one is even– translation invariant, sensitive to scale shift. The asymptotic distributions of the proposed statistics are obtained under the null hypothesis.

1. Introduction. In this paper a nonparametric procedure for the problem of testing for location or scale or both location and scale changes occurring at an unknown time point is considered. In a sequence of independent random variables X_{1}, …, X_{N} with continuous and differentiable distribution functions (d.fs.), F (x, θ_{i}) for i = 1, …, N; where the θ_{i}’s are either location or scale parameters, if the random variables X_{i}, i = 1, …, n for 1 ≤ n < N have d.fs. F (x, 0) and the random variables X_{i}, i = n + 1, …, N have d.fs. F (x, θ) with θ ≠ 0 then the sequence X_{i}, i = 1, …, N is said to have a single changepoint at time point n. The change in distribution may occur continuously over a period of time. This type of change may be referred to as a continuous change.

Changepoint problems have been studied quite extensively by various authors, using parametric and nonparametric procedures. In some of the studies the authors have assumed known underlying distributions. However, a good amount of work has also been done for the case of arbitrary underlying distributions. In these studies, changes in location or scale have been considered. To my knowledge, nothing has been done with respect to testing for location and scale changes together in a changepoint setting. Lombard [3] proposed rank statistics for detecting single abrupt, multiple abrupt, and smooth changepoints.

In this study, statistics that are functions of two linear rank statistics, one sensitive to location shift and the other one sensitive to scale shift are proposed. In section 2, the single changepoint model (SCM) is defined and the corresponding test statistic is obtained. The asymptotic distribution of the test statistic under null hypothesis is also considered. The same information for the continuous changepoint model (CCM) are given in section 3.

2. Single Changepoint Model and Test Statistic. Let X_{1}, …, X_{N} be a sequence of independent random variables with continuous d.fs. F [(1 + a_{i})x + b_{i}], i = 1, …, N where a_{i}’s and b_{i}’s are the scale and location parameters, respectively. The changepoint model SCM may be defined as follows.

(1)  a_{i} = \{ \begin{matrix}0, & 1 ≤ i ≤ n \\ a, & n + 1 ≤ i ≤ N, \end{matrix} b_{i} = \{ \begin{matrix}0, & 1 ≤ i ≤ n \\ b, & n + 1 ≤ i ≤ N. \end{matrix}

The accompanying null and alternative hypotheses are:

H_{0} : a = 0 or b = 0 or both

and

H_{a} : a ≠ 0 or b ≠ 0 or both.

In this case, if the changepoint is known then the problem becomes the standard two–sample problem and the test statistic is readily obtained and is given by

S_{n} = ∑_{i=n+1}^{N} a_{N}(R_{i}),

where a_{N}(R_{i})’s are the score functions based on the ranks R_{i}’s of X_{i}’s. In the model above, since the changepoint n is unknown, the required statistic takes the form

S_{N} = ∑_{n=1}^{N−1} ∑_{i=n+1}^{N} a_{N}(R_{i}) = ∑_{i=1}^{N}(i − 1)a_{N}(R_{i}).

Now we may use appropriate score functions to yield odd–translation invariant and even–translation invariant statistics that are suitable for testing location and scale changes, respectively. Thus, the test statistics can be formulated as

(2)  S_{Nk} = ∑_{i=1}^{N} c_{i}a_{Nk}(R_{i}), k = 1, 2,

where S_{N1} is odd–translation invariant, S_{N2} is even–translation invariant and c_{i} = i − 1, for i = 1, …, N. The statistics S_{Nk}, k = 1, 2 are suitable for detecting location and scale changes respectively. To formulate a statistic for testing location and scale changes, consider the following definitions. Let

(3)  S^{T} = (S_{N1}, S_{N2}), μ^{T} = (μ_{N1}, μ_{N2}), A = diag (σ_{N1}^{2}, σ_{N2}^{2})

where

μ_{Nk} = E[S_{Nk}] = N(N − 1)/2 ∫_{0}^{1} ϕ_{k}(u)du

σ_{Nk}^{2} = Var[S_{Nk}] = N(N^{2} − 1)/12 ∫_{0}^{1}[ϕ_{k}(u) − \overline{ϕ}_{k}]^{2}du, and

ζ_{Nk}^{2} = Cov [S_{N1}, S_{N2}] = N(N^{2} − 1)/12 ∫_{0}^{1}[ϕ_{1} − \overline{ϕ}_{1}][ϕ_{2} − \overline{ϕ}_{2}]du.

The score functions a_{Nk}(·), k = 1, 2 are given by square integrable functions ϕ_{k}, k = 1, 2 defined as

(4)  a_{Nk}(R_{i}) = ϕ_{k}(R_{i}/N + 1).

Now, for testing location and scale simultaneously in a changepoint problem the required statistic is given by

(5)  L_{1} = (S − μ)^{T} A^{−1}(S − μ).

The null hypothesis in the model SCM given by (1) is rejected for a large value of the statistic L_{1}. The following theorem gives the asymptotic distribution of L_{1} under H_{0}.

\underline{Theorem 1}. When H_{0} holds, then

lim_{N→∞} P [L_{1} ≤ x] = P [X_{2}^{2} ≤ x], x > 0,

where X_{2}^{2} is a Chi–square random variable with two degrees of freedom.

\underline{Proof}. The statistic L_{1} can be written as

L_{1} = ∑_{k=1}^{2}[(S_{Nk} − μ_{Nk})/σ_{Nk}]^{2}.

Since for each k, S_{Nk} is a linear rank statistic whose regression constants c_{i}’s satisfy the well known Noether’s condition, it follows from Theorem V.1.5a of Hajek and Sidak [2] that (S_{Nk} − μ_{Nk})/σ_{Nk} for each k has an asymptotic standard normal distribution. Furthermore, since the statistics S_{N1} and S_{N2} are uncorrelated, they are asymptotically independent. Therefore the statistic L_{1} converges in distribution to Z_{1}^{2} + Z_{2}^{2} where Z_{1} and Z_{2} are independent standard normal random variables. Hence, the result of the theorem.

Similar results can be obtained for the continuous changepoint problem and is given in the following section.

3. Continuous Changepoint Model and Test Statistic. The continuous changepoint model (CCM) is defined as follows

a_{i} = \{ \begin{matrix}0, & 1 ≤ i ≤ n \\ a(i-n)/(N-n) & n + 1 ≤ i ≤ N, \end{matrix} b_{i} = \{ \begin{matrix}0, & 1 ≤ i ≤ n \\ b(i-n)/(N-n) & n + 1 ≤ i ≤ N \end{matrix}

with the hypotheses

H_{0} : a = 0 or b = 0 or both

and

H_{a} : a ≠ 0 or b ≠ 0 or both.

The method of Hajek and Sidak [2] can be used to derive a test statistic for this changepoint model with known n, as

T_{n} = − ∑_{i=n+1}^{N}(N − i) a_{N}(R_{i}) + (N − n) ∑_{i=n+1}^{N} a_{N}(R_{i}) = ∑_{i=n+1}^{N}(i − n) a_{N}(R_{i}).

Now for the CCM with unknown n, the required statistic is obtained as

T_{N} = ∑_{n=1}^{N−1} ∑_{i=n+1}^{N}(i − n) a_{N}(R_{i}) = ∑_{i=1}^{N} d_{i} a_{N}(R_{i}),

where d_{i} = i(i − 1)/2. The statistic T_{N} may be modified as in the case of SCM, to test for location and scale changes as follows

(6)  T_{Nk} = ∑_{i=1}^{N} d_{i} a_{Nk}(R_{i}), k = 1, 2

so that T_{N1} is odd–translation invariant and T_{N2} is even–translation invariant. The statistics T_{N1} and T_{N2} are suitable for detecting location and scale changes, respectively.

In order to detect both the location and scale changes, like in the SCM the following statistic can be considered.

(7)  L_{2} = (T − v)^{T} B^{−1}(T − v),

where

T^{T} = (T_{N1}, T_{N2}), v^{T} = (v_{N1}, v_{N2}),

v_{Nk} = E[T_{Nk}] = N(N^{2} − 1)/6 ∫_{0}^{1} ϕ_{k}(u)du, B = diag (τ_{N1}^{2}, τ_{N2}^{2}), and

τ_{Nk}^{2} = var [T_{Nk}] = N(N^{2} − 1)(4N^{2} − 1)/180 ∫_{0}^{1}[ϕ_{k}(u) − \overline{ϕ}_{k}]^{2}du for k = 1, 2

and ϕ_{k}(·) is as defined in (4). And it can be shown that

Cov [T_{N1}, T_{N2}] = N(N^{2} − 1)(4N^{2} − 1)/180 ∫_{0}^{1}[ϕ_{1} − \overline{ϕ}_{1}][ϕ_{2} − \overline{ϕ}_{2}]du.

With these definitions and results we use the procedures of section 2 to come up with the following results regarding the asymptotic distributions of the test statistic L_{2}.

\underline{Theorem 2}. When H_{0} holds, then

lim_{N→∞} P [L_{2} ≤ x] = P [X_{2}^{2} ≤ x], x > 0,

where X_{2}^{2} is the random variable with a Chi–square distribution with two degrees of freedom.

4. Concluding Remarks. The detection of single and continuous changepoints in the presence of location and scale changes is studied in this paper. A combination of odd–translation invariant and even–translation invariant linear rank statistics is used in this case. Similar procedures to the one used can be applied in detecting multiple changepoints in a sequence of random variables. It is also believed that a similar procedure may be applied in detecting a changepoint in a sequence of exchangeable random variables. Note that exchangeability does not imply independence.

An extension of the procedure mentioned in this paper can be carried out effectively for multivariate changepoint problems. The statistics L_{1} and L_{2} are of the form used by Duran, Tsai and Lewis [1] for simultaneous location–scale testing on two–sample problems. Also note that Lombard [3] used similar models.

\underline{Acknowledgement}. I am grateful to the referees for their helpful suggestions.

\underline{References}

1. B. S. Duran, W. S. Tsai, and T. O. Lewis, “A Class of Location–Scale Nonparametric Tests,” Biometrika, 63 (1976), 173–176.

2. T. Hajek and Z. Sidak, Theory of Rank Tests, Academic Press, New York, 1967.

3. F. Lombard, “Rank Tests for Changepoint Problems,” Biometrika, 74 (1987), 615–624.

Sivanandan Balakumar Department of Natural Sciences and Mathematics Lincoln University Jefferson City, MO 65102 email: balakuma@lincolnu.edu

æ