<jupyter_start><jupyter_text>The median of independent repeated  sampling<jupyter_code>%pylab inline<jupyter_output>Populating the interactive namespace from numpy and matplotlib<jupyter_text>The median of a distribution The median of a distribution $P$ is the value $m$ such that if $X\sim P$, then $P(X\le m)\ge\frac12$ and  $P(X\ge m)\ge\frac12$. If multiple values satisfy this condition, the median is their average.For example, for the biased die with distribution given byx123456$P_X$(x)0.10.20.10.30.10.2Since $P(X\le 4)=0.7\ge 0.5$ and $P(X\ge 4)=0.6\ge 0.5$, $m=4$.If the distribution was,x123456$P_X$(x)0.10.20.20.20.10.2then both 3 and 4 satisfy the two conditions, and the median is 3.5. While writing the following functions, note that the distribution $P=[x_1,\ldots x_k]$ represents $P_X(1)=x_1,\ldots,P_X(k)=x_k$.  Exercise 1 Write a function median_cal(P) that returns the median given a distribution P.* **Sample run** *```pythonprint(median_cal([0.1 0.2 0.1 0.3 0.1 0.2]))print(median_cal([0.99 0.01])```* **Expected Output** *```python41```<jupyter_code>def median_cal(P):
    acc0ToVal = 0;
    medianValues = []
    i = 0;
    for val in P:
        i = i + 1;
        acc0ToVal = acc0ToVal + val;
        accValToEnd = 1 + val - acc0ToVal;
        if (acc0ToVal >= 0.5 and accValToEnd >= 0.5):
            medianValues.append(i);
            
    return sum(medianValues) / len(medianValues);
#Check Function

assert median_cal([0.99,0.1])==1
assert median_cal([0.1,0.2,0.1,0.3,0.1,0.2])==4<jupyter_output><empty_output><jupyter_text>Median of a sample  If the distribution is given, as above, the median can be determined easily. In this problem we will learn how to approximate the median when the distribution is not given, but we are given samples that it generates. Similar to distributions, we can define the median of a set to be the set element $m'$ such that at least half the elements in the set are $\le m'$ and at least half the numbers in the collection are $\ge m'$. If two set elements satisfy this condition, then the median is their average. For example, the median of [3,2,5,5,2,4,1,5,4,4] is $4$ and the median of [2,1,5,3,3,5,4,2,4,5] is $3.5$.To find the median of a $P$ distribution via access only to samplesit generates, we obtain $n$ samples from $P$, caluclate their median $M_n$, and then repeat the process many times and determine the averageof all the medians.   Exercise 2 Write a function sample_median(n,P) that generates n random values using distribution P and returns the median of the collected sample.Hint: Use function random.choice() to sample data from P and median() to find the median of the samples* **Sample run** *```pythonprint(sample_median(10,[0.1 0.2 0.1 0.3 0.1 0.2])) print(sample_median(10,[0.1 0.2 0.1 0.3 0.1 0.2]))print(sample_median(5,P=[0.3,0.7])print(sample_median(5,P=[0.3,0.7])```* **Expected Output** *```python4.54.02.01.0```<jupyter_code>import random

def get_accum(P):
    accProb = [];
    acc = 0;
    for prob in P:
        acc = acc + prob;
        accProb.append(acc);
        
    # I had to disable this check because there were some invalid distribution
    # definitions on the quiz time. This should be enabled for real use.
    #if (acc != 1):
        #raise ValueError("The distribution probability accumulated doesn't sum to 1.");
    
    return accProb;

def custom_rng(accProb):
    randomNum = random.random();
    for j in range(len(accProb)):
        if(randomNum <= accProb[j]):
            return(j + 1);
        
        
def get_custom_sample(n, P):
    # Calculating accumulated probability.
    accProb = get_accum(P);
    
    # Creating random sample from given distribution.
    sampleSet = [];
    for i in range(n):
        sampleSet.append(custom_rng(accProb));
        
    return sampleSet;

def sample_median(n,P, debugPrint=False):
    distributionSize = len(P);
    
    sampleSet = get_custom_sample(n, P);
    
    # Counting the number of each element.
    sampleProb = [0] * distributionSize;
    for index in sampleSet:
        sampleProb[index - 1] = sampleProb[index - 1] + 1;
    
    # Getting the ratio of each index on the sample as the sample probability.
    sampleProb = list(map(lambda x: x / n, sampleProb));
    
    if (debugPrint):
        print("Sample set ratio: {0}".format(sampleProb));  
        print("Median found: {0}" .format(median_cal(sampleProb)));
    
    return median_cal(sampleProb);
#Check Function

assert abs(sample_median(10,[0.1,0.2,0.3,0.2,0.2])-3)<=1
assert abs(sample_median(25,[0.2,0.1,0.2,0.3,0.1,0.1])-3)<=1
assert abs(sample_median(10,[0.1, 0.2, 0.1, 0.3, 0.1, 0.2])-4)<=1

# Note that with smaller N values we get a low confidence on the sample set.
# If we increase N, the sample ratios will become closer with the real distribution.

print("Normal n:");
assert abs(sample_median(10,[0.1,0.2,0.3,0.2,0.2], True)-3)<=1
assert abs(sample_median(25,[0.2,0.1,0.2,0.3,0.1,0.1], True)-3)<=1
assert abs(sample_median(10,[0.1, 0.2, 0.1, 0.3, 0.1, 0.2], True)-4)<=1
print("");
print("n * 100:");
assert abs(sample_median(1000,[0.1,0.2,0.3,0.2,0.2], True)-3)<=1
assert abs(sample_median(2500,[0.2,0.1,0.2,0.3,0.1,0.1], True)-3)<=1
assert abs(sample_median(1000,[0.1, 0.2, 0.1, 0.3, 0.1, 0.2], True)-4)<=1<jupyter_output>Normal n:
Sample set ratio: [0.1, 0.2, 0.3, 0.1, 0.3]
Median found: 3.0
Sample set ratio: [0.2, 0.12, 0.16, 0.36, 0.08, 0.08]
Median found: 4.0
Sample set ratio: [0.0, 0.3, 0.0, 0.2, 0.1, 0.4]
Median found: 4.5

n * 100:
Sample set ratio: [0.106, 0.206, 0.28, 0.208, 0.2]
Median found: 3.0
Sample set ratio: [0.2132, 0.0968, 0.2004, 0.2924, 0.0996, 0.0976]
Median found: 3.0
Sample set ratio: [0.104, 0.204, 0.104, 0.28, 0.099, 0.209]
Median found: 4.0<jupyter_text>Exercise 3  Write a function expected_cal(P) that finds the expected value of the distribution P.<jupyter_code>def expected_cal(P):
    expectedValue = 0;
    i = 0;
    for prob in P:
        i = i + 1;
        expectedValue = expectedValue + i * prob;
    
    return expectedValue;
#Check function

assert expected_cal([0.25,0.25,0.25,0.25])==2.5
assert expected_cal([0.3,0.4,0.3])==2<jupyter_output><empty_output><jupyter_text>Exercise 4 In this exercise, we explore the relationship between the distribution median $m$, the sample median with $n$ samples, and $E[M_n]$,the expected value of $M_n$. Write a function average_sample_median(n,P), that return the average $M_n$ of 1000 samples of size n sampled from the distribution P.* **Sample run** *```pythonprint(average_sample_median(10,[0.2,0.1,0.15,0.15,0.2,0.2])) print(average_sample_median(10,[0.3,0.4,0.3]))print(average_sample_median(10,P=[0.99,0.01])```* **Expected Output** *```python3.78552.0041```<jupyter_code>def average_sample_median(n,P):
    medianAverage = 0;
    for i in range(1000):
        medianAverage = medianAverage + sample_median(n, P);
        
    return medianAverage / 1000;
#Check function
assert((average_sample_median(20,[0.4,0.6])-median_cal([0.4,0.6]))<=1e-3)
assert((average_sample_median(200,[0.1,0.2,0.3,0.1,0.1,0.2])-median_cal([0.1,0.2,0.3,0.1,0.1,0.2]))<=1)
print(average_sample_median(10,[0.2,0.1,0.15,0.15,0.2,0.2])); 
print(average_sample_median(10,[0.3,0.4,0.3]));
print(average_sample_median(10,P=[0.99,0.01]));<jupyter_output>3.764
1.984
1.0<jupyter_text>Quiz answers<jupyter_code>median_cal([0.12,0.04,0.12,0.12,0.2,0.16,0.16,0.08])
print(sample_median(5, [0.12,0.04,0.12,0.12,0.2,0.16,0.16,0.08]))
print(sample_median(50, [0.12,0.04,0.12,0.12,0.2,0.16,0.16,0.08]))
print(sample_median(500, [0.12,0.04,0.12,0.12,0.2,0.16,0.16,0.08]))
expected_cal([0.12, 0.04, 0.12, 0.12, 0.2, 0.16, 0.16, 0.08])
average_sample_median(100,[0.12, 0.04, 0.12, 0.12, 0.2, 0.16, 0.16, 0.08])
average_sample_median(1,[0.12, 0.04, 0.12, 0.12, 0.2, 0.16, 0.16, 0.08])<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup