Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Edited for the sake of clarity:

If you have a random variable $Q$ distributed uniformly on some interval, say $[a,b]$, what is the function $f$ that describes how many times you have to draw on the distribution to expect to achieve an outcome of at least $c \in [a,b]$?

share|improve this question
    
The probability of achieving a specific outcome $c$ is $0$. Are you sure you don't want to know the probability of achieving an outcome that is $\leq c$? –  Bill Mance Aug 6 '13 at 3:04
    
@BillMance I mean the idea that, if you were to roll the dice a million times you would expect to see some extremes in there –  tacos_tacos_tacos Aug 6 '13 at 3:09
    
So I think your question is a little contradictory then. Do you have a uniform distribution on some set $\{1,2,\cdots,n\}$ or on the interval $[a,b]$? Your analogy of rolling the dice only really makes sense in the former case. –  Bill Mance Aug 6 '13 at 3:11
    
I'm having trouble understanding OP's question, but maybe what he means by "rolling the dice" is a geometric distribution? –  angryavian Aug 6 '13 at 3:13
    
@BillMance ... right, I mean if I have a random number generator that generates numbers in $[a,b]$ I would expect my minimum and maximum results to get closer and closer to the extremes as I ran it more times –  tacos_tacos_tacos Aug 6 '13 at 3:13

2 Answers 2

up vote 2 down vote accepted

"Throw the dice" $n$ times. Let the results be $X_1,X_2,\dots,X_n$. Let $Y=Y_n$ be the minimum. The probability that this is $\gt y$ is the probability that all the $X_i$ are greater than $y$.

Any particular $X_i$ is greater than $y$, where $a\le y\le b$, with probability $\frac{b-y}{b-a}$. So the probability they all are is $\left(\frac{b-y}{b-a}\right)^n$.

It follows that the cumulative distribution function of $Y$ is $$1-\left(\frac{b-y}{b-a}\right)^n.\tag{1}$$ Now you can evaluate any probability you want that concerns the random variable $Y=Y_n$.

The expectation: At an earlier stage of your post, you seemed to be asking for the mean of the minimum. We now proceed to calculate that.

Formula (1) shows that the density function of $Y$ is $n(b-y)^{n-1}(b-a)^{-n}$ on our interval and $0$ elsewhere.

Now we find the expectation of $Y$ in the usual way. So we want to integrate $y$ times the density from $a$ to $b$. Use $y=b-(b-y)$. So we want $$\int_a^b \left(bn(b-y)^{n-1}(b-a)^{-n}-n(b-y)^{n}(b-a)^{-n}\right)\,dy.$$ Both parts of the integral are easy to handle. We get $$b-\frac{n}{n+1}(b-a),$$ which simplifies to $$\frac{n}{n+1}a+\frac{1}{n+1}b.$$ Nice and simple! The mean of the minimum is $\frac{1}{n+1}$ of the way from $a$ to $b$.

The cdf found in Formula (1), and the mean of $Y$, will be I hope enough for you to solve your applied problem. If there are difficulties with that, just ask.

Remark: It is possible that you may need the maximum $Z$ of our $n$ random variables.

This has very nice expectation also. It is $\frac{1}{n+1}a +\frac{n}{n+1}b$.

The distribution of the maximum is marginally nicer than the distribution of the minimum, For the probability that the maximum is $\le z$ is $\left(\frac{z-a}{b-a}\right)^n$.

If you want to find the $n$ for which the expectation of the maximum is greater than $c$, then it is the distribution of the maximum that is relevant. The actual applied problem needs to be described in greater detail before we can see what the appropriate calculations are.

share|improve this answer
    
And from there do you just set $E(Y)=c$ and solve for $n$? –  tacos_tacos_tacos Aug 6 '13 at 3:49
    
If that's what you want to find, sure. The cdf is quite a bit more informative, since it lets you calculate actual probabilities. It happens to have a simple functional form that one can comfortably do algebra on. –  André Nicolas Aug 6 '13 at 3:51
    
So you provided the reasoning for the minimum result of $n$ trials, but since I am asking about finding $n$ to achieve an expected maximum, I should use the CDF corresponding to the event that ALL the trials are less than some value $y$? –  tacos_tacos_tacos Aug 6 '13 at 4:03
    
Yes, if it is the maximum you want the distribution of, I have added a comment about it, The derivation is about the same, as is the calculation of the mean. –  André Nicolas Aug 6 '13 at 4:04
1  
You then want the probability that the maximum is $\ge c$ to be $0.5$, or equivalently the probability that the maximu is $\le c$ to be $0.5$. So (if you look at my cdf for the max, in remark at end) the breakpoint is given by $\left(\frac{c-a}{b-a}\right)^n=0.5$. So solve for $n$, take the log of both sides. Here we are finding the median of the max, not the mean. The mean has a more attractive formula. –  André Nicolas Aug 6 '13 at 4:22

"Having a maximum result in $[c,b]$" is one of those statements where the language clouds the issue a bit. This event is equivalent to having at least one result in $[c,b]$, since you couldn't have a result in $[c,b]$ unless one of them is the maximum.

The complement event is easily examined: on each pull you fall outside the interval with probability $\frac{c-a}{b-a}$, so the chance that all $n$ pulls fall outside the interval is $\left(\frac{c-a}{b-a}\right)^n$.

Therefore, we can create a function $g_c(n)=1-\left(\frac{c-a}{b-a}\right)^n$ that is the probability that you have a maximum in $[c,b]$. Remember that you want to input a $c$ and find an $n$. In order to do this, we have to describe what we mean by "expect", so I'll also allow a parameter $p$ to be the certainty that we want to have that the event has occurred.

The problem has been reduced to this: Given $c$, find $f(c )$, the smallest $n$ such that $g_c(n)\geq p$. Some simple algebra gets $f(c )=\lceil\log_k(1-p)\rceil$ where $k=\frac{c-a}{b-a}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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