7
$\begingroup$

Say I have a 1-dimensional continuous random variable $X$, with PDF $f(X)$, CDF $F(X)$ and inverse CDF $F^{-1}$. What is the best way to discretize $X$?

To keep things clear, let $Y$ denote the discretized version of $X$, and let $g(Y)$, $G(Y)$ and $G^{-1}$ refer to the PMF, CDF and inverse CDF of $Y$.

Ideally, I would like for $E[X] = E[Y]$ and $Var(X) = Var(Y)$. However, I understand if these properties cannot hold for finite $N$ due to discretization error.

Some thoughts:

  • Should I just discretize $X$ into $N$ equally spaced points? Or should I discretize more at regions of high probability, by first discretizing a Uniform $[0,1]$ into equidistant points $u_1,u_2...u_N$ and then generating discrete values $Y_1 = F^{-1}(u_1), Y_2 = F^{-1}(u_2)$ and $Y_N = F^{-1}(u_N)$

  • Say I have discretized values $Y_1, Y_2... Y_N$. What is the best way to create $g(Y)$, $G(Y)$ and $G^{-1}$ from these values? My thoughts here are that each $Y_k$ corresponds to an interval of $X$ with width $w_k$, and that the $Y_k$ should be the "midpoints" of these intervals. That is, $g(Y_k) = p(Y_k - w_k < X < Y_k + w_k) = F(Y_k + w_k) - F(Y_k - w_k)$.

$\endgroup$
  • 1
    $\begingroup$ What exactly is your goal with this discretization? Can you say anything about the application? I asked a similar question recently, stats.stackexchange.com/questions/13054/…, where the goal was to maintain the properties of the distribution as closely as possible while inheriting the conveniences of having a discrete sample space. $\endgroup$ – Macro Jul 21 '11 at 16:12
  • $\begingroup$ @Macro The application is in stochastic programming. I am trying to obtain the expected value of an optimization problem (in the form of a linear program), which has a random variable as one of its parameters. Technically, I can only solve the optimization when the RV takes on a random parameter. I need to discretize, and keep N as small as possible, because solving the optimization problem takes a lot of time. $\endgroup$ – Berk U. Jul 21 '11 at 16:24
  • 3
    $\begingroup$ So essentially you're trying to approximate an integral of the form $\int g(x) f(x) dx$ where $g(x)$ is the solution to your optimization problem and is expensive to calculate. Have you consider some quadrature routines? You might be able to estimate the integral with far fewer evaluations of $g(x)$ than the monte carlo method you want to use. If $f(x)$ is approximately the Gaussian density, you could estimate the integral very cheaply using Gauss-Hermite quadrature. $\endgroup$ – Macro Jul 21 '11 at 16:32
  • $\begingroup$ Yeap! This is actually part of a larger research project about how Monte Carlo procedures perform in this case. I essentially need to carry out the discretization to validate the results and have something to compare them to. $\endgroup$ – Berk U. Jul 21 '11 at 16:41
7
$\begingroup$

Hint: quantization might be a better keyword to search information.

Designing an "optimal" quantization requires some criterion. To try to conserve the first moment of the discretized variable ... sounds interesting, but I don't think it's very usual.

More frequently (especially if we assume a probabilistic model, as you do) one tries to minimize some distortion: we want the discrete variable to be close to the real one, in some sense. If we stipulate minimum average squared error (not always the best error measure, but the most tractable), the problem is well known, and we can easily build a non-uniform quantizer with minimum rate distortion, if we know the probability of the source; this is almost a synonym of "Max Lloyd quantizer".

Because a non-uniform quantizer (in 1D) is equivalent to pre-applying a non-linear transformation to a uniform quantizer, this kind of transformation ("companding") (in probabilistic terms, a function that turns our variable into a quasi-uniform) are very related to non uniform quantization (sometimes the concepts are used interchangeably). A pair of venerable examples are the u-Law and A-Law specifications for telephony.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Here is one simple idea that may work. If $X$ has distribution $F$, draw a "large" i.i.d. sample $(x_1,\dots,x_n)$ from $F$. Construct the empirical distribution function of this sample as $$ \hat{F_n}(t) = \frac{1}{n} \sum_{i=1}^n I_{[x_i,\infty)}(t) \, , $$ and treat $\hat{F_n}$ as the distribution function of $Y$, the "discretization" of $X$. This way, $Y$ assumes the values $x_1,\dots,x_n$ with equal probability $1/n$. How large must $n$ be, will depend on the details of your application. I don't claim that this is "best" in any way.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.