2

Suppose we have a random number generator, and we do not know anything about the generator, including the distribution of its outputs. We are allowed to use the generator some number of times to get draws and observe the sample.

Then, from the sample(s), we want to find a number M such that we can say something like

"z% of the (future) draws from this random number generator will be less then M." (future draws meaning not including the draws we used to make sample(s))

How would I go about doing this, and are there any resources to go to?

Thanks!

guest
  • 141
  • 4
  • Is $M$ specified *before* you draw values from the generator or is it somehow computed from the values you have drawn? If it's the former, this is a Binomial sampling problem (and is [extensively discussed on this site](http://stats.stackexchange.com/search?q=binomial+sampling)). If it's the latter, please indicate precisely how $M$ is computed. – whuber Jul 03 '13 at 18:29
  • M will be computed from the values we have drawn. Sorry about being unclear. I will fix that on the post. – guest Jul 03 '13 at 18:31
  • 1
    Given $z$, you are asking for a *non-parametric tolerance limit.* I do not believe this concept has yet been discussed on our site. (+1) Tolerance limits (or, more generally, tolerance intervals) come in several flavors. There is uncertainty associated with $M$: due to the chance nature of the sample it is possible $M$ will be too low or too high. So you can ask for an $M$ that has a small (but prespecified) chance of being too low (or too high). You could also require that the expectation of $M$ be correct. Do you know which flavor you are looking for? – whuber Jul 03 '13 at 18:34
  • Well, the need for this is that I'm working on a multi-armed bandit problem, and all of the multi-armed bandit algorithms require that the support of the reward distribution be in [0,1]. I wanted to try to scale the reward distributions that may not have support in [0,1] so I could apply the algorithms mentioned. A natural way to scale the distribution is to divide the obtained number by the (predicted) maximum. Hence, I would say I am asking for an $M$ that has a small chance of being too high rather then low. – guest Jul 03 '13 at 18:43
  • 1
    I think you're asking the impossible. Without making distributional assumptions, the best you can do (without being arbitrary) is to let $M$ be the largest of the $n$ values you have already drawn. When the underlying distribution is continuous, it is *certain* that $M$ is smaller than the maximum. Sure, you can estimate a high quantile if $n$ is sufficiently large--but won't that just make your algorithm fail on random rare occasions? You would be better served by this site if you were to edit this question to ask what you really want to know about the multi-armed bandit. – whuber Jul 03 '13 at 18:54
  • Yes, I agree. Will post another question on it. Thanks a lot! Do you happen to know anything about this question? (http://stats.stackexchange.com/questions/62872/multi-armed-bandit-for-general-reward-distribution) – guest Jul 03 '13 at 18:59

0 Answers0