Probability & combination question
petert...@googlemail.com
this question:
(assume any other factors have no bearing on these simple
probabilities)
From the whole population if we found the probability of someone
having blonde hair = 0.2 & P(not blonde) = 0.8
If I pick a random group of 10 people, how to I work out the
probability that exactly 1 or 2... etc. to 10 will have blonde hair.
I think that for all 10 to be blonde the probability is 0.2^10, and
that for only 1 to be blonde it is 0.8^9 (i.e. the probability that 9
of them will not have blonde hair)
I know how to calculate combinations = n!/r!(n-r)!, but I'm having
difficulty visualizing how to apply it in this situation.
Thanks
Peter
Ray Vickson
> I'm having trouble knowing which methods I should be using to solve
> this question:
> (assume any other factors have no bearing on these simple
> probabilities)
>
> From the whole population if we found the probability of someone
> having blonde hair = 0.2 & P(not blonde) = 0.8
>
> If I pick a random group of 10 people, how to I work out the
> probability that exactly 1 or 2... etc. to 10 will have blonde hair.
>
> I think that for all 10 to be blonde the probability is 0.2^10, and
> that for only 1 to be blonde it is 0.8^9 (i.e. the probability that 9
> of them will not have blonde hair)
No. P{10 blonde} = (0.2)^10 is correct, but P{1 blonde} is *not* equal
to (0.8)^9. Look at a group of 10 people, which group happens to have
only 1 blonde. For the order person 1, person 2, ..., person 10 and
using N = not blonde, B = blonde, we could have: BNNNNNNNNN or
NBNNNNNNNN or NNBNNNNNNN or ... or NNNNNNNNNB. Altogether, there are
10 possible "sample points", each having probability (0.2)*(0.8)^9, so
P{1 blonde} = 10*(0.2)*(0.8)^9. What about the case of 2 blondes? We
could have BBNNNNNNNN or BNBNNNNNNN or ... or NNNNNNNNBB, each point
having probability (0.2)^2 * (0.8)^8. How many points are there? Well,
you can enumerate them all and count them, but a neater way is to note
that the number is just 10*9/2, the number of ways of choosing 2
things from 10 things. Why is this true? Think about it this way: we
have 10 empty boxes and want to but "B" into two of them. How many
distinct outcomes will there be? The first 'B' can go into any box, so
there are 10 ways to place the first 'B'. Then the second 'B' can go
into any of the remaining 9 boxes. Altogether, there are 10*9 ways of
placing the two 'B's. However, the arrangements in which B1 goes into
box 3 and B2 into box 7 is the same as that where B2 goes into box 3
and B1 into box 7. In other words, all permutations of B1 and B2 give
the same final outcome, so the number of distinct outcomes is only
10*9 / 2!
In general, P{k blondes} = C(10,k)*(0.2)^k *(0.8)^(10-k), where C(M,j)
= binomial coefficient = number of combinations of j things chosen
from M things = number of subsets of size j = M!/[j! * (M-j)!] = M*
(M-1)* ... *(M-j+1)/j! = number of distinct arrangements of k 'B's in
M boxes.
R.G. Vickson
petertwocakes
Thanks for the clear explanation Ray. I'm going to try and program it
in to a spreadsheet, then I'll know if I come unstuck.
Cheers
Steve
Ray Vickson
wrote:
You are working with the so-called Binomial distribution. If you have
EXCEL (or most other decent spreadsheets) the binomial distribution is
built in. However, if you would like to program it yourself, you
should avoid direct computation of the formula and use instead an
iterative method. In the following, put n = 10 and p = 0.2 to get the
case you are dealing with. The general case of k blondes among n
people with blonde probability = p per person gives P{k blondes} = b
(k) = C(n,k)*p^k* q^(n-k), where q = 1-p and k = 0, 1, 2, ..., n.
Here, b(k) is the so-called binomial probability distribution. We have
b(0) = q^n, and b(k+1) = [(n-k)/(k+1)]*(p/q)*b(k) for k =
0,1,2,...,n-1. Thus, you get b(1)=n*(p/q)*b(0), b(2) = [(n-1)/2]*b(1),
etc.
R.G. Vickson
Ray Vickson
Oops! This last one should be b(2) = [(n-1)/2]*(p/q)*b(1).
RGV
>
> R.G. Vickson
petertwocakes
Nice... it works AND I understand it now. :-) I was going to ask
what happens if we choose from a small population of say, 100, as the
probability would then change each time.(if the first is blonde then
the second would have p = 19/99, I think).
I want to program a general function for this in C, so using the
iterative method you showed me I can just adjust the probability
each time through the loop. I'm not sure what I'm going to do when n!
becomes very large as I guess it will overflow even a 64bit type. Is
this why you said to avoid direct computation?
Thanks
Steve
Ray Vickson
Yes. That is the problem of sampling without replacement. The
distribution of the number of blondes in this case is harder. It is
called the *hypergeometric distribution*. In my version of EXCEL it is
the built-in function HYPGEOMDIST.
Basically, in a population of N things, N1 of type 1 and N2 of type 2
(N = N1 + N2), the hypergeometric distribution with parameters N1, N2
and M describes the probability P(k) of getting k objects of type 1
when a sample of size M is drawn without replacement. In your case,
type 1 = blond, type 2 = other, N1 = 20, N2 = 80 (N = 100), and M =
10. For more details on the hypergeometric distribution, see, eg.,
http://en.wikipedia.org/wiki/Hypergeometric_distribution or
http://stattrek.com/Lesson2/Hypergeometric.aspx . I am not sure how
well it is implemented in EXCEL, since EXCEL is well-known to be
inaccurate and unreliable for statistical computations. See, eg.,
http://www.cs.uiowa.edu/~jcryer/JSMTalk2001.pdf or
http://www.coventry.ac.uk/ec/~nhunt/pottel.pdf or
http://www.burns-stat.com/pages/Tutor/spreadsheet_addiction.html
(especially the links therein).
R.G. Vickson
petertwocakes
> well it is implemented in EXCEL, since EXCEL is well-known to be
> (especially the links therein).
>
> R.G. Vickson
>
> > I want to program a general function for this in C, so using the
> > iterative method you showed me I can just adjust the probability
> > each time through the loop. I'm not sure what I'm going to do when n!
> > becomes very large as I guess it will overflow even a 64bit type. Is
> > this why you said to avoid direct computation?
>
> > Thanks
>
> > Steve
Thanks Ray, I've followed up on what you suggested, but I'm baffled by
when it is necessary to take replacement/no-replacemnet in to account;
intuitively I would have thought that when the population is very
large it wouldn't have made much difference, so to get a feel for this
I concocted some examples: (assuming that all factors are independent)
Population = 400,000
NumBlondes = 150,000
NumPeopleCalledDave = 100
P(blonde) = 150000/400000 = 0.375
Instead of picking a group at random we pick the Daves (100)
From this sample of 100, let k = 38. i.e. what's the probability that
exactly 38 of these 100 Daves will be blonde
= 0.08153
----------
Now flip the problem:
P(Dave) = 100/400000 = 0.00025
Now as our sample group we pick all the blondes.
From this 150,000, let k = 38. i.e. what's the probability that
exactly 38 of these 150,000 Blondes will be called Dave
= 0.06437
A >25% difference. OK, so I would EXPECT a small error in a population
of 400k, but no so big. (I chose k=38 as an estimate of the mean, the
error is worse for extreme values)
The first result is very close to the real result with using the
Hypergeometric distribution, which, as hoped, gives the same answer
for both.
I guess this is because the sample of 100 is a tiny proportion of
400,000.
Given that most problems are with no-replacement, is the Binomial
distribution all that useful if it can produce big errors even with a
population of 400000?
I'm trying to program for a real problem similar to the above that
finds the probability of finding k people that have both attribute A
AND attribute B, so I'll use the hypergeometric. But is there a
different/better way to tackle this altogether?
Thanks
Steve
Ray Vickson
> > well it is implemented in EXCEL, since EXCEL is well-known to be
> > (especially the links therein).
>
> > R.G. Vickson
>
> > > I want to program a general function for this in C, so using the
> > > iterative method you showed me I can just adjust the probability
> > > each time through the loop. I'm not sure what I'm going to do when n!
> > > becomes very large as I guess it will overflow even a 64bit type. Is
> > > this why you said to avoid direct computation?
Yes. However, if the population (sample size M) is very large, even
the recursion needs to be approached carefully, because starting from b
(0) = q^M might fail (inaccuracy, or perhaps even underflow). A better
method would be to start near the mean, say at k = k0 = [p*M] ([ ] =
integer part). Iterate upward using b(k+1) = [(M-k)/(k+1)]*(p/q)*b(k)
for k >= k0 and iterate downward using b(k-1) = c(M,k)*b(k) for k <=
k0; you can easily work out what the coefficient c(M,k) must be.
Regard B = b(k0) as unspecified at the moment. From the iteration, we
get the array of probabilities b(k) as [..., r(k0-2),r(k0-1),1,r
(k0+1),r(k0+2)...]*B, where the r(j) are what you would get if you had
put b(k0) = 1. Now determine B so that the b(j) sum to 1: B = 1/sum(r
(j),j=0..M), and finally re-scale the array to get b(k) = r(k)*B = r
(j)/sum(r). For large M, as you get very far from the center you may
start getting r(j) that are so small as to be negligible, maybe even
close to underflow. In that case, just stop the recursions and just
use sum(r) to be the sum of all the ones computed before stopping.
That method will work even in cases where the direct method fails, and
will in all cases be at least as accurate, if not more accurate, than
the direct method.
>
> > > Thanks
>
> > > Steve
>
> Thanks Ray, I've followed up on what you suggested, but I'm baffled by
> when it is necessary to take replacement/no-replacemnet in to account;
> intuitively I would have thought that when the population is very
> large it wouldn't have made much difference, so to get a feel for this
> I concocted some examples: (assuming that all factors are independent)
>
> Population = 400,000
> NumBlondes = 150,000
> NumPeopleCalledDave = 100
> P(blonde) = 150000/400000 = 0.375
>
> Instead of picking a group at random we pick the Daves (100)
>
> From this sample of 100, let k = 38. i.e. what's the probability that
> exactly 38 of these 100 Daves will be blonde
>
> = 0.08153
> ----------
>
> Now flip the problem:
> P(Dave) = 100/400000 = 0.00025
>
> Now as our sample group we pick all the blondes.
> From this 150,000, let k = 38. i.e. what's the probability that
> exactly 38 of these 150,000 Blondes will be called Dave
>
> = 0.06437
Are you using the binomial distribution in both cases? If so, we can
see what is happening by changing the scenarios' descriptions
somewhat. In the first case we have 150K blondes and 250K others, all
as yet unnamed. Now we randomly throw in the label "Dave" 100 times.
The hypergeometric applies if we don't allow more than one label per
person (so once named, a person is essentially removed), while the
binomial applies if we all the label applications are independent (so
a person could have more than one "Dave" label sticking to him). It is
apparent that since there are so few labels compared to both sub-
populations N1 = 150K and N2 = 250K, the chance that anyone will have
more than one label is small; that is why the binomial gives a good
approximation to the hypergeometric in this case. In the second case
we have N1 = 100 'Daves' and N2 = 399,900 others, all without hair
color at the moment. Now we select 150,000 people at random and dye
them blonde. In this case there is a real difference between the
hypergeometric and the binomial. The hypergeometric case applies if we
don't dye anyone more than once, while the binomial applies if we pick
the 150,000 randomly one-by-one and dye them, irrespective of whether
or not they have been picked and dyed already. Now there is a good
chance that some people (including the "Daves") will have been dyed
more than once, so one would expect a possibly-noticeable difference
between the hypergeometric and binomial answers.
By the way, instead of using the binomial in the second case (which we
should not do, but never mind that for now) we can use the so-called
Poisson approximation. We have a large population N1 = 150K (the
blondes) and a small probability p = 1/4000 per person of being a
'Dave', so the mean number of Daves in the population is m = 150K *
1/4000 = 37.5. This is the case of a "large N, small p with modest
N*p" binomial, so is well-approximated by the much simpler Poisson
distribution P{k} = exp(-m)*m^k/k! for k = 0, 1, 2, ... . In the case
above we have P_binomial{38} = .06436937436, while P_poisson{38} = .
06436127406.
>
> A >25% difference. OK, so I would EXPECT a small error in a population
> of 400k, but no so big.
I have already tried to explain why noticeable differences are not
surprising.
> (I chose k=38 as an estimate of the mean, the
> error is worse for extreme values)
> The first result is very close to the real result with using the
> Hypergeometric distribution, which, as hoped, gives the same answer
> for both.
> I guess this is because the sample of 100 is a tiny proportion of
> 400,000.
> Given that most problems are with no-replacement, is the Binomial
> distribution all that useful if it can produce big errors even with a
> population of 400000?
It is not the 400K alone that is relevant; the two sub-population
sizes should also be "large" compared with the sample size M. In the
first case N1 = 150K and N2 = 250K are both large with respect to M =
100, but in the second case N1 = 100 and N2 = 399,900 are not both
large with respect to M = 150,000.
>
> I'm trying to program for a real problem similar to the above that
> finds the probability of finding k people that have both attribute A
> AND attribute B, so I'll use the hypergeometric. But is there a
> different/better way to tackle this altogether?
Unless you know it is like the first case, you would probably be best
using the hypergeometric directly. By the way, there are better ways
of computing the hypergeometric than straight use of the basic
formula. For example, see http://dissertations.ub.rug.nl/FILES/faculties/eco/2005/e.talens/c4.pdf
.
Section 4.3, starting on page 70, has some recursive formulas. These
are much like the recursive formula b(k+1) = [(n-k)/(k+1)]*(p/q)*b(k)
of the binomial, but are a bit more complicated because the
hypergeometric is itself more complicated.
Well, good luck.
R.G. Vickson
Adjunct Professor, University of Waterloo
>
> Thanks
>
> Steve
petertwocakes
>
> read more »
Thanks
>It is
>apparent that since there are so few labels compared to both sub-
>populations N1 = 150K and N2 = 250K, the chance that anyone will have
>more than one label is small; that is why the binomial gives a good
>approximation to the hypergeometric in this case. In the second case
>we have N1 = 100 'Daves' and N2 = 399,900 others, all without hair
>color at the moment. Now we select 150,000 people at random and dye
>them blonde. In this case there is a real difference between the
>hypergeometric and the binomial.
I can really visualize it now.
I wrote a basic bignum c++ class and I'm finding the iterative method
is working well for the binomial, even with very large N.
(and bailing out when values become negligible as suggested)
From your spreadsheet formula I managed to extract the iterative
method for just calculating C(n,k) also.
Using that I'm calculating the hypergeometric distribution (avoiding
having to calculate factorials).
I'm happy to report I'm getting the same hypergeometric results as the
calculator on the stattrek page you mentioned :-)
(I haven't yet implemented the method from
http://dissertations.ub.rug.nl/FILES/faculties/eco/2005/e.talens/c4.pdf)
Cheers
Steve