Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

This is a problem from the "7th Kolmogorov Student Olympiad in Probability Theory":

Given one observation $X$ from a $\operatorname{Normal}(\mu,\sigma^2)$ distribution with both parameters unknown, give a confidence interval for $\sigma^2$ with a confidence level of at least 99%.

It seems to me that this should be impossible. I have the solution, but haven't read it yet. Any thoughts?

I'll post the solution in a couple days.

[Follow-up edit: Official solution posted below. Cardinal's solution is longer, but gives a better confidence interval. Thanks also to Max and Glen_b for their input.]

share|improve this question
1  
Seems impossible to me, too; I await the answer –  Peter Flom Dec 2 '12 at 0:11
1  
Check out this site. –  Max Dec 2 '12 at 0:29
2  
Here's a paper with better formatting: paper. –  Max Dec 2 '12 at 0:54
    
Heh. I remember reading a paper on this stuff (one observation intervals) many years back. Might have been this one. –  Glen_b Dec 2 '12 at 1:06
1  
@Max, thanks for the link! I haven't had time to look closely at it yet, but I will. I posted the "official" answer below. –  Jonathan Christensen Dec 5 '12 at 3:27
add comment

3 Answers 3

up vote 14 down vote accepted

Viewed through the lens of probability inequalities and connections to the multiple-observation case, this result might not seem so impossible, or, at least, it might seem more plausible.

Let $\renewcommand{\Pr}{\mathbb P}\newcommand{\Ind}[1]{\mathbf 1_{(#1)}}X \sim \mathcal N(\mu,\sigma^2)$ with $\mu$ and $\sigma^2$ unknown. We can write $X = \sigma Z + \mu$ for $Z \sim \mathcal N(0,1)$.

Main Claim: $[0,X^2/q_\alpha)$ is a $(1-\alpha)$ confidence interval for $\sigma^2$ where $q_\alpha$ is the $\alpha$-level quantile of a chi-squared distribution with one degree of freedom. Furthermore, since this interval has exactly $(1-\alpha)$ coverage when $\mu = 0$, it is the narrowest possible interval of the form $[0,b X^2)$ for some $b \in \mathbb R$.

A reason for optimism

Recall that in the $n \geq 2$ case, with $T = \sum_{i=1}^n (X_i - \bar X)^2$, the typical $(1-\alpha)$ confidence interval for $\sigma^2$ is $$ \Big(\frac{T}{q_{n-1,(1-\alpha)/2}}, \frac{T}{q_{n-1,\alpha/2}} \Big) \>, $$ where $q_{k,a}$ is the $a$-level quantile of a chi-squared with $k$ degrees of freedom. This, of course, holds for any $\mu$. While this is the most popular interval (called the equal-tailed interval for obvious reasons), it is neither the only one nor even the one of smallest width! As should be apparent, another valid selection is $$ \Big(0,\frac{T}{q_{n-1,\alpha}}\Big) \>. $$

Since, $T \leq \sum_{i=1}^n X_i^2$, then $$ \Big(0,\frac{\sum_{i=1}^n X_i^2}{q_{n-1,\alpha}}\Big) \>, $$ also has coverage of at least $(1-\alpha)$.

Viewed in this light, we might then be optimistic that the interval in the main claim is true for $n = 1$. The main difference is that there is no zero-degree-of-freedom chi-squared distribution for the case of a single observation, so we must hope that using a one-degree-of-freedom quantile will work.

A half step toward our destination (Exploiting the right tail)

Before diving into a proof of the main claim, let's first look at a preliminary claim that is not nearly as strong or satisfying statistically, but perhaps gives some additional insight into what is going on. You can skip down to the proof of the main claim below, without much (if any) loss. In this section and the next, the proofs—while slightly subtle—are based on only elementary facts: monotonicity of probabilities, and symmetry and unimodality of the normal distribution.

Auxiliary claim: $[0,X^2/z^2_\alpha)$ is a $(1-\alpha)$ confidence interval for $\sigma^2$ as long as $\alpha > 1/2$. Here $z_\alpha$ is the $\alpha$-level quantile of a standard normal.

Proof. $|X| = |-X|$ and $|\sigma Z + \mu| \stackrel{d}{=} |-\sigma Z+\mu|$ by symmetry, so in what follows we can take $\mu \geq 0$ without loss of generality. Now, for $\theta \geq 0$ and $\mu \geq 0$, $$ \Pr(|X| > \theta) \geq \Pr( X > \theta) = \Pr( \sigma Z + \mu > \theta) \geq \Pr( Z > \theta/\sigma) \>, $$ and so with $\theta = z_{\alpha} \sigma$, we see that $$ \Pr(0 \leq \sigma^2 < X^2 / z^2_\alpha) \geq 1 - \alpha \>. $$ This works only for $\alpha > 1/2$, since that is what is needed for $z_\alpha > 0$.

This proves the auxiliary claim. While illustrative, it is unsatifying from a statistical perspective since it requires an absurdly large $\alpha$ to work.

Proving the main claim

A refinement of the above argument leads to a result that will work for an arbitrary confidence level. First, note that $$ \Pr(|X| > \theta) = \Pr(|Z + \mu/\sigma| > \theta / \sigma ) \>. $$ Set $a = \mu/\sigma \geq 0$ and $b = \theta / \sigma \geq 0$. Then, $$ \Pr(|Z + a| > b) = \Phi(a-b) + \Phi(-a-b) \>. $$ If we can show that the right-hand side increases in $a$ for every fixed $b$, then we can employ a similar argument as in the previous argument. This is at least plausible, since we'd like to believe that if the mean increases, then it becomes more probable that we see a value with a modulus that exceeds $b$. (However, we have to watch out for how quickly the mass is decreasing in the left tail!)

Set $f_b(a) = \Phi(a-b) + \Phi(-a-b)$. Then $$ f'_b(a) = \varphi(a-b) - \varphi(-a-b) = \varphi(a-b) - \varphi(a+b) \>. $$ Note that $f'_b(0) = 0$ and for positive $u$, $\varphi(u)$ is decreasing in $u$. Now, for $a \in (0,2b)$, it is easy to see that $\varphi(a-b) \geq \varphi(-b) = \varphi(b)$. These facts taken together easily imply that $$ f'_b(a) \geq 0 $$ for all $a \geq 0$ and any fixed $b \geq 0$.

Hence, we have shown that for $a \geq 0$ and $b \geq 0$, $$ \Pr(|Z + a| > b) \geq \Pr(|Z| > b) = 2\Phi(-b) \>. $$

Unraveling all of this, if we take $\theta = \sqrt{q_\alpha} \sigma$, we get $$ \Pr(X^2 > q_\alpha \sigma^2) \geq \Pr(Z^2 > q_\alpha) = 1 - \alpha \>, $$ which establishes the main claim.

Closing remark: A careful reading of the above argument shows that it uses only the symmetric and unimodal properties of the normal distribution. Hence, the approach works analogously for obtaining confidence intervals from a single observation from any symmetric unimodal location-scale family, e.g., Cauchy or Laplace distributions.

share|improve this answer
    
Wow! and students are expected to come up with this type of argument in the short time of an Olympiad exam? –  Dilip Sarwate Dec 3 '12 at 2:12
1  
@Dilip: I have no idea! I'm unfamiliar with the format of this Olympiad or what is expected in terms of a solution. From a literal reading, I would think Scortchi's answer would be acceptable. I was more interested in trying to figure out how far one might get with a "non-trivial" solution. My own (fairly minimal) exploration followed the same train of thought described in the answer (with one detour). It's quite likely there exists a better solution. :-) –  cardinal Dec 3 '12 at 2:31
    
This is considerably longer than the "official" solution, but it gives a better bound on the variance, so I'm marking it as the "correct" answer. I've posted the "official" answer below, as well as some simulation results and discussion. Thanks, @cardinal! –  Jonathan Christensen Dec 5 '12 at 3:27
2  
@Jonathan: Thanks. Yes, I could have made the proof quite a bit more terse. Due to the wide range of backgrounds of the participants here, I often tend to indulge in extra (or, perhaps, excessive) detail. :-) –  cardinal Dec 5 '12 at 5:13
add comment

Time to follow up! Here's the solution I was given:

We will construct a confidence interval of the form $[0,T(X))$, where $T(\cdot)$ is some statistic. By definition this will be a confidence interval with confidence level at least 99% if $$(\forall \mu \in \mathbb R )(\forall \sigma > 0)\; \mathbb P_{\mu,\sigma_2}(\sigma^2 > T(X)) < 0.01.$$ We note that the density of the $\mathcal{N}(\mu,\sigma^2)$ distribution does not exceed $1/\sigma\sqrt{2\pi}$. Therefore, $\mathbb{P}(|X| \leq a) \leq a/\sigma$ for every $a \geq 0$. It follows that $$t \geq \mathbb P (|X|/\sigma \leq t) = \mathbb P (X^2 \leq t^2\sigma^2) = \mathbb P (\sigma^2 \geq X^2/t^2).$$ Plugging in $t = 0.01$ we obtain that the appropriate statistic is $T(X) = 10000X^2.$

The confidence interval (which is very wide) is slightly conservative in simulation, with no empirical coverage (in 100,000 simulations) lower than 99.15% as I varied the CV over many orders of magnitude.

For comparison, I also simulated cardinal's confidence interval. I should note that cardinal's interval is quite a bit narrower--in the 99% case, his ends up being up to about $6300X^2$, as opposed to the $10000X^2$ in the provided solution. Empirical coverage is right at the nominal level, again over many orders of magnitude for the CV. So his interval definitely wins.

I haven't had time to look carefully at the paper Max posted, but I do plan to look at that and may add some comments regarding it later (i.e., no sooner than a week). That paper claims a 99% confidence interval of $(0,4900X^2)$, which has empirical coverage slightly lower (about 98.85%) than the nominal coverage for large CVs in my brief simulations.

share|improve this answer
1  
(+1) That's a nice solution. Should you have $t \geq \cdots$ instead of $t \leq \cdots$ in the display equation? –  cardinal Dec 5 '12 at 5:10
1  
A couple more points: Your solution can be made to be very close to mine without any change in the argument. Note that you can claim that $\mathbb P(|X| \leq a) \leq 2 a / \sigma \sqrt{2\pi}$. Then the interval becomes $(0,2X^2/\pi\alpha^2)$ for any $\alpha$. Using $\alpha = 0.01$ yields $T(X) \approx 6366.198 X^2$ versus the $1/q_{0.01} \approx 6365.864$ in my answer. The higher the confidence level (i.e., the smaller the $\alpha$), the closer your method compares to mine (though your interval will always be wider). –  cardinal Dec 5 '12 at 14:58
1  
Second, I have not looked at that paper, but I have strong doubts that $(0,4900 X^2)$ can be a valid 99% confidence interval. Indeed, consider all confidence intervals of the form $(0, b X^2)$ for some $b$. Then, when $\mu = 0$, we have that $X^2/\sigma^2$ is exactly chi-squared with one degree of freedom and so the smallest $b$ we could select in this instance is $b = 1/q_{\alpha}$. In other words, the interval given in my answer is the narrowest possible of the stated form. –  cardinal Dec 5 '12 at 15:00
1  
I made the (suspected) typo correction. Also, pchisq(1/4900,1,lower.tail=F) in R returns 0.9886, quite close to your simulation results for the $(0,4900X^2)$ interval. –  cardinal Dec 5 '12 at 15:39
1  
Thanks for all the comments, @cardinal. I think your change is correct, though I typed it the way it was in the original solutions--typo there, I guess. –  Jonathan Christensen Dec 5 '12 at 17:02
add comment

The CI's $(0,\infty)$ presumably.

share|improve this answer
1  
I think it would be helpful for you to say why you can't get a finite length confidence interval. –  Max Dec 2 '12 at 1:00
    
@Max I'm not smart enough - but the question didn't ask for one. –  Scortchi Dec 2 '12 at 1:12
2  
+1 for this. Question didn't say a CI with minimal coverage, and in fact implies that this might be acceptable through its curious wording, "a confidence interval with a confidence level of at least 99%." –  Ari B. Friedman Dec 3 '12 at 1:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.