Python代写 | CS 237: Homework 6 Programming Portion


Exercise 1: Data structures for discrete RVs: PDFs and CDFs

In this exercise, we’ll build simple data structures to represent PDFs and CDFs of discrete random
variables (RVs).

As input, the user will provide a dictionary of values of a discrete RV and their associate percentage
probabilities. At the end of this notebook are some test cases involving frequencies of English letters
in documents and Super Bowl win probabilities of NFL teams. You’re welcome and encouraged to
try others, including larger datasets.

Concretely, the input is a Python dictionary with tuples of the form (RV_value: percentage_prob)
For example, if the user creates an RV named X with ‘{4: 50.0, 22: 30.0, 2: 20.0}’, we will want to
represent the following information (in sorted order), sorted by values:

PDF f(X): Pr[X = 2] = 0.2, Pr[X = 4] = 0.5, Pr[X = 22] = 0.3
CDF F(X): Pr[X < 2] = 0, Pr[2 <=X < 4] = 0.2, Pr[4 <= X < 22] = 0.7, Pr[22 <= X] = 1

We also need to check that the user has specified a valid PDF (probabilities sums to 1).

To manipulate PDFs and CDFs efficiently, we will store the values in sorted order. To be space-
efficient, we only need to store those values where the PDF has mass, or equivalently, where the
CDF has a discontinuity. So our random variable X can be described by:

3 Exercise 1a) Complete the implementation of the init method
of the RV class below

class RV:
# Create an RV from a user-specified dictionary. See examples of input␣
# Member variables are
# self.values (sorted list)
# self.PDF (list of probabilities)
# self.CDF (list of cumulative probabilities)
def __init__(self, dict):
# create sorted list of values
self.values = []
for x in dict:
self.values.sort() # create a sorted list of outcomes
# create PDF
self.PDF = [None] * len(self.values)
for i in range(len(self.values)):
pct = dict[self.values[i]]
self.PDF[i] = round(pct * 10000)/1000000
# round to 8 decimal digits to avoid numerical precision problems
# see what bad things happen if you just use pct/100
# compute F_X from f_X
self.CDF = [None] * len(self.values)

4 Exercise 1b) Complete the implementation of prob() below

# Find the leftmost index i in sorted list a such that a[i] == x
def index(a, x):
i = bi.bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
return None
# Given an RV value return its likelihood: Pr[R=value]
def prob (R, value):
# We expect you to call index() above