So suppose we have a random variable $Z$ which can take values in $\left[-A, A \right]$. Suppose we do not know the exact distribution of $Z$.

Now if we take $N$ fixed disjoint intervals of $[-A,A]$ such that $\mathop{\dot{\bigcup}}_{i=1}^N Y_i=[-A,A]$ and suppose that we know the probability $p_i=P(Z \in Y_i)$.

Now if we wish to sample $Z$ we can first sample from a categorical distribution to get in which interval $Y_i$ the sample of $Z$ will lie. From there we have to sample from the distribution of $Z|Z \in Y_i$.

If we know the distribution of $Z|Z \in Y_i$ we can easily sample $Z$ in this indirect manner. Now for my question:

Suppose we do not the distribution of $Z|Z \in Y_i$ and approximate this with a uniform distribution. How good is our approximation? Can we get any convergence results if we let $N \rightarrow \infty$ assuming we still can get the $P(Z \in Y_i)$?

Now based on the comments, I see that this is equivalent to asking if we know the cumulative distribution function $F_Z$ at the values $F_Z(x_i)=p_i$ where the $x_i$ correspond to the edges of the intervals $Y_i$ and we do linear interpolation. Now since the cumulative distribution function is a monotonicaly increasing function I think we should be able to achieve some sort of result on how well the linear interpolation approximates this. I hope this clarifies my question.

Futhermore, would it make a difference if $Z$ is unbounded?

  • 2
    perhaps, it should be $F_{Y_i}(z) \dots$ – pointguard0 Aug 10 at 14:47
  • When you have no information about the $p_i$, it is hard to see how you could proceed. – herb steinberg Aug 10 at 16:22
  • Let see if this match with your situation: There is a set of points $\{z_1, z_2, \ldots, z_n\}$ in which you know the corresponding values $F_Z(z_i)$ and you do not know the other points. To approximate by uniform distribution in between is equivalent to drawing a straight line connecting the neighboring points $(z_i, F_Z(z_i)), (z_{i+1}, F_Z(z_{i+1}))$ when you plot the points (assume in ascending order WLOG) as a CDF graph, and you approximate the original CDF by a trapezoid, like the trapezoidal rule in numerical integration. – BGM Aug 11 at 3:11
  • can the OP clarify what else is needed? IMHO, @BGM comment pretty much answered the question. if the intervals are picked reasonably, e.g. divide $[-A, A]$ into $N$ equal parts, then as $N \rightarrow \infty$ the piecewise linear approximation will tend to the true CDF, i.e. convergence in distribution I am not an expert on the technical details of functional convergence -- is that what the OP requires? Or does the OP want info (e.g. bounds as function of $N$) on some form of ? – antkam Aug 19 at 13:50
  • It looks like you are using a Riemann sum approach to getting $F_z$ as $N \to \infty$. – herb steinberg Aug 21 at 18:36
up vote 2 down vote accepted

Let the real unknown PDF and CDF of $Z$ be $f(z)$ and $F(z)$ respectively. You can make this approximation more precise as $N$ tends to $\infty$ iff $$p_i=\Pr(Z\in Y_i)=\int_{Y_i}f(z)dz=|Y_i|\\\text{and}\\\max_{i}|Y_i|\to 0$$to show the sufficiency of this we try to show that $|\Pr(Z<z)-F(z)|$ can be arbitrarily small by choosing $N$ large enough and $p_i$ being chosen as defined above. For each $N$, let $Y_1,Y_2,\cdots Y_m$ and a fraction of $Y_{m+1}$ are included by region $Z<z$. Therefore$$\Pr(Z<z)=\Pr(Z\in Y_1\cup\cdots \cup Y_m\cup Y'_{m+1})$$since $Y_i$s are disjoint we can write$$\Pr(Z<z){=\sum_{i=1}^{m}\Pr(Z\in Y_i)+\Pr(Z\in Y'_{m+1})\\=\sum_{i=1}^{m}\int_{Y_i}f(z)dz+\int_{Y'_{m+1}}f(z)dz}$$but the term $\int_{Y'_{m+1}}f(z)dz$ can be chosen near enough to zero since $$\int_{Y'_{m+1}}f(z)dz<\int_{Y_{m+1}}f(z)dz=p_{m+1}=|Y_{m+1}|$$the last equality is because we have assumed uniform distribution on each $Y_i$ and all the cardinalities $|Y_i|$ tend to zero hence our primary assumption. This completes our sufficiency proof. For proving necessity, note that $Y_i$s can be interpreted as "clouds". To increase our knowledge about some random variable those clouds need to become smaller and tend to points otherwise there will always remain some ambiguity about the random variable in at least one cloud that doesn't get smaller after a while i.e. the $Y_i$s such that $$|Y_i|>\epsilon\qquad,\qquad\text{for every value of }N$$also since we have assumed uniform distribution on each cloud, the ambiguity will be maximum (you can refer to information theory and entropy function for this). Therefore the statement defined is necessary and sufficient and the proof is complete.

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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