Approximate Probability Distribution Function

I am trying to approximate a large discreet probability distribution function using a histogram with a small number of entries. I.e., create a piece-wise first-order polynomial approximation for a monotonic function using a minimal number of segments/pieces.

I dont have an extensive background in statistics but I suspect this is a very common problem that was studied/solved already. It must be the most straight-forward and intutitive way to approximate a non-linear function. I am looking for any pointers related to this..

A (more) formal definition of the problem:

• Input:

Assume an array is given that contains a finite number of entries y_i. Let PDF = {y_1, ..., y_n} denote this array. Also assume that the number of entries in the array, n = |PDF|, is finite and known. The PDF has the following properties:

 - y_1 >= y_2 >= ... >= y_n

- y_i \in (0, 1]

- \sum{y_i} = 1


Esentially, this PDF array represents a discreet probability distribution function where the items are already sorted according to their frequency/probability and numbered between 1 ... n. Therefore, PDF represents a monotonically decreasing discreet function.

• Output:

Let uniq(PDF) be the number of distinct y_i values in the PDF. Obviously uniq(PDF) <= n. The goal is to find another array PDF' with the same PDF-like properties that approximates the original PDF:

 - y'_1 >= y'_2 >= ... >= y'_n

- y'_i \in (0, 1]

- \sum{y'_i} = 1 and,

- minimal ord(PDF') such that the normalized square error between PDF/PDF' is bounded.
This is equivalent to \sum{(y_i-y'_i)^2}/\sum{y_i^2} < given_error_bound.


In other words, all of this means that I want to represent the orginal PDF in the most compact way possible given a certain required level of accuracy.

For example, the original PDF can have billions of distinct y_i probability entries. I want a new PDF' that has only a few distinct y'_i entries (i.e. in the order of 10) that accurately represents the original PDF and can be expressed as (count, y'_i) pairs.

** Alternative formulations:**

• Continous PDF equivalent:

Assume a continous monotonically decreasing function f:[0,1] -> [0, 1] with \int{f(i)} = 1. Find function f':[0,1] -> [0,1] defined by n points (x_1, y_1), ... , (x_n, y_n), x_i < x_i+1, y_i < y_i+1, such that f'(k) = f(x_n), where x_n = max(x_i, x_i <= k) (essentially the original function f is represented by a multi-step function f').

Variations of the problem:

• The PDF can be replaced with a continous function if this makes the problem easier.

• The PDF can be replaced with its corresponding CDF (the sum/integral of the PDF), either in the discreet or continous variations. The goal will be now to find a new CDF' that uses n points to interpolate the original CDF.

• Simplify the problem by assuming that the number of points for the PDF' approximation is fixed/given. How to find the location of these points (i.e., how to distribute these points) such that the total error is minimized?

• A histogram isn't piecewise first order, it's a step function (zeroth order). Are you conflating frequency polygon with histogram? – Glen_b Sep 29 '14 at 17:23
• I think I did not express myself well enough.. You are right that a PDF/histogram is piecewise zeroth order. However, if you take items/multiple bins together that is not longer the case. – Radu Sep 29 '14 at 17:33
• What do you mean by "take multiple bins together"? Unless you're doing something further to the data (such as joining the bin centers, making it something other than a histogram), it's still a histogram and so still zeroth order. If you join the centers of the horizontal pieces with line segments ... you have a frequency polygon, not a histogram. Can you clearly describe what you intend? – Glen_b Sep 29 '14 at 17:46
• Sorry for the premature reply. I am still getting used to the website... My full response: You are right that a PDF/histogram is piecewise zeroth order so my words are inaccurate. I was thinking that the CDF' for the PDF' approximation is composed of multiple straight lines, which translates into a first-order approximation (I am thinking in CDF terms about the problem although is easier to express it in PDF terms). As a side note, a first order interpolation histogram (this might be a frequency polygon as you say) is a more complex form / more general form of this problem. – Radu Sep 29 '14 at 17:49
• To sum it up: (1) I was thinking about the CDF where a zeroth order PDF approximation translates into a first order CDF approximation. (2) Solving the problem for any order (zero, first, etc.) is just as good (for me at least). – Radu Sep 29 '14 at 17:53