Rutgers University
The State University Of New Jersey
College of Engineering
Department of Electrical and Computer Engineering


332:501Systems Analysis
Pop Quiz I Statement and Solution

1.

What are the properties of a distance measure?

There are three properties

• 
  
  $$\rho(x,y) = \left\{\begin{array}{ll} \displaystyle {0} & {\... ... \displaystyle {>0} & {\mbox{otherwise}} \end{array}\right.$$
  
  

• $\rho(x,y) = \rho(y,x)$
• $\rho(x,z) \le \rho(x,y) + \rho(y,z)$

2.

Is

$$\rho(x,y) = \sum_{i=1}^p x_i \log(x_i/y_i) + \sum_{i=1}^p y_i \log(y_i/x_i)$$

a distance measure? Constraints:

$$\sum_{i=1}^p x_i = \sum_{i=1}^p y_i = 1$$

and x_i, y_i > 0.

• Rewriting $\rho()$ as
  
  $$\rho(x,y) = \sum_{i=1}^p (x_i - y_i)\log(x_i/y_i)$$
  
  
  it's pretty obvious that $\rho(x,y) = \rho(y,x)$ and that $\rho(x,y) = 0$ iff x=y. But is it non negative? There's LOTS of ways to do this. There's a sleight-of-hand way using a useful factoid that $\log x \le x-1$. But that's another story. Here's the easy way - notice that $(x_i - y_i)\log(x_i/y_i) > 0$is always greater than zero for $x_i \ne y_i$ and identically zero if x_i = y_i. SO the beast is non-negative.

• Now the fun begins - is the ``triangle inequality'' satisfied? We need to compare
  
  $$\sum_{i=1}^p (x_i - z_i)\log(x_i/z_i) \le (?) \sum_{i=1}^p (x_i - y_i)\log(x_i/y_i) + \sum_{i=1}^p (y_i - z_i)\log(y_i/z_i)$$
  
  
  Splitting things up and dragging to one side we obtain
  
  $$\begin{eqnarray*}0 & \le (?) & -\sum_{i=1}^p (x_i\log x_i -x_i \log z_i - z_i\lo... ... ( y_i \log y_i - y_i \log z_i - z_i\log y_i +z_i \log z_i ) \\ \end{eqnarray*}$$
  
  Simplifying
  
  $$\begin{eqnarray*}0 & \le (?) & -\sum_{i=1}^p (-x_i \log z_i - z_i\log x_i)\\ &... ... & \sum_{i=1}^p ( y_i \log y_i - y_i \log z_i - z_i\log y_i) \\ \end{eqnarray*}$$
  
  Grouping terms
  
  $$\begin{eqnarray*}0 & \le (?) & \sum_{i=1}^p (x_i - y_i)\log( z_i/y_i) + (z_i - y_i) \log( x_i/y_i) \end{eqnarray*}$$
  
  As you can see, this is tricky for general p, at least on short notice. So we now invoke p=2 along with the contraints to obtain,
  
  $$\begin{eqnarray*}0 & \le (?) & (x_1 - y_1)\log( z_1/y_1) + (z_1 - y_1) \log( x_1... ... x_1)\log((1- z_1)/(1-y_1)) + (y_1 - z_1) \log((1- x_1)/(1-y_1)) \end{eqnarray*}$$
  
  Regrouping
  
  $$\begin{eqnarray*}0 & \le (?) & (x_1 - y_1)\log(\frac{z_1(1-y_1)}{y_1(1-z_1)}) + (z_1 - y_1) \log(\frac{(1-y_1)x_1}{y_1(1-x_1)} ) \end{eqnarray*}$$
  
  Let's make x₁ > y₁ and z₁ < y₁. The first term is negative because the term inside the log is smaller than 1. The second term is negative because the leading factor is negative while the term inside the log is greater than 1. So the RHS can be made negative.

  Thus, when all is said and done, this is not a distance measure for p=2. I also suspect that one can find similar examples for larger pbut I did not dig into it.

  (The above was done quickly so please check the algebra for this part).

3.

Show rigorously that

$$\lim_{p \rightarrow \infty} \left ( \sum_{i=1}^N (\alpha^*)^p... ...} \right )^{1/p} = \alpha^* \equiv \max_i \vert x_i - y_i\vert$$

Well

$$\frac{\vert x_i - y_i\vert^p}{(\alpha^*)^p} \le 1$$

owing to the definition of $\alpha^*$. Thus we can bound the term from above and below as

$$\lim_{p \rightarrow \infty} \left ( (\alpha^*)^p \right )^{1/... ...m_{p \rightarrow \infty} \left ( (\alpha^*)^p N \right )^{1/p}$$

or

$$\alpha^* \le \lim_{p \rightarrow \infty} \left ( \sum_{i=1}^N... ...right )^{1/p} \le \alpha^* \lim_{p \rightarrow \infty} N^{1/p}$$

The result follows since $\lim_{p \rightarrow \infty} N^{1/p} = 1$.