# What is the best way to discretize a 1D continuous random variable?

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)$.

• 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. – Macro Jul 21 '11 at 16:12
• @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. – Berk U. Jul 21 '11 at 16:24
• 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. – Macro Jul 21 '11 at 16:32
• 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. – Berk U. Jul 21 '11 at 16:41

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.