Location test under a bounded non-stationarity?

Suppose I draw $n$ observations $X_1,X_2,\ldots,X_n$ independently from a distribution where $X_i \sim \mathcal{N}(\mu_i,\sigma^2)$, where the mean is assumed to be Lipschitz: $\left| \mu_i - \mu_{i+1}\right| \le \gamma,$ with $\gamma$ known. I want to test the null hypothesis: $$H_0: \mu_n = 0$$ against the local alternative $H_1: \mu_n > 0$.

A few questions:

1. Is this a known problem? If so, for what terms should I google search?
2. What is a reasonable way to perform this test? I can imagine there might be some way to do it by downweighting less recent observations--maybe throw the innovations into the noise term, then use a weighted t-test? The problem with that approach is that the change in mean may be deterministic, so I should pose the problem as a minimax problem maybe. Perhaps another approach would be to ignore the non-stationarity and use a regular t-test on some subset of the observations $X_j,X_{j+1},\ldots,X_n$, with $n-j$ chosen by some function of $\gamma, \sigma$ (probably their ratio?), and accept that the test will not maintain the nominal Type I rate. What are some better ideas?

Edit: per the excellent comments so far, I believe this question can be reformulated as follows: Let $V$ be the convex set in $\mathbb{R}^n$ defined by: $$V = \left\{\mathbf{x} | x_n = 0, x_{i-1} \le x_i + \gamma, x_{i-1} \ge x_i - \gamma, i = 2,\ldots,n \right\}$$ Observing vector $X = f + \sigma\epsilon$, where the elements of $\epsilon$ are drawn independently from a standard Gaussian, test the null hypothesis: $$H_0: f \in V$$ In this sense, it is similar to the paper of Baraud et. al. mentioned by @Robin Girard, except the Baraud paper provides a method for the case where $V$ is a linear subspace of $\mathbb{R}^n$, not a convex polytope.

Under this formulation, it seems that, under the null, the squared distance from $X$ to $f$ should be distributed as a Chi-squared, up to the scaling factor of $\sigma^2$. Then the distance from $X$ to $V$ should be no greater than that. The proposed test would then be to find the projection of $X$ onto $V$, and test the distance from $X$ to that projection based on the Chi-squared bound. I imagine this test will have fairly low power. Perhaps truncating the observation to a final subset of the $X_i$ would have higher power...

• This doesn't qualify as an answer, but I think something along the lines of a maximum entropy distribution for $\mu_{i}$, subject to your constraints $\left| \mu_i - \mu_{i+1}\right| \le \gamma$. Set this distribution as the prior, and then set jeffreys prior for $\sigma$. Then update using Bayes theorem to a posterior for $\mu_n$, and calculate the probability $Pr(\mu_{n}>0)$, and use it like a p-value. Calculating the MaxEnt distribution may be difficult to do though. Feb 13 '11 at 5:27
• @probabilityislogic: We can assume that $\sigma$ is known, which should simplify this computation. Feb 13 '11 at 5:50
• @shabbychef, if you set up a likelihood ratio test, then under both $H_0$ and $H_1$, you have a convex program to solve for $\hat{\mu}_i$. If you look at the KKT conditions, you might even be able to find an explicit solution. Maybe try "walking backward" from $i = n$, e.g., under $H_0$, it seems that if $|X_{n-1}| > \gamma$, then $\hat{\mu}_{n-1}$ is likely equal to $\mathrm{sgn}(X_{n-1}) \gamma$. You might also look at the fused lasso, which has a "similar" (but not identical) form as your problem. I'm not sure that much is known about distributions of likelihood ratios in that setting. Feb 13 '11 at 5:59
• @mpiktas, not in general since the constraints can force the "perfect fit" to be infeasible. Of course, if the perfect fit is feasible for $H_0$ then the LRT will be 1. But, I think that's the desired answer in that case anyway! Feb 13 '11 at 15:33
• I fully agree with cardinal's answer, there is not a very big problem here and hence certainly no litterature (however I like the question :) +1 for that). However this is certainly a simple particular case of what is called ["Adaptive tests of linear hypotheses by model selection by " Y. Baraud, S. Huet, and B. Laurent] : projecteuclid.org/… Feb 13 '11 at 19:49

Ok, I've thought of two possible ways to answer to this problem using Bayesian analysis. I will assume $\sigma$ to be known throughout this answer. First start with a "baby" case, where $n=2$ (or alternatively, only using the last two observations as a first approximation). You would usually start this by assuming a "flat" prior for $\mu$, just proportion to 1. But you have additional information, so we just restrict the prior to conform to this. So the prior is: $$f(\mu_1,\mu_2|\gamma) \propto I_{|\mu_1-\mu_2|\leq\gamma}$$ (the improper prior should be fine, because you are dealing with normal RVs, and you aren't dividing them) Combining this prior with the likelihood, and integrating out $\mu_1$ gives (Writing $\phi(x)$ as standard normal pdf and $\Phi(x)$ as standard normal cdf):

$$f(\mu_2 | X_1,X_2,\sigma,\gamma) \propto \phi\big(\frac{\mu_2-X_2}{\sigma}\big) \Bigg[\Phi\Big(\frac{\mu_2-X_1+\gamma}{\sigma}\Big)-\Phi\Big(\frac{\mu_2-X_1-\gamma}{\sigma}\Big)\Bigg]$$ So in order to calculate the "p-value" for the hypothesis, we need to take $Pr(\mu_2 > 0 |X_1,X_2,\sigma,\gamma)=P$. This is given by the ratio of two integrals of the posterior: $$P=\frac{\int_{-\frac{X_2}{\sigma}}^{\infty}\phi\big(y\big) \Bigg[\Phi\Big(y+\frac{X_2-X_1+\gamma}{\sigma}\Big)-\Phi\Big(y+\frac{X_2-X_1-\gamma}{\sigma}\Big)\Bigg]dy}{\int_{-\infty}^{\infty}\phi\big(z\big) \Bigg[\Phi\Big(z+\frac{X_2-X_1+\gamma}{\sigma}\Big)-\Phi\Big(z+\frac{X_2-X_1-\gamma}{\sigma}\Big)\Bigg]dz}$$

It is beyond my abilities to do either of these integrals exactly, and even if it was possible, you probably would learn anything intuitive about the problem (except that the integral was friggin hard! you'd think it could be derived using something to do with convolutions, but I couldn't work it out). So I would just numerically evaluate these two integrals.

For the whole data set, you will almost surely need some kind of numerical technique, or analytic approximation. This is a rather quick numerical technique. Okay, so it basically goes like this: if you knew $\mu_1$, then you could generate a sample of the remaining $\mu_i$ values sequentially, using the uniform distribution $(\mu_{i}|\mu_{i-1}) \sim U(\mu_{i-1}-\gamma,\mu_{i-1}+\gamma)$. An obvious way to sample $\mu_1$ is from a gaussian with large variance $\mu_1 \sim N(0,\delta^2)$ ("large" meaning relative to your data, say $\delta\approx 10\sigma$). Use the notation $\mu_{i}^{(b)}$ for the $b$th sample of means $b=1,\dots,B$. Now you calculate the total likelihood for each iteration. This will be used as a weight:

$$w^{(b)}=\prod_{i=1}^{n} \phi \Big(\frac{\mu_{i}^{(b)}-X_i}{\sigma}\Big)$$

Then you take a "weighted probability" of the alternative hypothesis:

$$\hat{P}=\frac{\sum_{b=1}^{B}w^{(b)} I(\mu_{n}^{(b)}>0)}{\sum_{b=1}^{B}w^{(b)}}$$

If $P$ is too big (in either case), then you reject the null hypothesis. A standard value would be $P>0.95$.