Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

I'm more of a programmer than a statistician, so I hope this question isn't too naive.

It happens in sampling program executions at random times. If I take N=10 random-time samples of the program's state, I could see function Foo being executed on, for example, I=3 of those samples. I'm interested in what that tells me about the actual fraction of time F that Foo is in execution.

I understand that I is binomially distributed with mean F*N. I also know that, given I and N, F follows a beta distribution. In fact I've verified by program the relationship between those two distributions, which is

cdfBeta(I, N-I+1, F) + cdfBinomial(N, F, I-1) = 1

The problem is I don't have an intuitive feel for the relationship. I can't "picture" why it works.

EDIT: All the answers were challenging, especially @whuber's, which I still need to grok, but bringing in order statistics was very helpful. Nevertheless I've realized I should have asked a more basic question: Given I and N, what is the distribution for F? Everyone has pointed out that it's Beta, which I knew. I finally figured out from Wikipedia (Conjugate prior) that it appears to be Beta(I+1, N-I+1). After exploring it with a program, it appears to be the right answer. So, I would like to know if I'm wrong. And, I'm still confused about the relationship between the two cdfs shown above, why they sum to 1, and if they even have anything to do with what I really wanted to know.

share|improve this question
    
If "what you actually wanted to know" is "the actual fraction of time that Foo is in execution," then you are asking about a Binomial confidence interval or a (Bayesian) Binomial credible interval. –  whuber Nov 21 '10 at 21:12
    
@whuber: Well I've used the random-pause method of performance tuning for over 3 decades, and some other people have discovered it too. I've told people that if some condition is true on 2 or more random-time samples, then removing it would save a good fraction of time. HOW good a fraction is what I've tried to be explicit about, assuming we don't know a Bayesian prior. Here's the general flame: stackoverflow.com/questions/375913/… and stackoverflow.com/questions/1777556/alternatives-to-gprof/… –  Mike Dunlavey Nov 21 '10 at 21:54
1  
Nice idea. The statistical assumption is that the interruption is independent of the execution state, which is a reasonable hypothesis. A binomial confidence interval is a good tool to use to represent the uncertainty. (It can be an eye-opener, too: in your 3/10 situation, a symmetric two-sided 95% CI for the true probability is [6.7%, 65.2%]. In a 2/10 situation the interval is [2.5%, 55.6%]. These are wide ranges! Even with 2/3, the lower limit is still less than 10%. The lesson here is that something fairly rare can happen twice.) –  whuber Nov 21 '10 at 22:16
    
@whuber: Thanks. You're right. Something more useful is the expected value. As far as priors go, I point out that if you only see something once, it doesn't tell you much unless you happen to know the program is in an infinite (or exceedingly long) loop. –  Mike Dunlavey Nov 21 '10 at 22:44

4 Answers 4

up vote 7 down vote accepted

Consider the order statistics $x_{[0]} \le x_{[1]} \le \cdots \le x_{[n]}$ of $n+1$ independent draws from a uniform distribution. Because order statistics have Beta distributions, the chance that $x_{[k]}$ does not exceed $p$ is given by the Beta integral

$$\Pr[x_{[k]} \le p] = \frac{1}{B(k+1, n-k+1)} \int_0^p{x^k(1-x)^{n-k}dx}.$$

(Why is this? Here is a non-rigorous but memorable demonstration. The chance that $x_{[k]}$ lies between $p$ and $p + dp$ is the chance that out of $n+1$ uniform values, $k$ of them lie between $0$ and $p$, at least one of them lies between $p$ and $p + dp$, and the remainder lie between $p + dp$ and $1$. To first order in the infinitesimal $dp$ we only need to consider the case where exactly one value (namely, $x_{[k]}$ itself) lies between $p$ and $p + dp$ and therefore $n - k$ values exceed $p + dp$. Because all values are independent and uniform, this probability is proportional to $p^k (dp) (1 - p - dp)^{n-k}$. To first order in $dp$ this equals $p^k(1-p)^{n-k}dp$, precisely the integrand of the Beta distribution. The term $\frac{1}{B(k+1, n-k+1)}$ can be computed directly from this argument as the multinomial coefficient ${n+1}\choose{k,1, n-k}$ or derived indirectly as the normalizing constant of the integral.)

By definition, the event $x_{[k]} \le p$ is that the $k+1^\text{st}$ value does not exceed $p$. Equivalently, at least $k+1$ of the values do not exceed $p$: this simple (and I hope obvious) assertion provides the intuition you seek. The probability of the equivalent statement is given by the Binomial distribution,

$$\Pr[\text{at least }k+1\text{ of the }x_i \le p] = \sum_{j=k+1}^{n+1}{{n+1}\choose{j}} p^j (1-p)^{n+1-j}.$$

In summary, the Beta integral breaks the calculation of an event into a series of calculations: finding at least $k+1$ values in the range $[0, p]$, whose probability we normally would compute with a Binomial cdf, is broken down into mutually exclusive cases where exactly $k$ values are in the range $[0, x]$ and 1 value is in the range $[x, x+dx]$ for all possible $x$, $0 \le x \lt p$, and $dx$ is an infinitesimal length. Summing over all such "windows" $[x, x+dx]$--that is, integrating--must give the same probability as the Binomial cdf.

alt text

share|improve this answer
    
(+1) very nice! –  G. Jay Kerns Nov 18 '10 at 16:51
    
I appreciate the effort. I'm going to have to really study this because it's not my "native tongue". Also, I'm seeing a lot of dollar signs and formatting stuff. Is there something I don't know about that makes it look like real math? –  Mike Dunlavey Nov 18 '10 at 17:17
    
What happened? All of a sudden the math showed up, and typing in here got real slow. –  Mike Dunlavey Nov 18 '10 at 17:25
    
@Mike See meta.stats.stackexchange.com/q/218/919 . –  whuber Nov 18 '10 at 18:12
1  
It's a little late, but I finally got time to sit down and re-create your argument. The key was "multinomial coefficient". I had tried figuring it out using plain old binomial coefficients and I was getting all balled up. Thanks again for a nice answer. –  Mike Dunlavey Jan 25 '11 at 17:29

Look at the pdf of Binomial as a function of $x$: $$f(x) = {n\choose{x}}p^{x}(1-p)^{n-x}$$ and the pdf of Beta as a function of $p$: $$g(p)=\frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}p^{a-1}(1-p)^{b-1}$$ You probably can see that with an appropriate (integer) choice for $a$ and $b$ these are the same. As far as I can tell, that's all there is to this relationship: the way $p$ enters into the binomial pdf just happens to be called a Beta distribution.

share|improve this answer
    
I know those look almost the same, but if I substitute y for n-x, and if I take the Beta pdf and substitute x for a-1 and y for b-1 I get an extra factor of (x+y+1), or n+1. i.e. (x+y+1)!/x!/y!*p^x*q^y. That seems to be enough to throw me off. –  Mike Dunlavey Nov 18 '10 at 21:10
1  
Maybe somebody will chime in with a full response, but in an "intuitive" explanation we can always hand-wave away constants (like $n+1$) that do not depend on the variables of interest ($x$ and $p$), but are required to make the pdf add/integrate to 1. Feel free to replace the "equality" signs with "proportional to" signs. –  Aniko Nov 18 '10 at 21:37
    
Good point. I think I'm getting closer to an understanding. I'm still trying to be able to say what x tells you about the p distribution, and why those two cdfs sum to 1. –  Mike Dunlavey Nov 18 '10 at 21:43
    
I take a different view of "intuitive" explanations. In some cases we don't care too much about constants, but in this case the crux of the matter is to see why an n+1 appears and not an n. If you don't understand that then your "intuition" is incorrect. –  whuber Nov 18 '10 at 22:49
    
I revised the question, if you care to take a look. Thanks. –  Mike Dunlavey Nov 20 '10 at 15:03

As you noted, the Beta distribution describes the distribution of the trial probability parameter $F$, while the binomial distribution describes the distribution of the outcome parameter $I$. Rewriting your question, what you asked about was why $$P(F \le \frac {i+1} n)+P(I \le fn-1)=1$$ $$P(Fn \le i+1)+P(I+1 \le fn)=1$$ $$P(Fn \le i+1)=P(fn<I+1)$$ That is, the likelihood that the observation plus one is greater than the expectation of the observation is the same as the likelihood that the observation plus one is greater than the expectation of the observation.

I admit that this may not help intuit the original formulation of the problem, but maybe it helps to at least see how the two distributions use the same underlying model of repeated Bernoulli trials to describe the behavior of different parameters.

share|improve this answer
    
I appreciate your take on it. All the answers are helping me to think about the question and possibly understand better what I'm asking. –  Mike Dunlavey Nov 19 '10 at 14:56
    
I revised the question, if you care to take a look. Thanks. –  Mike Dunlavey Nov 20 '10 at 15:05
    
Regarding your revision: Yes, $F\sim Beta(I+1,N-I+1)$, as long as your sampling intervals are long enough that each observation is independent and identically distributed. Note that if you want to be Bayesian about it and specify a nonuniform prior distribution for what you expect the actual proportion to be, you can add something else to both parameters. –  sesqu Nov 21 '10 at 11:51

In Bayesian land, the Beta distribution is the conjugate prior for the p parameter of the Binomial distribution.

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.