2
$\begingroup$

I'm interested in finding the minimum and maximum of a particular distribution. However, I don't have a model/function of the distribution, but I can generate at random samples from this distribution.

Here is my issue. I know that my method of generating samples explores the entire space of the distribution. That is to say, given a particular sample in the underlying distribution, my method of sampling may potentially pick it (however, theres technically a zero probability so to speak that I pick any particular sample since my under lying distribution isn't discrete). However, the way I'm drawing samples may not reflect the underlying distribution. For example, imagine a continuous random variable on the interval $[0,1]$. The underlying distribution may be completely skewed to the right (ie towards 1) but it's possible that my sampling method results in a distribution that is skewed completely to the left (ie towards 0). I have no way of determining if they are similar; I only have this method of generating samples which I know come from the same space as the underlying distribution.

Is it possible to construct a meaningful confidence interval in this situation (monte carlo comes to mind but I have little to no experience in this area)?

Edit: Note that I know that the underlying distribution is continuous and bounded on the range $[0,1]$.

$\endgroup$
  • $\begingroup$ From your description, you cannot "generate at random samples from this distribution". If you could, you could just sample many times and approximate the underlying distribution with a histogram. It seems you're just picking randomly from the domain of the distribution, without regard to the distribution itself. That said, if you know the domain of your mystery distribution and the domain of your random sampling method are the same, with enough sampling you should be able to approximate the max/min quite well. $\endgroup$ – Nuclear Wang Aug 1 '18 at 18:13
  • $\begingroup$ Out of interest, if you don't already know the min/max of the support of the distribution of interest, how is it that you know that your sampling distribution has the same support? $\endgroup$ – Ben Jan 7 at 4:13
1
$\begingroup$

I don't think you can do this without making some assumptions about the form of the distribution you're characterising.

Consider two different random variables:

x1 = 0 with probability 1

x2 = 0 with probability (1-d) for some very small d, and 1 otherwise.

If all the data points you sample have outcome 0, does that mean your distribution is x1? Or does it just mean you haven't sampled enough to get a single non-zero point? If you can't tell the difference between these two distributions, obviously you can't accurately estimate the maximum.

As another example, note that a binomial distribution with large n approximates a normal distribution, so as n becomes large it gets harder and harder to distinguish between the two by sampling. But a binomial is always bounded, and a normal distribution is not - it doesn't even have a minimum or maximum.


edit to add: This issue applies even with continuous distributions. For example, let x0 be a random variable uniformly distributed in [0,1] and define random variable x3:

  • if x0 >= d for some small positive d, x3 = x0.
  • if x0 < d, x3 = x0 - k(d-x0)/d for some positive k.

x0 has minimum 0 and maximum 1, obviously. x3 has minimum of -k (when x0 = 0), and maximum 1. Both these distributions are continuous.

For x >= d, the cumulative distributions for these two functions are identical: p(x3 >= x) = p(x0 >= x) = 1-x.

Suppose I give you some extra information: I tell you that your distribution is either x0, or x3 with k=100. Given this additional information, finding the minimum is equivalent to figuring out whether you're sampling from x0 or x3.

Let's make the problem easier again, by saying that you can sample uniformly from the mystery distribution.

Since these two variables have probability (1-d) of giving an identical outcome, it should be clear that you need O(1/d) samples to figure out which one it is. If you observe any negative value, you know you're sampling from x3 and hence minimum = -100; if you run >> 1/d samples without ever getting a negative, you can be pretty sure you're sampling from x0.

But if I don't tell you the value of d, then you can never be certain of the difference between "sampling from x0" and "sampling from x3 but haven't taken enough samples to hit the part of the distribution where they behave differently". In order to decide that you'd taken enough samples, you'd need some sort of prior assumptions about what values of d are plausible.

So if it's not possible to be sure of the minimum even with uniform sampling and that particular restriction on the possible distributions, it certainly isn't possible without uniform sampling or that restriction.

edit #2: x3 isn't bounded between 0 and 1, but it's trivial to construct examples within those bounds that have the same sort of "equal with very high probability" behaviour.

$\endgroup$
  • $\begingroup$ Two comments for your first example. First, is this distribution even possible? Did you mean to say x1 = 0 with probability 1-d and x2=0 for d where d is extremely small? Since this is a discrete distribution sampling will either result in you picking the exact minimum or always picking the max. With a continuous distribution I have the same problem but if I generate enough numbers I'm wondering if I will be able to say the minimum is within a certain range of at least one of my samples. $\endgroup$ – HXSP1947 Mar 21 '17 at 5:41
  • $\begingroup$ Rereading your response, I believe that I wasn't clear enough that I know that my distribution is continuous. I've updated my question so that it is more clear. That said, I should also add that I know that my continuous distribution is bounded between 0 and 1 (and in fact more tightly than this but I don't know exactly how tight). I have added this as well $\endgroup$ – HXSP1947 Mar 21 '17 at 5:44
  • $\begingroup$ Specifying a continuous distribution isn't enough to address this issue. I will update my response to explain why not. $\endgroup$ – Geoffrey Brent Mar 22 '17 at 0:28

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.