Katkat
Back

Compute CDF from a PDF Function

UberData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your understanding of numerical integration techniques (specifically the trapezoidal rule) and your ability to implement a functional mapping of a continuous probability density function (PDF) into a discrete cumulative distribution function (CDF).

Problem Statement

You are provided with a function pdf(x) that represents the probability density of a continuous random variable. Your task is to implement a CDFCalculator class that approximates the cumulative distribution function P(X <= x) for any input x within a given range [a, b].

Since an analytical solution may not be available, you must use numerical integration. Use the trapezoidal rule to compute the integral of the PDF from the lower bound a to your target x.

Requirements

Implement the following interface:

class CDFCalculator:
    def __init__(self, pdf_func, a, b, n=1000):
        # pdf_func: A callable that returns the density at point x
        # a, b: The range over which to define the CDF
        # n: The number of trapezoids to use for numerical integration
        pass

    def get_cdf(self, x):
        # Returns the approximated P(X <= x) for x in [a, b]
        pass

Constraints

  • n represents the number of sub-intervals.
  • The approximation should handle values of x between a and b.
  • Assume pdf(x) is non-negative.

Example

If pdf(x) = 2*x on interval [0, 1], then get_cdf(0.5) should return approximately 0.25.

Edge Cases

  • What should the function return if x b?
  • How does the accuracy of the integration change with n?

Hints

Hint 1

Recall that the trapezoidal rule approximates the integral of a function by summing the areas of trapezoids created by connecting points (x_i, f(x_i)) and (x_{i+1}, f(x_{i+1})).

Hint 2

Precompute the PDF values at uniform intervals between 'a' and 'b' to avoid redundant function calls during the query phase.

Hint 3

For a query 'x', perform the integration only up to the largest interval endpoint less than or equal to 'x', and add a final partial trapezoid for the remaining segment.

Follow-up questions

  • How would you modify your implementation to support efficient O(log n) queries if the number of segments 'n' is very large?
  • How would you normalize your PDF numerically if the provided function does not integrate exactly to 1 over [a, b]?
  • What are the trade-offs between the trapezoidal rule and higher-order methods like Simpson's Rule in this context?