Assignment 1 Solution

All members of the group should work on all parts of the assignment. Copying across groups or from other sources is not allowed. We will adopt a zero-tolerance policy against any violation.

Submission instructions:

    1. You should type out a report containing all the answers to the written problems in Word (with the equation editor) or using Latex, or write it neatly on paper and scan it. In either case, prepare a single pdf le.

    2. Put the pdf le and the code for the programming parts all in one zip le. The pdf should contain the names and ID numbers of all students in the group within the header. The pdf le should also contain instructions for running your code. Name the zip le as follows: A1-IdNumberOfFirstStudent-IdNumberOfSecondStudent.zip. (If you are doing the assignment alone, the name of the zip le is A1-IdNumber.zip).

    3. Upload the le on moodle BEFORE 11:55 pm on the due date (i.e. 16th August). We will nevertheless allow and not penalize any submission until 6:00 am on the following day (i.e. 17th August). No assignments will be accepted thereafter.

    4. Note that only one student per group should upload their work on moodle.

    5. Please preserve a copy of all your work until the end of the semester.

Questions:
1. Given n distinct values fxign    with mean    and standard deviation    , prove that for all i, we have jxi    j
p    i=1


n 1. How does this inequality compare with Chebyshev’s inequality as n increases? (give an informal answer) [7+3=10 points]

2. Given n values fxigni=1 having mean , median and standard deviation , prove that j j . Assume n is even. [10 points]

    3. In a certain town, there exist 100 rickshaws out of which 1 is red and 99 are blue. A person XYZ observes a serious accident caused by a rickshaw at night and remembers that the rickshaw was red in color. Hence, the police arrest the driver of the red rickshaw. The driver pleads innocence. Now, a lawyer decides to defend the hapless rickshaw driver in court. The lawyer ropes in an opthalmologist to test XYZ’s ability to di erentiate between the colors red and blue, under illumination conditions similar to those that existed that fateful night. The opthalmologist suggests that XYZ sees red objects as red 99% of the time and blue objects as red 2% of the time. What will be the main argument of the defense lawyer? (In other words, what is the probability that the rickshaw was really a red one, when XYZ observed it to be red?) [10 points]

    4. A contestant is on a game show and is allowed to choose between three doors. Behind one of them lies a car, behind the other two there lies a stone. The contestant will be given whatever is behind the door that (s)he picked, and quite naturally (s)he wants the car. Suppose (s)he chooses the rst door, and the host of the show who knows what is behind every door, opens (say) the third door, behind which there lies a stone (without opening the rst door). The host now asks the contestant whether (s)he wishes to choose the second door instead of the rst one. Your task is to determine whether switching the contestant’s choice is going to


1

increase his/her chance of winning the car. Remember that the host is intelligent: (s)he is always going to open a door not chosen by the contestant, and is also going to open a door behind which there is a stone. You should approach this problem only from the point of view of conditional probability as follows. To this end, let C1; C2; C3 be events that the car is behind doors 1,2,3 respectively. Assume P (Ci) = 1=3; i 2 f1; 2; 3g.

    (a) Let Z1 be the event that the contestant chose door 1. Write down the value of P (CijZ1) for all i 2 f1; 2; 3g.

    (b) Let H3 be the event that the host opened door 3. Write down the value of P (H3jCi; Z1) for all i 2 f1; 2; 3g.

    (c) Clearly the conditional probability of winning by switching is P (C2jH3; Z1). This is equal to
P (H3jC2; Z1)P (C2; Z1). Evaluate this probability. Note that P (A1; A2) denotes the joint probability P(H3; Z1)

of events A1; A2.

(d) Likewise evaluate P (C1jH3; Z1).

(e) Conclude whether switching is indeed bene cial.

(f) Now let us suppose that the host were quite whimsical and decided to open one of the two doors not chosen by the contestant, with equal probability, not caring whether there was a car behind the door. In this case, repeat your calculations and determine whether or not it is bene cial for the contestant to switch choices. [2+2+5+5+1+5=20 points]

In the following problems, you can use the mean, median and standard deviation functions from MATLAB.

5. Generate a sine wave in MATLAB of the form y = 5 sin(2:2x + =3) where x ranges from -3 to 3 in steps of 0.02. Now randomly select a fraction f = 30% of the values in the array y (using MATLAB function ‘randperm’) and corrupt them by adding random values from 100 to 120 using the MATLAB function ‘rand’. This will generate a corrupted sine wave which we will denote as z. Now your job is to lter z using the following steps.

Create a new array ymedian to store the  ltered sine wave.

For a value at index i in z, consider a neighborhood N(i) consisting of z(i), 8 values to its right and 8 values to its left. For indices near the left or right end of the array, you may not have 8 neighbors in one of the directions. In such a case, the neighborhood will contain fewer values.

Set ymedian(i) to the median of all the values in N(i). Repeat this for every i.

This process is called as ‘moving median ltering’, and will produce a ltered signal in the end. Repeat the entire procedure described here using the arithmetic mean instead of the median. This is called as ‘moving average ltering’. Repeat the entire procedure described here using the rst quaritle (25 percentile) instead of the median. This is called as ‘moving quartile ltering’. Plot the original (i.e. clean) sine wave y, the corrupted sine wave z and the ltered sine wave using each of the three methods on the same gure in di erent colors. Introduce a legend on the plot ( nd out how to do this in MATLAB). Include an image of the plot in your report. Now compute and print the relative mean squared error between each result and the original clean sine wave. The relative mean squared error between y and its estimate y^ (i.e. the ltered

P
i(yi
y^i)2
.


i
yi2

signal - by any one of the di erent methods) is de ned as



Now repeat all the steps above using f = 60%, and include
the plot of the sine waves in your report, and

P



write down the relative mean square error values.

Which of these methods (median/quartile/arithmetic mean) produced better relative mean squared error? Why? Explain in your report. [5+5+4+3+3=20 points]

    6. Suppose that you have computed the mean, median and standard deviation of a set of n numbers stored in array A where n is very large. Now, you decide to add another number to A. Write a MATLAB function to update the previously computed mean, another MATLAB function to update the previously computed median, and yet another MATLAB function to update the previously computed standard deviation. Note


2

that you are not allowed to simply recompute the mean, median or standard deviation by looping through all the data. You may need to derive formulae for this. Include the formulae and their derivation in your report. Note that your MATLAB functions should be of the following form

function newMean = UpdateMean (OldMean, NewDataValue, n), function newMedian = UpdateMedian (oldMedian, NewDataValue, A, n), function newStd = UpdateStd (OldMean, OldStd, NewMean, NewDataValue, n).

Also explain, how would you update the histogram of A, if you received a new value to be added to A? (Only explain, no need to write code.) Note: For updating the median, you may assume that the array A is sorted in ascending order, that the numbers are all unique. For sorted arrays with a even number of elements, MATLAB returns the answer as (A(N=2) + A(N=2 + 1))=2. You may use MATLAB’s convention though it is not strictly required. [4+5+5+1 = 15 points]

    7. Determine using a mathematical formula and a computer algorithm the smallest number n of people such that the probability that at least two of them share their birthday is at least p where

p 2 f5; 10; 15; 20; 30; 40; 50; 60; 70; 80; 90; 95; 99; 99:99; 99:9999; 100g%. Plot a graph of n on Y axis versus p on X axis. The algorithm is to be implemented in MATLAB. [15 points]


















































3