Suppose there exists a sequence of $n$ numbers with two possible instantiations:

  1. The sequence contains all zeros;
  2. $n-1$ of the numbers are zeros, and one is a zero-mean Gaussian random variable $y_t\sim\mathcal{N}(0,\sigma^2)$ where $t$ denotes the location of the Gaussian in the sequence of zeros. The location $t$ is uniformly distributed from 1 to $n$ (i.e. the Gaussian is equally likely to be found in every location in the sequence).

This sequence is corrupted by zero-mean i.i.d. additive Gaussian noise (that is also independent from the sequence). Therefore, when I observe a vector $\mathbf{x}$, it is either:

  1. Sequence of $n$ i.i.d. Gaussian random variables $\mathbf{x}=\{x_i\}_{i=1}^n$ where $x_i=z_i\sim\mathcal{N}(0,s^2)$ for all $i=1,2,\ldots,n$;
  2. Sequence of $n$ Gaussian random variables $\mathbf{x}=\{x_i\}_{i=1}^n$ for $t\in 1,2,\ldots, n$ and $P(T=t)=1/n$, where $x_t=y_t+z_t$ which means $x_t\sim\mathcal{N}(0,\sigma^2+s^2)$, and $x_i=z_i\sim\mathcal{N}(0,s^2)$ for $i\neq t$.

I am looking for a hypothesis test to distinguish these two sequences, denoting the first sequence as a null. Since all the random variates are independent, the likelihood function of null hypothesis is then just the product of Gaussians: $$f_1(\mathbf{x})=\frac{1}{(2\pi s^2)^{n/2}}e^{-\frac{1}{2s^2}\sum_{i=1}^nx_i^2}$$ while the likelihood function of the alternate hypothesis is the following mixture of the products of Gaussians:

$$f_2(\mathbf{x})=\frac{1}{n}\frac{1}{(2\pi s^2)^{(n-1)/2}}\frac{1}{\sqrt{2\pi(\sigma^2+s^2)}}\sum_{t=1}^ne^{-\frac{x_t^2}{2(s^2+\sigma^2)}-\frac{1}{2s^2}\sum_{i=1,i\neq t}^nx_i^2}$$

With a little arithmetic massaging, the likelihood ratio is as follows:

$$\Lambda(\mathbf{x})=\frac{f_2(\mathbf{x})}{f_1(\mathbf{x})}=\frac{1}{n}\sqrt{\frac{s^2}{\sigma^2+s^2}}\sum_{t=1}^n e^{\frac{\sigma^2}{2s^2(s^2+\sigma^2)}x_t^2}$$

So the LRT here involves squaring each observation, summing their exponents, and comparing the resultant test statistic to a threshold. However, the distribution of the test statistic is analytically daunting (at least to me, maybe someone knows how to analyze the probabilities of error without resorting to numerical analysis).

The simpler, "natural" (at least to me) hypothesis test is to square the observed sequence term-by-term, find the maximum and compare to a threshold. This is much more amenable to analysis, but how close is it to the optimal LRT above? Are there asymptotic results (say, as $n$ increases)?

This problem seems like something that might have been solved in the radar scenario (seems to correspond to pinging a target with a single Gaussian, and having some random offset in the return time of the signal if it bounces off the target), however, I can't find any appropriate references.

  • $\begingroup$ How do you obtain a sum instead of a product over the data? $\endgroup$ – whuber Jul 17 '13 at 14:57
  • $\begingroup$ @whuber The sum is due to the mixture distribution over the data when alternate hypothesis is true. I clarified in the question. $\endgroup$ – M.B.M. Jul 17 '13 at 15:45
  • 1
    $\begingroup$ The alternate is not a mixture, that's why. You have guaranteed that precisely one of the values is different. Therefore the data are a random permutation of an experiment in which the first observation is from one distribution and all the rest are from another (and all distributional parameters are known, apparently). Because you don't label the data and they are independent, the likelihood conditional on any permutation is the product of the likelihoods. Because this conditional likelihood does not depend on the permutation, it must be the full likelihood. $\endgroup$ – whuber Jul 17 '13 at 16:09
  • 2
    $\begingroup$ I'm not convinced this is correct. The potential error I made lies in asserting that the conditional likelihood is independent of the permutation: but it does depend on it. And that, unfortunately, gets us right back to where you started. This pseudo-reasoning, though, suggests you might construct a successful test anyway by using the sum of squares as your test statistic. It can be justified as a first-order approximation to the correct log-likelihood. $\endgroup$ – whuber Jul 17 '13 at 16:40
  • 1
    $\begingroup$ @whuber Right, I was just about to post that I was confused again, as I was having trouble writing down the likelihood function for the alternate... Could you please elaborate on the "first-order approximation to the correct log-likelihood"? How does one justify an approximation of a function when the function is unknown in the first place? $\endgroup$ – M.B.M. Jul 17 '13 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.