Categories
Combinatorics I.S.I. and C.M.I. Entrance ISI M.Stat PSB

Lock and Key | ISI MStat 2017 PSB | Problem 6

This problem is a beautiful and elegant probability based on an elementary problem on how to effectively choose the key to a lock. This gives a simulation environment to problem 6 of ISI MStat 2017 PSB.

Problem

Suppose you have a 4-digit combination lock, but you have forgotten the correct combination. Consider the following three strategies to find the correct one:
(i) Try the combinations consecutively from 0000 to 9999.
(ii) Try combinations using simple random sampling with replacement from the set of all possible combinations.
(iii) Try combinations using simple random sampling without replacement from the set of all possible combinations.

Assume that the true combination was chosen uniformly at random from all possible combinations. Determine the expected number of attempts needed to find the correct combination in all three cases.

This problem really intrigues me, which gives me the excitement to solve and solve it.

Prerequisite

  • Expectation
  • Simple Random Sampling With and Without Replacement
  • Discrete Uniform Distribution
  • Geometric Distribution
  • Smoothing of Expectation \( E_X(E(Y|X)) = E(Y)\). When \(Y\) and \(X\) have some relationship, this helps us to calculate the expectation.

Solution

Consecutive Combination

\(U\) ~ Discrete Uniform \(({0, 1, 2, …, 9999})\)

Suppose, observe that if you select the keys consecutively, then for the true key \(U\), you need \(U\) attempts. (*)

\(N\) denotes the number of attempts required = \(U + 1\) due to (*)

\( E(N) = E(U) = \frac{9999}{2}\).

Simple Random Sampling With Replacement

This is something no one does, but let’s calculate this and see why we don’t do this and why we need to remember the keys that don’t work like SRSWOR, which is the next case.

\(U\) ~ Discrete Uniform \(({0, 1, 2, …, 9999})\)

\(N\) denotes the number of attempts required. \( E_U(E(N|U)) = E(N)\)

Let’s say, we have observed \(U\), which is fixed and we will calculate \(E(N|U)\).

Observe that \(N|U\) ~ Geom(\frac{1}{10000}\), since, there are unlimited trials and success occurs if you pick up the right key \(U\), which has a probability of \(\frac{1}{10000}\).

Therefore, \(E(N|U) = 10000\). Hence, \( E(N) = E_U(E(N|U)) = 10000\)

Let’s simulate it.

#Simple Random Sampling with Replacement

NUM = 0
size = 1000 # we have taken 1000 for easier calculation
key = sample(size,1)
number = NULL
random = sample(size,1)
N = 1
for (k in 1:1000) {
  number = NULL
  
  for (j in 1:100)
  {
    while (random != key) 
    {
      random = sample(size,1)
      N = N + 1
    }
    number = c(number,N)
    random = sample(size,1)
    N = 1
  }
  NUM = c(NUM,mean(number))
}
mean(NUM)
980.899
hist(NUM) 
#Note Replace = TRUE will not work, since, this is an open-ended program

Hence, this is validated by our simulation.

Simple Random Sampling Without Replacement

This is the sort of key selection, we usually do. Let’s investigate it.

\(U\) ~ Discrete Uniform \(({0, 1, 2, …, 9999})\)

\(N\) denotes the number of attempts required. \( E_U(E(N|U)) = E(N)\)

Let’s say, we have observed \(U\), which is fixed and we will calculate \(E(N|U)\).

\( p_i = P ((N|U) = i) = \frac{9999}{10000}.\frac{9998}{9999}.\frac{9997}{9998}…\frac{10001-i}{10002-i}.\frac{1}{10001-i} = \frac{1}{10000}\)

\(E(N|U) = \sum_{i = 0}^{9999} ip_i = \sum_{i = 0}^{9999} i \cdot \frac{1}{10000} = \frac{9999}{2} \). Hence, \( E(N) = E_U(E(N|U)) = \frac{9999}{2}\).

#Simple Random Sampling without Replacement
average = NULL
number = NULL
size = 10000
key = sample(size,1)
for (j in 1:1000)
{
for (i in 1:100) 
    {
      option = sample(size,size, replace = FALSE)
      v = which(option == key)
      number = c(number,v)
    }
average = c(average,mean(number))
}  
mean(average)
4996.567
hist(average, freq = FALSE)
 a graph of lock and key problem
Close to 4999.5

Stay tuned!

Stay Blessed!

Categories
Calculus I.S.I. and C.M.I. Entrance ISI M.Stat PSB

A Telescopic Sequence| ISI MStat 2018 PSB Problem 2

This is a beautiful problem from ISI MStat 2018 problem 2, which uses the cute little ideas of telescopic sum and partial fractions.

Problem

Let \(\{x_{n}\}_{n \geq 1}\) be a sequence defined by \(x_{1}=1\) and
$$
x_{n+1}=\left(x_{n}^{3}+\frac{1}{n(n+1)(n+2)}\right)^{1 / 3}, \quad n \geq 1
$$
Show that \(\{x_{n}\}_{n \geq 1}\) converges and find its limit.

Prerequisities

  • Limit of a Sequence
  • Partial Fraction \( \frac{1}{n(n+1)(n+2)} = \frac1{n(n+1)(n+2)}=\frac12\cdot\frac1n-\frac1{n+1}+\frac12\cdot\frac1{n+2} = -\frac12\left(\underbrace{\frac1{n+1} -\frac1n}\right)+\frac12\left(\underbrace{\frac1{n+2}-\frac1{n+1}}\right)\)
  • Telescopic Sum \( \sum_{i = 1}^{\infty} \left(\underbrace{\frac1{i+1} -\frac1i}\right) = \lim_{n \to \infty} \frac1n – 1 = -1 \)

Solution

\(x_{n+1} = (x_{n}^{3}+\frac{1}{n(n+1)(n+2)})^{1 / 3} \Rightarrow {x_{n+1}}^3 = x_{n}^{3}+\frac{1}{n(n+1)(n+2)}\)

\( \Rightarrow {x_{n+1}}^3 – x_{n}^{3} = \frac{1}{i(i+1)(i+2)}; x_1 = 1\).

\( \Rightarrow \sum_{i = 1}^{n-1} {x_{i+1}}^3 – x_{i}^{3} = \sum_{i = 1}^{n-1} \frac{1}{n(n+1)(n+2)} ; x_1 = 1\).

\( x_{n}^{3} – x_{1}^{3} = \sum_{i = 1}^{n-1} \frac{1}{i(i+1)(i+2)} = \sum_{i = 1}^{n-1} -\frac12\left(\underbrace{\frac1{i+1} -\frac1i}\right)+\frac12\left(\underbrace{\frac1{i+2}-\frac1{i+1}}\right)\)

\(\lim_{n \to \infty} (x_{n}^{3} – x_{1}^{3}) = \sum_{i = 1}^{\infty} \frac{1}{i(i+1)(i+2)} = \sum_{i = 1}^{\infty} -\frac12\left(\underbrace{\frac1{i+1} -\frac1i}\right)+\frac12\left(\underbrace{\frac1{i+2}-\frac1{i+1}}\right) = \frac14 \)

\( \lim_{n \to \infty} x_{n}^{3} = \frac54 \Rightarrow \lim_{n \to \infty} x_{n} = ({\frac54})^\frac13 \).

Categories
I.S.I. and C.M.I. Entrance ISI M.Stat PSB Linear Algebra

The Unique Decomposition | ISI MStat 2015 PSB Problem 3

The solution plays with Eigen values and vectors to solve this cute and easy problem in Linear Algebra from the ISI MStat 2015 problem 3.

Problem

Let \(A\) be a real valued and symmetric \(n \times n\) matrix with entries such that \(A \neq \pm I\) and \(A^{2}=I\).
(a) Prove that there exist non-zero column vectors \(v\) and \(w\) such that
\(A v=v\) and \(A w=-w\).
(b) Prove that every vector \(z\) has a unique decomposition \(z=x+y\)
where \(A x=x\) and \(A y=-y\).

This problem is from ISI MStat 2015 PSB ( Problem #3).

Prerequisites

  • Eigen values and Eigen vectors

Solution

(a)

Let’s say \(\lambda\) is an eigenvalue of \(A\). Let’s explore the possibilities of \(\lambda\).

\(Av= \lambda v \Rightarrow A^2v= {\lambda}^2 v \Rightarrow Iv= {\lambda}^2 v \Rightarrow v= {\lambda}^2 v \). Since, \( v\) is arbitrary, we get \({\lambda}^2 = 1 \Rightarrow \lambda = \pm 1\).

Since \(A\) is real symmetric, it has real eigenvalues, and the possibilities are 1 and -1. Since, \(A \neq \pm I\), there exists non-zero column vectors \(v\) and \(w\) such that \(A v=1.v\) and \(A w=-1.w\).

(b)

Suppose \(z\) has two decompositions \(z= x+y = x’+y’\) where \(A x=x\) and \(A y=-y\) and \(A x’=x’\) and \(A y’=-y’\).

Tberefore, \( A(x+y) = A(x’+y’) \Rightarrow Ax+Ay = Ax’+Ay’ \Rightarrow x – y = x’ – y’\).

But, we also have \( x+y = x’+y’\). Thus, by adding and subtracting, we get \(x = x’, y = y’ \).

Categories
I.S.I. and C.M.I. Entrance ISI M.Stat PSB Regression Techniques

Invariant Regression Estimate | ISI MStat 2016 PSB Problem 7

This cute little problem gives us the wisdom that when we minimize two functions at a single point uniquely, then their sum is also minimized at the same point. This Invariant Regression Estimate is applied to calculate the least square estimates of two group regression from ISI MStat 2016 Problem 7.

Problem- Invariant Regression Estimate

Suppose \({(y_{i}, x_{1 i}, x_{2 i}, \ldots, x_{k i}): i=1,2, \ldots, n_{1}+n_{2}}\) represents a set of multivariate observations. It is found that the least squares linear regression fit of \(y\) on \(\left(x_{1}, \ldots, x_{k}\right)\) based on the first \(n_{1}\) observations is the same as that based on the remaining \(n_{2}\) observations, and is given by
\(y=\hat{\beta}_{0}+\sum_{j=1}^{k} \hat{\beta}_{j} x_{j}\)
If the regression is now performed using all \(\left(n_{1}+n_{2}\right)\) observations, will the regression equation remain the same? Justify your answer.

Prerequisites

  • \(f(\tilde{x})\) and \(g(\tilde{x})\) are both uniquely minimized at \( \tilde{x} = \tilde{x_0}\), then \(f(\tilde{x}) + g(\tilde{x})\) is uniquely minimized at \( \tilde{x} = \tilde{x_0}\).

Solution

Observe that we need to find the OLS estimates of \({\beta}{i} \forall i \).

\(f(\tilde{\beta}) = \sum_{i = 1}^{n_1} (y – {\beta}_{0} – (\sum_{j=1}^{k} \hat{\beta}_{j} x_{j}))^2 \), where \(\tilde{\beta} = ({\beta}_0, {\beta}_1, …, {\beta}_k ) \)

\(g(\tilde{\beta}) = \sum_{i = n_1}^{n_1+n_2} (y – {\beta}_{0} – (\sum_{j=1}^{k} \hat{\beta}_{j} x_{j}))^2 \), where \(\tilde{\beta} = ({\beta}_0, {\beta}_1, …, {\beta}_k ) \)

\(\hat{\tilde{\beta}} = (\hat{{\beta}_0}, \hat{{\beta}_1}, …, \hat{{\beta}_k )} \)

\( h(\tilde{\beta}) = f(\tilde{\beta}) + g(\tilde{\beta}) = \sum_{i = 1}^{n_1+n_2} (y – {\beta}_{0} – (\sum_{j=1}^{k} \hat{\beta}_{j} x_{j}))^2 \), where \(\tilde{\beta} = ({\beta}_0, {\beta}_1, …, {\beta}_k ) \).

Now, \( h(\tilde{\beta})\) is the loss squared erorr under the grouped regression, which needs to be minimized with respect to \(\tilde{\beta} \).

Now, by the given conditions, \(f(\tilde{\beta})\) and \(g(\tilde{\beta})\) are both uniquely minimized at \( \hat{\tilde{\beta}}\), therefore \(h(\tilde{\beta}) = f(\tilde{\beta}) + g(\tilde{\beta})\) will be uniquely minimized at \(\hat{\tilde{\beta}}\) by the prerequisite.

Hence, the final estimate of \(\tilde{\beta}\) will be \( \hat{\tilde{\beta}}\).

Categories
I.S.I. and C.M.I. Entrance ISI M.Stat PSB Probability

Discover the Covariance | ISI MStat 2016 Problem 6

This problem from ISI MStat 2016 is an application of the ideas of indicator and independent variables and covariance of two summative random variables.

Problem- Covariance Problem

Let \(X_{1}, \ldots, X_{n}\) ~ \(X\) be i.i.d. random variables from a continuous distribution whose density is symmetric around 0. Suppose \(E\left(\left|X\right|\right)=2\) . Define \( Y=\sum_{i=1}^{n} X_{i} \quad \text { and } \quad Z=\sum_{i=1}^{n} 1\left(X_{i}>0\right)\).
Calculate the covariance between \(Y\) and \(Z\).

This problem is from ISI MStat 2016 (Problem #6)

Prerequisites

  1. X has Symmetric Distribution around 0 \( \Rightarrow E(X) = 0\).
  2. \( |X| = X.1( X > 0 ) – X.1( X \leq 0 ) = 2X.1( X > 0 ) – X\), where \(X\) is a random variable.
  3. \( X_i\) and \(X_j\) are independent \(\Rightarrow\) \(g( X_i)\) and \(f(X_j)\) are independent.
  4. \(A\) and \(B\) are independent \(\Rightarrow Cov(A,B) = 0\).

Solution

\( 2 = E(|X|) = E(X.1(X >0)) – E(X.1(X \leq 0)) = E(2X.1( X > 0 )) – E(X) = 2E(X.1( X > 0 ))\)

\( \Rightarrow E(X.1( X > 0 )) = 1 \overset{E(X) = 0}{\Rightarrow} Cov(X, 1( X > 0 )) = 1\).

Let’s calculate the covariance of \(Y\) and \(Z\).

\( Cov(Y, Z) = \sum_{i,j = 1}^{n} Cov( X_i, 1(X_{j}>0))\)

\( = \sum_{i = 1}^{n} Cov( X_i, 1(X_{i}>0)) + \sum_{i,j = 1, i \neq j}^{n} Cov( X_i, 1(X_{j}>0)) \)

\( \overset{X_i \text{&} X_j \text{are independent}}{=} \sum_{i = 1}^{n} Cov( X_i, 1(X_{i}>0)) = \sum_{i = 1}^{n} 1 = n \).

Categories
I.S.I. and C.M.I. Entrance ISI M.Stat PSB Linear Algebra

Tracing the Trace | ISI MStat 2016 PSB Problem 3

This ISI MStat 2016 problem is an application of the ideas of tracing the trace and Eigen values of a matrix and using a cute sum of squares identity.

Problem- Tracing the Trace

Suppose A is an \(n × n\) real symmetric matrix such that
\(Tr(A^2) = T r(A) = n\). Show that all the eigenvalues of A are equal to 1.

This problem is from ISI MStat 2016 PSB ( Problem #3)

Prerequisites

  • Trace of a Matrix
  • Eigen values of \(A^n\) w.r.t to the eigen values of \(A\).
  • Sum of Squares \(\geq 0\).

Solution

\( Av = {\lambda}v \Rightarrow A^nv = {\lambda}^nv\).

Since, A is a real symmetric matrix, then all the eigen values of the matrix A are real say {\( {\lambda}_1, {\lambda}_2, …, {\lambda}_n\)}.

\(Tr(A^2) = \sum_{i=1}^{n} {{\lambda}_i}^2 = Tr(A) = \sum_{i=1}^{n} {{\lambda}_i} = n\)

\( \Rightarrow n\sum_{i=1}^{n} {{\lambda}_i}^2 = (\sum_{i=1}^{n} {{\lambda}_i})^2\)

\( \Rightarrow (n-1)\sum_{i=1}^{n} {{\lambda}_i}^2 = \sum_{i, j = 1, i \neq j }^{n} 2{\lambda}_i{\lambda}_j\)

\( \Rightarrow \sum_{i=1}^{n} ({{\lambda}_i – {\lambda}_j })^2 = 0\)

\( \Rightarrow {\lambda}_i = {\lambda}_j = \lambda \forall i \neq j \)

\( \Rightarrow Tr(A) = n\lambda = n \Rightarrow \lambda = 1\).

Categories
I.S.I. and C.M.I. Entrance ISI M.Stat PSB Probability

Inverse Uniform Distribution | ISI MStat 2007 PSB Problem 4

This problem is an interesting application of the inverse uniform distribution family, which has infinite mean. This problem is from ISI MStat 2007. The problem is verified by simulation.

Problem

The unit interval (0,1) is divided into two sub-intervals by picking a point at random from inside the interval. Denoting by \(Y\) and \(Z\) the
lengths of the long and the shorter sub-intervals respectively show that \(\frac{Y}{Z}\) does not have a finite expectation.

This is the 4th Problem ISI MStat 2008. Enjoy it.

Prerequisites

  • Distribution Function
  • Distribution Function of \( \frac{1}{X} \) in terms of the Distribution Function of \(X\).

Solution

\( \frac{Y}{Z} + 1 = \frac{Y+Z}{Z} = \frac{1}{Z} \), where \(Z\) is the shorter length of the broken stick.

So, \( E( \frac{Y}{Z}) = E(\frac{1}{Z}) – 1 \).

Let’s try to find the distribution of \(\frac{1}{Z}\).

Let \( U \) ~ Unif \((0,1)\) whcih denotes the random uniform cut.

Number line - Inverse Uniform Distribution

The shorter stick of length smaller than \( x\) can be achieved if the stick is cut either before \(x\) or it is cut after \( 1-x\).

Observe that \( P( Z \leq x) = P ( U \leq x ) + P ( U \geq 1 – x) = x + 1 – (1-x) = 2x \). This answer is natural since, the total valid length is \(2x\).

\( P( \frac{1}{Z} \leq z) = P ( Z \geq \frac{1}{z} ) = 1 – \frac{2}{z} \Rightarrow F_{\frac{1}{Z}}(z) = 1 – \frac{2}{z}\) if \( 2 \leq z < \infty \).

Therefore, \(f_{\frac{1}{Z}}(z) = \frac{2}{z^2}\) if \( 2 \leq z < \infty \).

Hence, \( E( \frac{Y}{Z}) = E(\frac{1}{Z}) – 1 = (\int_{2}^{\infty} \frac{2}{z} dz) – 1 = \infty \)

Simulation and Verification

Exercise: Prove that \(F_{\frac{Y}{Z}}(x) = \frac{(x-1)}{(x+1)}\) if \(1 \leq x < \infty \).

 u = runif(1000,0,1)
  w = 1 - u
  Z = pmin(u,w)
  Y = pmax(u,w)
  YbyZ = Y/Z
plot(ecdf(YbyZ), xlim = c(0,50))
x = seq(0, 50, 0.01)
curve((x - 1)/(x+1), from = 0, col = "red", add = TRUE)
Graph - Inverse Uniform Distribution
Red = Actual Distribution Function, Black = Simulated ECDF

The Mean moves really slowly to infinity ~ logx. Hence it is really hard to show it is going to \(\infty\). Also, the probability of occurrence of high value is almost 0. Hence, it really hard to show my simulation that the mean is \(\infty\). But, we can show that the mean of the maximum values is really large.

v = rep(0,200)
m = NULL
for ( i in 1:200)
{
  #v[i] = 100*i
  u = runif(10000,0,1)
  w = 1 - u
  Z = pmin(u,w)
  Y = pmax(u,w)
  YbyZ = Y/Z
  m = c(m, max(YbyZ))
}
mean(m) = 79079.43

Beware of the simulation, it can be totally counterintuitive. This is really enjoyable though.

Stay Tuned!

Categories
Experiment Design and Sample Survey I.S.I. and C.M.I. Entrance ISI M.Stat PSB Probability

Collect All The Toys | ISI MStat 2013 PSB Problem 9

Remember, we used to collect all the toy species from our chips’ packets. We were all confused about how many more chips to buy? Here is how, probability guides us through in this ISI MStat 2013 Problem 9.

Toys - ISI MStat 2013 Problem 9
Collect all the toys offer

Problem

Chips are on sale for Rs. 30 each. Each chip contains exactly one toy, which can be one of four types with equal probability. Suppose you keep on buying chips and stop when you collect all the four types of toys. What will be your expected expenditure?

Prerequisites

Solution

I am really excited to find the solution. Remember, in your childhood, you were excited to buy packets of chips to collect all the toys and show them to your friends. There was a problem, that you don’t have enough money to buy the chips. A natural question was how much money you have to spend?

See, the problem is right here! Let’s dive into the solution. Remember we have to be a little bit mathematical here.

Let’s see how we get the four new toys.

1st new toy \( \rightarrow \) 2nd new toy \( \rightarrow \) 3rd new toy \( \rightarrow \) 4th new toy.

\( N_1\) = The number of chips to be bought to get the first new toy.

\( N_2\) = The number of chips to be bought to get the second new toy after you got the first new toy.

\( N_3\) = The number of chips to be bought to get the third new toy after you got the second new toy.

\( N_4\) = The number of chips to be bought to get the fourth new toy after you got the third new toy.

Observe that the expected number of chips to be bought = \( E ( N_1 + N_2 + N_3 + N_4 \) = \(E (N_1) + E(N_2) + E(N_3) + E(N_4) \).

Now, can you guess what are the random variables \( N_1, N_2, N_3, N_4 \)?

There are all geometric random variables. ( Why? )

[ Hint : Success is when you don’t get the already observed toys ]

Observe that \( N_i\) ~ Geom(\(\frac{4-i}{4}\)) ( Why? )

If \(N\) ~ Geom(\(p\)), then \(E(N) = \frac{1}{p}\).

Therefore, the required number of chips to be brought is \( 4 \times \sum_{i=1}{4} \frac{1}{4} = 8 + \frac{1}{3}\).

Therefore, you can guess, what will be the answer if there are \(n\) toys? ( \(n H_n\) ) , where \(H_n\) is the nth harmonic number.

Simulation and Verification

v = NULL
N = 0
n = 4  #number of toys
init = rep(0,n)
toy = rep(0,n)
True = rep(TRUE,n)
for (j in 1:10000)
{
  for (i in 1:100) 
  {
    s = sample(4,1)
    toy[s] = toy[s] + 1
    N = N + 1
    if (identical (toy > init, True))
    {
      break
    }
  }
v = c(v,N)
N = 0
toy = rep(0,n)
}
mean(v) = # 8.3214

Therefore, it is verified by simulation.

This image has an empty alt attribute; its file name is image-4.png
This is the histogram of the mean, which is expected to be around 8.33

Stay Tuned! Stay Shambho!

Categories
Calculus I.S.I. and C.M.I. Entrance ISI M.Stat PSB

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!

Categories
I.S.I. and C.M.I. Entrance ISI M.Stat PSB Linear Algebra

Eigen Values | ISI MStat 2019 PSB Problem 2

This post based on eigen values of matrices and using very basic inequalities gives a detailed solution to ISI M.Stat 2019 PSB Problem 2.

Problem

Let \(A\) and \(B\) be \(4 \times 4\) matrices. Suppose that \(A\) has eigenvalues \(x_{1}, x_{2}, x_{3}, x_{4}\) and \(B\) has eigenvalues \(\frac{1}{x_{1}}, \frac{1}{x_{2}}, \frac{1}{x_{3}}, \frac{1}{x_{4}}\) where each \(x_{i}>1\)
(a) Prove that \(A+B\) has at least one eigenvalue greater than 2.
(b) Prove that \(A-B\) has at least one eigenvalue greater than 0.
(c) Give an example of \(A\) and \(B\) so that 1 is not an eigenvalue of \(AB\).

Prerequisites

  • Trace of a Matrix
  • AM – GM Inequality
  • Pigeon Hole Principle: Let the average of a set of positive numbers be \(\mu\). Use the pigeonhole principle to show that there exists at least one number less than or equal to \(\mu\).
  • Algebra of Diagonal Matrices
  • Eigenvalues of a Diagonal Matrix are the diagonal elements.

Solution

(a)

Consider the trace of \(A+B\).

Mean of the eigen values of \(A\) + \(B\) = \( \frac{Tr(A+B)}{4}\) = \(\frac{Tr(A)+ Tr(B)}{4}\) = \( \frac{x_{1} + x_{2} + x_{3} + x_{4}+ \frac{1}{x_{1}} + \frac{1}{x_{2}} + \frac{1}{x_{3}} + \frac{1}{x_{4}}}{4} \) = \( \frac{\sum_{i = 1}^{4}(x_{i} + \frac{1}{x_{i}})}{4} \overset{x_{i} + \frac{1}{x_{i}} \geq 2}{\geq} 2 \). [ Hint: AM – GM Inequality ].

Now, use Pegion Hole Principle as mentioned in the prerequisites.

(b)

Mean of the eigen values of \(A\) – \(B\) = \( \frac{Tr(A-B)}{4}\) = \(\frac{Tr(A) – Tr(B)}{4}\) = \( \frac{x_{1} + x_{2} + x_{3} + x_{4} – \frac{1}{x_{1}} – \frac{1}{x_{2}} – \frac{1}{x_{3}} – \frac{1}{x_{4}}}{4} \) = \( \frac{\sum_{i = 1}^{4}(x_{i} – \frac{1}{x_{i}})}{4} \overset{x_{i} – \frac{1}{x_{i}} > 0}{>} 0 \). [ Hint: \( a > 1 \Rightarrow a^2 > 1\).]

Now, use Pegion Hole Principle as mentioned in the prerequisites.

(c)

Let’s take \(A = diag( 2, 3, 4, 5)\) and \( B = diag( \frac{1}{2} , \frac{1}{3} , \frac{1}{4} . \frac{1}{5} ) \). Now observe that \(A\) and \(B\) satisfy the given conditions.

\( AB = I\). But \( I\) has an eigenvalue 1.

So, what to do? We want none of the diagonal values of \(AB\) to be not 1.

Take, \(A = diag( 2, 3, 4, 5)\) and \( B = diag( \frac{1}{3} , \frac{1}{2} , \frac{1}{5} , \frac{1}{4} ) \). ow observe that \(A\) and \(B\) satisfy the given conditions.

\( AB = diag( \frac{2}{3} , \frac{3}{2} , \frac{4}{5} . \frac{5}{4} )\), which has no eigen value 1.

Stay tuned!