Hello again, gooseman!
Let's address your questions one by one. It's going to be a bit
difficult to write mathematical
symbols in this format, but I'll do muy best.
If you want to estimate the population mean using the sample mean, you
will need a large number
of simulations. The sample size (that is, the number of simulations
you'll have to run) depend on
the the accuracy (error margin) you want to achieve. To understand how
the sample size depends on
the error margin you set, you must first understand what the Central
Limit Theorem is.
There are various versions of the Central Limit Theorem. I'll state
the one that is most used and
applies to your case:
Central Limit Theorem (adapted from "Statistical Inference", by
Casella and Berger, 1990):
(1) Let X1, X2,...Xn be a sequence of n random iid (independent and
identically distributed)
variables.
(2) Let E(Xi)=u and Var(Xi)=s^2 for i=1,2,...
Define "An" be the sample mean of X1, X2,...Xn. Then
[sqrt(n)*(An-u)]/s converges to a standard normal distribution
(that is, when n is large,
it follows a normal distribution with mean 0 and variance 1).
sqrt(n) is the sqare root of n. If you don't see how this applies to
your case, think that if you
take n samples WITHOUT changing the parameters, it seems right to say
that each observation is a
random variable, and that they all have the same distribution. This is
because if you don't
change any parameters and just run your simulation over and over, then
the outcomes of each
simulation should follow the same -unknown- distribution (so the mean
and variance of each
outcome are the same, and assumption (2) is true).
What the central limit theorem implies is that the *sample mean* (I
called it An, a sample mean
of 'n' observations) minus the *population* mean and then divided by
(s/sqrt(n)) where s is the
*population* variance follows a standard normal distribution.
This is a very powerful theorem. It says that no matter what's the
distribution from which the
sample comes; anyway, if the sample size is large, the sample mean
(with some transformations)
will have a standard normal distribution.
You can see this theorem in 'action' at
The Central Limit Theorem
http://www.math.csusb.edu/faculty/stanton/m262/central_limit_theorem/clt.html
It's stated a bit different than I wrote above. If you divide the
numerator and the denominator
by n, you'll get the equation I stated.
Now, we have two problems here. First: we don't know the population
mean 'u' (recall from above
that you have to substract it from the sample mean to form the random
variable that converges to
standard normal). Second: we don't know the population variance.
I'll first address the second problem. We don't know the population
variance, but then, you can
calculate the sample variance. You can find the formula at:
Sample variance
http://mathworld.wolfram.com/SampleVariance.html
(see item (3) )
By the Law of Large Numbers, you know that the sample variance
converges to the population
variance. So, applying Slutzky's Theorem, you can directly use the
sample variance instead of the
population variance, and the results will be the same for a large 'n'.
That solves the second problem. Now you're ready to find out which is
the minimum 'n' to achieve
a certain error margin.
Say you want to choose a sample size (n) so that:
Probability of "the difference between the sample mean and the actual
mean is no bigger than 2"
is 95%. That is, the sample mean you estimated is in the interval
[u-2,u+2] with a 95%
confidence.
You would write this event like this:
Prob (|An-u|<2) = 0.95
Where | | is modulus
This is the same to say that
Prob (|An-u|>2) = .05
But you also know by the Central Limit Theorem that sqrt(n)*(An-u)/s
has a standard normal
distribution (for large n). Thus,
Prob (|An-u| > 2) =
Prob (sqrt(n)*|An-u| > sqrt(n)*2) =
Prob (sqrt(n)*|An-u|/s > sqrt(n)*2/s) = 0.05
Now, what follows is easy. You know that the lefthand side of the
inequality has a standard
normal distribution. Let's call the lefthand side as 'z'. You have
Prob (|z| > sqrt(n)*2/s) = 0.05
So you check a standard normal distribution table (you can find these
in mostly any Statistics
book, or at the link I provide below), and find which value leaves
0.025 (0.05/2) of the possible
values in the right tail.
Standard normal distribution table
http://www.math2.org/math/stat/distributions/z-dist.htm
In the example I'm giving you (that is, with 95% confidence), this
value is 1.96
Finally, you're all set! You just have to solve (in my example)
sqrt(n)*2/s = 1.96
Now you run into another problem (that's Statistics :-) ). You don't
have a sample variance until
you actually have run some simulations. The good news is that this
sample variance needn't be
very precise; some authors suggest using a sample size of a "few
hundred", I've found 150 has
worked well for me in most researches I've done. So once you have the
sample variance, you take
square root of it to get the standard deviation; and that's your 's'.
Now you have one equation
with one unknown. So, in general, with a confidence level of 95%, the
minimum sample size (n) you
need to be within a given error margin (ER) is:
*** n = [(1.96*s)/ER]^2 ***
That's all. I've explained everything step by step. BUT if you're
solely interested in the number
of the sample size, you can check the following site, where you enter
the error margin and the
sample standard deviation, and it automatically calculates the needed
sample size.
http://department.obg.cuhk.edu.hk/ResearchSupport/Sample_size_EstMean.asp
If the 'n' you find here is smaller than the 'n' you used to estimate
the sample variance (say,
150), obviously you don't need to run simulations again: just use the
mean of the same sample you
used for the variance.
Now, onto your second question. You want compare the means of
different processes, and see if
they are or not statistically different. This is somewhat more
complicated to explain step by
step, especially using text to write mathematical symbols. So I'll
just tell you what method to
use and then mention some books you can check to find out why it
works.
What you need to use for this kind of comparison is an ANOVA analysis.
It's not true that this
analysis can only be done for 2 populations, you can use it for as
many populations as you want.
Here, you are testing the null hypothesis "the means of all groups are
equal" versus "the means
of at least two groups are different", where, in your case, each
"group" would be the program run
with different parameters (different grid size, etc.). In order to
make this test, you have to
build an F-statistic in the following way (taken from EViews 3.1 help
file):
Denote the i-th observation in group g as Xgi, where i=1,2,...,Ng for
groups g=1,2,...,G. The
between and within sums of squares are defined as
SSbetween= G
---
\ Ng*(Yg-Y)^2
/
---
g=1
SSwithin= G Ng
--- ---
\ \ (Xgi-Yg)^2
/ /
--- ---
g=1 i=1
Where Yg is the sample mean of group g, Y is the overall sample mean
(that is, using all
observations from all groups), G is the number of groups, and Ng is
the sample size of group g.
The F-statistic is as follows
F= SSb/(G-1)
---------
SSw/(N-G)
where N is the total number of observations. This statistic is
distributed as an F with G-1
numerator degrees of freedom and N-G denominator degrees of freedom.
And now you're all set. Just
look up the area to the right of F in a table; or, if you don't have a
book, just plug the
degrees of freedom and F in the following page
F-table
http://davidmlane.com/hyperstat/F_table.html
click on Compute and you'll see the p-value for the test. So, a
p-value of .05 or lower means you
can be 95% confident that the null hyupothesis can be REJECTED. A
higher p-value means you cannot
reject the null hypothesis that the means across different groups are
equal.
Needless to say, you don't need to run the simulations again in order
to perform the ANOVA
analysis. Using the method I described above, by now you should have
calculated the minimum
sample size for each group, and you should have run that many
simulations; so by now you should
have a large (and efficient) number of observations.
I also found two web pages that can calculate the F-statistic for you:
Lieberman Research Worldwide
http://www.lrwonline.com/stattest/means.asp
Although using this will be simpler in that they only ask you for the
mean and variance of the
groups (you don't have to enter all the data), they only let you
compare two groups.
The following site is great: it's a statistics java applet. You can
enter data and it will
calculate descriptive statistics (mean, variance, etc.), graph the
data, and calculate many
Statistical Inference functions, including the ANOVA analysis.
WebStat
http://www.stat.sc.edu/webstat/
To learn more about ANOVA analysis check the following site:
http://www.cityu.edu.hk/ma/staff/ychon/3518/wk9-ANOVA.pdf
Finally, as I don't know java programming, I can't help you to
automate the calculation of this
statistics. However, I was able to locate some pages that provide java
source codes for
statistics applications; I'm sure you can adapt them to your needs.
The first site generates
random numbers from a distribution, and then, among other things, it
calculates their mean and
variance. I think this may apply to your case, in that the random
numbers for this applet would
be equivalent to the "number of iterations taken" variable of your
process.
http://www.math.uah.edu/psol/objects/experiments/SampleMeanExperiment.html
http://nimitz.mcs.kent.edu/~blewis/stat/anova.html
Well, I hope this explanation has proved useful to you. I know this is
a difficult subject, even
more difficult when you have to use mathematical symbols in an text
editor... I hope I've been
clear enough for you. In any case, for an in-depth explanation of
statistics methods, I suggest
you check the book I quoted above, "Statistical Inference". It's
available at Amazon.com.
Good luck with your project!
elmarto-ga |
Clarification of Answer by
elmarto-ga
on
22 Jun 2002 18:47 PDT
I'm sorry, something went wrong when pasting the text from my Notepad,
and there are line breaks where there shouldn't be. I'll paste it
again hoping this time works.
--BTW, the Google search terms I used were
"sample size" population mean
compare two means
"ANOVA analysis"
---------------------------------------------
ANSWER REPOSTING
Hello again, gooseman!
Let's address your questions one by one. It's going to be a bit
difficult to write mathematical symbols in this format, but I'll do
muy best.
If you want to estimate the population mean using the sample mean, you
will need a large number of simulations. The sample size (that is, the
number of simulations you'll have to run) depend on the the accuracy
(error margin) you want to achieve. To understand how the sample size
depends on the error margin you set, you must first understand what
the Central Limit Theorem is.
There are various versions of the Central Limit Theorem. I'll state
the one that is most used and applies to your case:
Central Limit Theorem (adapted from "Statistical Inference", by
Casella and Berger, 1990):
(1) Let X1, X2,...Xn be a sequence of n random iid (independent and
identically distributed) variables.
(2) Let E(Xi)=u and Var(Xi)=s^2 for i=1,2,...
Define "An" be the sample mean of X1, X2,...Xn. Then
[sqrt(n)*(An-u)]/s converges to a standard normal distribution
(that is, when n is large, it follows a normal distribution with mean
0 and variance 1).
sqrt(n) is the sqare root of n. If you don't see how this applies to
your case, think that if you take n samples WITHOUT changing the
parameters, it seems right to say that each observation is a random
variable, and that they all have the same distribution. This is
because if you don't change any parameters and just run your
simulation over and over, then the outcomes of each simulation should
follow the same -unknown- distribution (so the mean and variance of
each outcome are the same, and assumption (2) is true).
What the central limit theorem implies is that the *sample mean* (I
called it An, a sample mean of 'n' observations) minus the
*population* mean and then divided by (s/sqrt(n)) where s is the
*population* variance follows a standard normal distribution.
This is a very powerful theorem. It says that no matter what's the
distribution from which the sample comes; anyway, if the sample size
is large, the sample mean (with some transformations) will have a
standard normal distribution.
You can see this theorem in 'action' at
The Central Limit Theorem
http://www.math.csusb.edu/faculty/stanton/m262/central_limit_theorem/clt.html
It's stated a bit different than I wrote above. If you divide the
numerator and the denominator by n, you'll get the equation I stated.
Now, we have two problems here. First: we don't know the population
mean 'u' (recall from above that you have to substract it from the
sample mean to form the random variable that converges to standard
normal). Second: we don't know the population variance.
I'll first address the second problem. We don't know the population
variance, but then, you can calculate the sample variance. You can
find the formula at:
Sample variance
http://mathworld.wolfram.com/SampleVariance.html
(see item (3) )
By the Law of Large Numbers, you know that the sample variance
converges to the population variance. So, applying Slutzky's Theorem,
you can directly use the sample variance instead of the population
variance, and the results will be the same for a large 'n'.
That solves the second problem. Now you're ready to find out which is
the minimum 'n' to achieve a certain error margin.
Say you want to choose a sample size (n) so that:
Probability of "the difference between the sample mean and the actual
mean is no bigger than 2" is 95%. That is, the sample mean you
estimated is in the interval [u-2,u+2] with a 95% confidence.
You would write this event like this:
Prob (|An-u|<2) = 0.95
Where | | is modulus
This is the same to say that
Prob (|An-u|>2) = .05
But you also know by the Central Limit Theorem that sqrt(n)*(An-u)/s
has a standard normal distribution (for large n). Thus,
Prob (|An-u| > 2) =
Prob (sqrt(n)*|An-u| > sqrt(n)*2) =
Prob (sqrt(n)*|An-u|/s > sqrt(n)*2/s) = 0.05
Now, what follows is easy. You know that the lefthand side of the
inequality has a standard normal distribution. Let's call the lefthand
side as 'z'. You have
Prob (|z| > sqrt(n)*2/s) = 0.05
So you check a standard normal distribution table (you can find these
in mostly any Statistics book, or at the link I provide below), and
find which value leaves 0.025 (0.05/2) of the possible values in the
right tail.
Standard normal distribution table
http://www.math2.org/math/stat/distributions/z-dist.htm
In the example I'm giving you (that is, with 95% confidence), this
value is 1.96
Finally, you're all set! You just have to solve (in my example)
sqrt(n)*2/s = 1.96
Now you run into another problem (that's Statistics :-) ). You don't
have a sample variance until you actually have run some simulations.
The good news is that this sample variance needn't be very precise;
some authors suggest using a sample size of a "few hundred", I've
found 150 has worked well for me in most researches I've done. So once
you have the sample variance, you take square root of it to get the
standard deviation; and that's your 's'. Now you have one equation
with one unknown. So, in general, with a confidence level of 95%, the
minimum sample size (n) you need to be within a given error margin
(ER) is:
*** n = [(1.96*s)/ER]^2 ***
That's all. I've explained everything step by step. BUT if you're
solely interested in the number of the sample size, you can check the
following site, where you enter the error margin and the sample
standard deviation, and it automatically calculates the needed sample
size.
http://department.obg.cuhk.edu.hk/ResearchSupport/Sample_size_EstMean.asp
If the 'n' you find here is smaller than the 'n' you used to estimate
the sample variance (say, 150), obviously you don't need to run
simulations again: just use the mean of the same sample you used for
the variance.
Now, onto your second question. You want compare the means of
different processes, and see if they are or not statistically
different. This is somewhat more complicated to explain step by step,
especially using text to write mathematical symbols. So I'll just tell
you what method to use and then mention some books you can check to
find out why it works.
What you need to use for this kind of comparison is an ANOVA analysis.
It's not true that this analysis can only be done for 2 populations,
you can use it for as many populations as you want. Here, you are
testing the null hypothesis "the means of all groups are equal" versus
"the means of at least two groups are different", where, in your case,
each "group" would be the program run with different parameters
(different grid size, etc.). In order to make this test, you have to
build an F-statistic in the following way (taken from EViews 3.1 help
file):
Denote the i-th observation in group g as Xgi, where i=1,2,...,Ng for
groups g=1,2,...,G. The between and within sums of squares are defined
as
SSbetween= G
---
\ Ng*(Yg-Y)^2
/
---
g=1
SSwithin= G Ng
--- ---
\ \ (Xgi-Yg)^2
/ /
--- ---
g=1 i=1
Where Yg is the sample mean of group g, Y is the overall sample mean
(that is, using all observations from all groups), G is the number of
groups, and Ng is the sample size of group g.
The F-statistic is as follows
F= SSb/(G-1)
---------
SSw/(N-G)
where N is the total number of observations. This statistic is
distributed as an F with G-1 numerator degrees of freedom and N-G
denominator degrees of freedom. And now you're all set. Just look up
the area to the right of F in a table; or, if you don't have a book,
just plug the degrees of freedom and F in the following page
F-table
http://davidmlane.com/hyperstat/F_table.html
click on Compute and you'll see the p-value for the test. So, a
p-value of .05 or lower means you can be 95% confident that the null
hyupothesis can be REJECTED. A higher p-value means you cannot reject
the null hypothesis that the means across different groups are equal.
Needless to say, you don't need to run the simulations again in order
to perform the ANOVA analysis. Using the method I described above, by
now you should have calculated the minimum sample size for each group,
and you should have run that many simulations; so by now you should
have a large (and efficient) number of observations.
I also found two web pages that can calculate the F-statistic for you:
Lieberman Research Worldwide
http://www.lrwonline.com/stattest/means.asp
Although using this will be simpler in that they only ask you for the
mean and variance of the groups (you don't have to enter all the
data), they only let you compare two groups.
The following site is great: it's a statistics java applet. You can
enter data and it will calculate descriptive statistics (mean,
variance, etc.), graph the data, and calculate many Statistical
Inference functions, including the ANOVA analysis.
WebStat
http://www.stat.sc.edu/webstat/
To learn more about ANOVA analysis check the following site:
http://www.cityu.edu.hk/ma/staff/ychon/3518/wk9-ANOVA.pdf
Finally, as I don't know java programming, I can't help you to
automate the calculation of this statistics. However, I was able to
locate some pages that provide java source codes for statistics
applications; I'm sure you can adapt them to your needs. The first
site generates random numbers from a distribution, and then, among
other things, it calculates their mean and variance. I think this may
apply to your case, in that the random numbers for this applet would
be equivalent to the "number of iterations taken" variable of your
process.
http://www.math.uah.edu/psol/objects/experiments/SampleMeanExperiment.html
http://nimitz.mcs.kent.edu/~blewis/stat/anova.html
Well, I hope this explanation has proved useful to you. I know this is
a difficult subject, even more difficult when you have to use
mathematical symbols in an text editor... I hope I've been clear
enough for you. In any case, for an in-depth explanation of statistics
methods, I suggest you check the book I quoted above, "Statistical
Inference". It's available at Amazon.com.
Good luck with your project!
elmarto-ga
|
