pending
    

Exercise 2 (20 points):

Some years ago, greek video-club chain Seven had the following offer to their  customers: every time a customer rented a DVD, he was given a random coupon with the title of the  Academy awards (Oscars) winner movie written on it. The first person to gather the coupons with all the  unique winner-movie titles won a 10-day vacation on a Caribbean island. If at that time, there were 75  unique such titles, and these titles were uniformly assigned to coupons, find the expected number of DVDs one had to rent in order to gather all of them.  

   ....
.
.

Exercise 3 (20 points):

Assume two d-dimensional real vectors x and y. And denote by xi (yi) the value in the i-th coordinate of x (y). Prove or disprove the following statements:

1. Distance function     =\(L_1\left(x,y\right)=\sum_{i=1}^d\left|x_{i-}y_i\right|\) is a metric. (5 points)

A distance function that satisfies all the below properties  is called a metric
Proof:
i. non-negativity:-
\(Consider\ D\left(x,y\right)\ge0\ \forall\ x,y\ \epsilon\ R\)   --------------------- equation 1
\(\Rightarrow\ D\left(x,y\right)=\sum_{i=1}^d\left|x_i-y_i\right|\)
\(\Rightarrow\ D\left(-x,-y\right)=\sum_{i=1}^d\left|-x_i+y_i\right|\)
 \(\Rightarrow\ D\left(-x,-y\right)=\sum_{i=1}^d\left|-1\right|\left|x_i-y_i\right|\)                      (because \(\left|x-y\right|=\ \ \left|-1\right|\cdot\left|y-x\right|\))
\(\Rightarrow\ D\left(-x,-y\right)=\sum_{i=1}^d\left|x_i-y_i\right|\)
Using Equation 1 we can say that \(\ D\left(-x,-y\right)\ge0\)
Alternate Proof: The formula consists of a sum of a modulus (|x-y|)which would always be positive  for all values of x and y because modulus of a number is always positive.
ii. Isolation
 \(d\left(x,y\right)=0\ \Leftrightarrow\ x=y\)
\(Given\ D\left(x,y\right)=\sum_{i=1}^d\left|x_i-y_i\right|\)
Considering x=y
\(\Rightarrow\ D\left(x,y\right)=\sum_{i=1}^d\left|x_i-x_i\right|\) (because x=y)
 \(\Rightarrow\ D\left(x,y\right)=\sum_{i=1}^d\left|0\right|=0\)
iii. Symmetry
\(d\left(x,y\right)=d\left(y,x\right)\)
 \(D\left(x,y\right)=\sum_{i=1}^d\left|x_i-y_i\right|\)                                                                                                 
\(D\left(y,x\right)=\sum_{i=1}^d\left|y_i-x_i\right|\)
        if \(x-y\ge0\)    then  \(y-x\le0\)                                                              |                          if  \(x-y\le0\)    then \(y-x\ge0\)                          
    \(\Rightarrow\left|x-y\right|=x-y\)          and         \(\Rightarrow\left|y-x\right|=x-y\)               |                          \(\Rightarrow\left|x-y\right|=y-x\)  and    \(\Rightarrow\left|y-x\right|=y-x\)
 \(\Rightarrow\sum_{i=1}^d\left|x_i-y_i\right|=\sum_{i=1}^d\left|y_i-x_i\right|\)                                                     |                         \(\Rightarrow\sum_{i=1}^d\left|x_i-y_i\right|=\sum_{i=1}^d\left|y_i-x_i\right|\)       
Therefore,
\(D\left(x,y\right)=D\left(y,x\right)\)
iv. triangle inequality , 
\(d\left(x,z\right)\le d\left(x,y\right)+d\left(y,z\right)\) 
To Prove: \(\left|x-z\right|\le\left|x-y\right|+\left|y-z\right|\)