9
$\begingroup$

I have been trying to establish the inequality

$$\left| T_i \right|=\frac{\left|X_i -\bar{X} \right|}{S} \leq\frac{n-1}{\sqrt{n}}$$

where $\bar{X}$ is the sample mean and $S$ the sample standard deviation, that is $S=\sqrt{\frac{\sum_{i=1}^n \left( X_i -\bar{X} \right)^2}{n-1}}$.

It is easy to see that $\sum_{i=1}^n T_i^2 = n-1 $ and so $\left| T_i \right| < \sqrt{n-1}$ but this is not very close to what I have been looking for, nor is it a useful bound. I have experimented with the Cauchy-Schwarz and the triangle inequalities but have gone nowhere. There must be a subtle step that I am missing somewhere. I would appreciate some help, thank you.

$\endgroup$
10
$\begingroup$

This is Samuelson's inequality and it needs the $\leq$ sign. If you take the Wikipedia version and rework it for the $n-1$ definition of $S,$ you will find that it becomes $${{ \left| X_i-\bar X \right| } \over S} \leq {{n-1} \over \sqrt{n}}$$

$\endgroup$
  • $\begingroup$ It's given as a strict inequality in the book but I've fixed it, thanks. $\endgroup$ – JohnK Sep 14 '15 at 16:22
5
$\begingroup$

After simplifying the problem by means of routine procedures, it can be solved by converting it into a dual minimization program which has a well-known answer with an elementary proof. Perhaps this dualization is the "subtle step" referred to in the question. The inequality can also be established in a purely mechanical manner by maximizing $|T_i|$ via Lagrange multipliers.

First though, I offer a more elegant solution based on the geometry of least squares. It requires no preliminary simplification and is almost immediate, providing direct intuition into the result. As suggested in the question, the problem reduces to the Cauchy-Schwarz inequality.


Geometric solution

Consider $\mathbf{x} = (X_1, X_2, \ldots, X_n)$ as an $n$-dimensional vector in Euclidean space with the usual dot product. Let $\mathbf{y} = (0,0,\ldots,0,1,0,\ldots,0)$ be the $i^\text{th}$ basis vector and $\mathbf{1} = (1,1,\ldots, 1)$. Write $\mathbf{\hat x}$ and $\mathbf{\hat y}$ for the orthogonal projections of $\mathbf{x}$ and $\mathbf{y}$ into the orthogonal complement of $\mathbf{1}$. (In statistical terminology, they are the residuals with respect to the means.) Then, since $X_i-\bar X = \mathbf{\hat x}\cdot \mathbf{y}$ and $S = ||\mathbf{\hat x}||/\sqrt{n-1}$,

$$|T_i| = \sqrt{n-1}\frac{|\mathbf{\hat x} \cdot \mathbf{y}|}{||\mathbf{\hat x}||} = \sqrt{n-1}\frac{|\mathbf{\hat x} \cdot \mathbf{\hat y}|}{||\mathbf{\hat x}||}$$

is the component of $\mathbf{\hat y}$ in the $\mathbf{\hat x}$ direction. By Cauchy-Schwarz, it is maximized exactly when $\mathbf{\hat x}$ is parallel to $\mathbf{\hat y} = (-1,-1,\ldots,-1,n-1,-1,-1,\ldots,-1)/n$, for which $$T_i = \pm \sqrt{n-1} \frac{\mathbf{\hat y}\cdot \mathbf{\hat y} }{ ||\mathbf{\hat y}||} = \pm\sqrt{n-1}||\mathbf{\hat y}|| = \pm\frac{n-1}{\sqrt{n}},$$ QED.

Incidentally, this solution provides an exhaustive characterization of all the cases where $|T_i|$ is maximized: they are all of the form

$$\mathbf{x} = \sigma\mathbf{\hat y} + \mu\mathbf{1} = \sigma(-1,-1,\ldots,-1,n-1,-1,-1,\ldots,-1) + \mu(1,1,\ldots, 1)$$

for all real $\mu, \sigma$.

This analysis generalizes easily to the case where $\{\mathbf{1}\}$ is replaced by any set of regressors. Evidently the maximum of $T_i$ is proportional to the length of the residual of $\mathbf{y}$, $||\mathbf{\hat y}||$.


Simplification

Because $T_i$ is invariant under changes of location and scale, we may assume with no loss of generality that the $X_i$ sum to zero and their squares sum to $n-1$. This identifies $|T_i|$ with $|X_i|$, since $S$ (the mean square) is $1$. Maximizing it is tantamount to maximizing $|T_i|^2 = T_i^2 = X_i^2$. No generality is lost by taking $i=1$, either, since the $X_i$ are exchangeable.


Solution via a dual formulation

A dual problem is to fix the value of $X_1^2$ and ask what values of the remaining $X_j, j\ne 1$ are needed to minimize the sum of squares $\sum_{j=1}^n X_j^2$ given that $\sum_{j=1}^n X_j = 0$. Because $X_1$ is given, this is the problem of minimizing $\sum_{j=2}^n X_j^2$ given that $\sum_{j=2}^n X_j = -X_1$.

The solution is easily found in many ways. One of the most elementary is to write

$$X_j = -\frac{X_1}{n-1} + \varepsilon_j,\ j=2, 3, \ldots, n$$

for which $\sum_{j=2}^n \varepsilon_j = 0$. Expanding the objective function and using this sum-to-zero identity to simplify it produces

$$\sum_{j=2}^n X_j^2 = \sum_{j=2}^n \left(-\frac{X_1}{n-1} + \varepsilon_j\right)^2 = \\\sum \left(-\frac{X_1}{n-1}\right)^2 - 2\frac{X_1}{n-1}\sum \varepsilon_j + \sum \varepsilon_j^2 \\= \text{Constant} + \sum \varepsilon_j^2,$$

immediately showing the unique solution is $\varepsilon_j=0$ for all $j$. For this solution,

$$(n-1)S^2 = X_1^2 + (n-1)\left(-\frac{X_1}{n-1}\right)^2 = \left(1 + \frac{1}{n-1}\right)X_1^2 = \frac{n}{n-1}X_1^2$$

and

$$|T_i| = \frac{|X_1|}{S} = \frac{|X_1|}{\sqrt{\frac{n}{(n-1)^2}X_1^2}} = \frac{n-1}{\sqrt{n}},$$

QED.


Solution via machinery

Return to the simplified program we began with:

$$\text{Maximize } X_1^2$$

subject to

$$\sum_{i=1}^n X_i = 0\text{ and }\sum_{i=1}^n X_i^2 -(n-1)=0.$$

The method of Lagrange multipliers (which is almost purely mechanical and straightforward) equates a nontrivial linear combination of the gradients of these three functions to zero:

$$(0,0,\ldots, 0) = \lambda_1 D(X_1^2) + \lambda_2 D\left(\sum_{i=1}^n X_i\right ) + \lambda_3 D\left(\sum_{i=1}^n X_i^2 -(n-1)\right).$$

Component by component, these $n$ equations are

$$\eqalign{ 0 &= 2\lambda_1 X_1 +& \lambda_2 &+ 2\lambda_3 X_1 \\ 0 &= & \lambda_2 &+ 2\lambda_3 X_2 \\ 0 &= \cdots \\ 0 &= & \lambda _2 &+ 2\lambda_3 X_n. }$$

The last $n-1$ of them imply either $X_2 = X_3 = \cdots = X_n = -\lambda_2/(2\lambda_3)$ or $\lambda_2=\lambda_3=0$. (We may rule out the latter case because then the first equation implies $\lambda_1=0$, trivializing the linear combination.) The sum-to-zero constraint produces $X_1 = -(n-1)X_2$. The sum-of-squares constraint provides the two solutions

$$X_1 = \pm\frac{n-1}{\sqrt{n}};\ X_2 = X_3 = \cdots = X_n = \mp\frac{1}{\sqrt{n}}.$$

They both yield

$$|T_i| = |X_1| \le |\pm\frac{n-1}{\sqrt{n}}| = \frac{n-1}{\sqrt{n}}.$$

$\endgroup$
  • $\begingroup$ Thank you for your addendum, geometry is very powerful and of all three solutions it is the most intuitive to me. $\endgroup$ – JohnK Oct 2 '15 at 21:05
0
$\begingroup$

The inequality as stated is true. It is quite clear intuitively that we get the most difficult case for the inequality (that is, maximizing the left hannd side for given $S^2$) by choosing one value, say $x_1$ as large as possible while having all the others equal. Let us look at an example with such configuration:

$$ n=4, \quad x_1=x_2=x_3=0, x_4=4, \bar{x}=1, S^2=4, $$ now $\frac{|x_i-\bar{x}|}{S}=\begin{cases} \frac12 ~\text{or}~ \\ \frac32 \end{cases}$ depending on $i$, while the given upper limit is equal to $\frac{4-1}{2}=1.5$ which is just enough. That idea can be completed to a proof.

EDIT

We will now prove the claim, as hinted above. First, for any given vector $ x=(x_1, x_2, \dots, x_n)$ in this problem, we can replace it with $x-\bar{x}$ without changing either side of the inequality above. So, in the following let us assume that $\bar{x}=0$. We can also by relabelling assume that $x_1$ is largest. Then, by choosing first $x_1>0$ and then $x_2=x_3=\dots=x_n=-\frac{x_1}{n-1}$ we can check by simple algebra that we have equality in the claimed inequality. So, it is sharp.

Then, define the (convex) region $R$ by $$ R = \{ x\in\mathbb{R} \colon \bar{x}=0, \sum(x_i-\bar{x})^2/(n-1) \le S^2\} $$ for a given positive constant $S^2$. Note that $R$ is the intersection of a hyperplane with a sphere centered at the origin, so is a sphere in $(n-1)$-space. Our problem can now be formulated as $$ \max_{x\in R} \max_i |x_i| $$ since an $x$ maximizing that will be the most difficult case for the inequality. This is a problem of finding the maximum of a convex function over a convex set, which in general are difficult problems (minimums are easy!). But, in this case the convex region is a sphere centered on the origin, and the function we want to maximize is the absolute value of the coordinates. It is obvious that that maximum is found at the boundary sphere of $R$, and by taking $|x_1|$ maximal, our first test case is forced.

$\endgroup$
  • $\begingroup$ @JohnK you can delete your comments now, the post is corrected $\endgroup$ – kjetil b halvorsen Sep 14 '15 at 18:06
  • $\begingroup$ Although this answer shows that the inequality (assuming it is true, which it is) is tight, it isn't evident how that single calculation could be "completed to a proof." Could you provide some indication of how that would be done? $\endgroup$ – whuber Sep 14 '15 at 19:16
  • $\begingroup$ Will, but tomorrow, now I have to prepare tomorrows class. $\endgroup$ – kjetil b halvorsen Sep 14 '15 at 19:47
  • $\begingroup$ Thank you--I appreciate your careful formulation of the problem. But your "proof" seems to come to the statement that "it is obvious that." You could always apply Lagrange multipliers to finish the job, but it would be nice to see an approach that (a) actually is a proof and (b) provides insight. $\endgroup$ – whuber Sep 15 '15 at 14:53
  • 2
    $\begingroup$ @whuber If you have the time, I would appreciate it if you can post your Lagrange multipliers solution. I think the inequality overall is not as famous as it should be. $\endgroup$ – JohnK Oct 1 '15 at 22:17

Your Answer

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

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