Get inspired by the success stories of our students in IIT JAM MS, ISI  MStat, CMI MSc DS.  Learn More 

Two-Faced Problem | ISI MStat 2013 PSB Problem 1

This post has a two-faced problem, which gives you both an analytical and statistical insight into ISI MStat 2013 PSB Problem 1.

Problem

If a_{1}<a_{2}<\ldots \ldots \ldots<a_{m}, b_{1}<b_{2}<\ldots \ldots < b_{n} and also \sum_{i=1}^{m}|a_i - x|=\sum_{j=1}^{n}|b_j - x|, where
x is any real number then prove that a_i=b_i for all i and n=m.

Prerquisites

  • Non - Differentiability of |x - a| at x = a.
  • f(x) is non differentiable on set A and g(x) is non differentiable on set B, then f(x) + g(x) is non differentiable on A \cup B.
  • Minimization of \sum_{i=1}^{m}|a_i - x| at x = median. In other words, the Median minimizes the Sum of Absolute Deviation.

Solution I (Calculus)

f(x) = \sum_{i=1}^{m}|a_i - x| has non - differentiability at a_{1}<a_{2}<\ldots \ldots \ldots<a_{m}, since each of |a_i - x| is non differentiable at a_i. The result follows from the first two results in the pre-requisites.

Now, since, \sum_{i=1}^{m}|a_i - x|=\sum_{j=1}^{n}|b_j - x|, the set of non differentiability points of f(x) = \sum_{i=1}^{m}|a_i - x| is a_{1}<a_{2}<\ldots \ldots \ldots<a_{m} while the set of non differentiability points of g(x) = \sum_{i=1}^{n}|b_j - x| is b_{1}< b_{2}<\ldots \ldots \ldots<b_{n}. f(x) = g(x).

Graph of Two-Faced Problem
f(x) = \sum_{i=1}^{5}|i - x|

Thus, {a_{1}<a_{2}<\ldots \ldots \ldots<a_{m}} = {b_{1}< b_{2}<\ldots \ldots \ldots<b_{n}}.

Therfore, a_i=b_i for all i and n=m.

Solution II ( Statistical Perspective )

The Median Minimizes the Sum of Absolute Deviation has really elegant proof here.

We will see the idea from a different perspective with respect to the diagrams and use the idea to prove the actual problem.

2 Graphs for the problem

For the set { 1 < 2 < 3 < 4 < 5 }, the median is 3. Hence, the f(x) = \sum_{i=1}^{5}|i - x| is minized at x = 3.

But for the set { 1 < 2 < 3 < 4 < 5 < 6}, the median is \frac{3+4}{2}. Rather the f(x) = \sum_{i=1}^{6}|i - x| is minized at 3 \leq x \leq 4. Let's for the time being call \{3,4\} as the median of { 1 < 2 < 3 < 4 < 5 < 6}.

Now, the next idea is simple yet elegant.

A_0 = {a_{1}<a_{2}<\ldots \ldots \ldots<a_{m}}; B_0 = {b_{1}< b_{2}<\ldots \ldots \ldots<b_{n}}.

A = A_0; B = B_0.

f_A(x) = \sum_{a \in A}|a - x| = g_B(x) = \sum_{b \in B}|b - x|.

Step 1 : Take the minimum of f(x) and g(x). They must be equal.

Step 2 : Therefore, median of A = median o f B.

Step 3 : A = A - median of A; B = B - median of B. This means, we delete the equal elements in both A and B.

Step 4 : Go to Step 1. Stop if A = \phi = B

This will converge only if A_0 = B_0.

Hence, a_i=b_i for all i and n=m.

Thus, we gave two different views of the same problem.

Hope you enjoyed it.

Stay Tuned!

This post has a two-faced problem, which gives you both an analytical and statistical insight into ISI MStat 2013 PSB Problem 1.

Problem

If a_{1}<a_{2}<\ldots \ldots \ldots<a_{m}, b_{1}<b_{2}<\ldots \ldots < b_{n} and also \sum_{i=1}^{m}|a_i - x|=\sum_{j=1}^{n}|b_j - x|, where
x is any real number then prove that a_i=b_i for all i and n=m.

Prerquisites

  • Non - Differentiability of |x - a| at x = a.
  • f(x) is non differentiable on set A and g(x) is non differentiable on set B, then f(x) + g(x) is non differentiable on A \cup B.
  • Minimization of \sum_{i=1}^{m}|a_i - x| at x = median. In other words, the Median minimizes the Sum of Absolute Deviation.

Solution I (Calculus)

f(x) = \sum_{i=1}^{m}|a_i - x| has non - differentiability at a_{1}<a_{2}<\ldots \ldots \ldots<a_{m}, since each of |a_i - x| is non differentiable at a_i. The result follows from the first two results in the pre-requisites.

Now, since, \sum_{i=1}^{m}|a_i - x|=\sum_{j=1}^{n}|b_j - x|, the set of non differentiability points of f(x) = \sum_{i=1}^{m}|a_i - x| is a_{1}<a_{2}<\ldots \ldots \ldots<a_{m} while the set of non differentiability points of g(x) = \sum_{i=1}^{n}|b_j - x| is b_{1}< b_{2}<\ldots \ldots \ldots<b_{n}. f(x) = g(x).

Graph of Two-Faced Problem
f(x) = \sum_{i=1}^{5}|i - x|

Thus, {a_{1}<a_{2}<\ldots \ldots \ldots<a_{m}} = {b_{1}< b_{2}<\ldots \ldots \ldots<b_{n}}.

Therfore, a_i=b_i for all i and n=m.

Solution II ( Statistical Perspective )

The Median Minimizes the Sum of Absolute Deviation has really elegant proof here.

We will see the idea from a different perspective with respect to the diagrams and use the idea to prove the actual problem.

2 Graphs for the problem

For the set { 1 < 2 < 3 < 4 < 5 }, the median is 3. Hence, the f(x) = \sum_{i=1}^{5}|i - x| is minized at x = 3.

But for the set { 1 < 2 < 3 < 4 < 5 < 6}, the median is \frac{3+4}{2}. Rather the f(x) = \sum_{i=1}^{6}|i - x| is minized at 3 \leq x \leq 4. Let's for the time being call \{3,4\} as the median of { 1 < 2 < 3 < 4 < 5 < 6}.

Now, the next idea is simple yet elegant.

A_0 = {a_{1}<a_{2}<\ldots \ldots \ldots<a_{m}}; B_0 = {b_{1}< b_{2}<\ldots \ldots \ldots<b_{n}}.

A = A_0; B = B_0.

f_A(x) = \sum_{a \in A}|a - x| = g_B(x) = \sum_{b \in B}|b - x|.

Step 1 : Take the minimum of f(x) and g(x). They must be equal.

Step 2 : Therefore, median of A = median o f B.

Step 3 : A = A - median of A; B = B - median of B. This means, we delete the equal elements in both A and B.

Step 4 : Go to Step 1. Stop if A = \phi = B

This will converge only if A_0 = B_0.

Hence, a_i=b_i for all i and n=m.

Thus, we gave two different views of the same problem.

Hope you enjoyed it.

Stay Tuned!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Knowledge Partner

Cheenta is a knowledge partner of Aditya Birla Education Academy
Cheenta

Cheenta Academy

Aditya Birla Education Academy

Aditya Birla Education Academy

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.
JOIN TRIAL
support@cheenta.com
Menu
Trial
Whatsapp
ISI Entrance Solutions
ISI CMI Self Paced
rockethighlight