March 22, 2012 --- Class 20--- Testing the Hit or Miss Method, Aver,
Testing Trapeziod, Simpson and Romberg Methods (part 1)
Activities:
Testing Hit-or-Miss Method
Program ~sg/src/misc/pi3.c implements the hit-or-miss method using a
feedback shift register random number generator.
You have to tell the program how many "pebbles you want to throw."
This is the first command line argument. You may also have it
repeat the experiment multiple times. This is the optional second
argument.
In the last class we posed these questions:
Do we get the right answer on average?
Can we estimate the error?
How does the error depend on n, the number of trials?
We expect the error to fall like 1/sqrt(n), but can we show that?
In our last class, I asked everyone to explore these questions.
I wrote a shell script ~sg/runpi3.csh and piped the output to a
new program called aver.
[sw246-01:~] sg% runpi3.csh |aver
1.0000000000e+01 3.1434400000e+00 5.1789939986e-03
5.0000000000e+01 3.1441920000e+00 2.3305968939e-03
1.0000000000e+02 3.1425000000e+00 1.6396962708e-03
2.5000000000e+02 3.1395296000e+00 1.0363842538e-03
1.0000000000e+03 3.1416288000e+00 5.1788238172e-04
2.5000000000e+03 3.1415403200e+00 3.2695246022e-04
5.0000000000e+03 3.1413463200e+00 2.2762488525e-04
1.0000000000e+04 3.1415698800e+00 1.6189730323e-04
Aver is a very useful code you may copy from ~sg/src/misc
Aver
For our purposes you only have to know that if you have a file
with x and y on each line, if you type
aver file
then for any lines that have the same x-value aver will average all
the corresponding y-values. It will print x y_average y_error.
This can be very useful when you want averages. It is also why I
arranged the output of pi3 so that the number of pebbles thrown was the
first word of output on each line.
In ~sg/src/pi_test.ax you can find the output of my average value
of pi and the error in the mean of 100 trails. I have also drawn
a horizontal line at pi. For most, but not every point, the line
crosses the error bar.
How Big Should the Errors Be?
We analyze the errors in terms of a random process.
Let p be the probablity of a hit and q = 1-p the probability of a miss.
F_N(p,q) = (p+q)^N
is a polynomial that represents all the possible outcomes of N tosses.
In terms of combinatorial factors
F_N(p,q) = \Sum_{i=0}^N p^i q^{N-i} ( N )
( i )
where (N) = N!/( i! (N-i)! )
(i)
If we want to find the average number of hits = *, we can
apply the operator p X partial derivative w.r.t. p
We can also get ** by applying that operator twice. After applying
the differential operators, we can set p+q = 1
We find ** = N p and ** = N p + N(N-1) p^2 . So the variance
** - **^2 = N p (1-p)
Our pi3 program takes i and multiplies it by 4/N to get a number
that should be Pi. Taking these factors into account, the error
in pi, proportional to the square root of the variance should be
4 \sqrt( p(1-p)/N )
Each student wrote a script to study the error and reproduce
data similar to that in my pi_test.ax file. We then went on to
look at the error and compare it with the theoretical prediction.
Agreement was perfect. The script ~sg/src/run.csh makes 10000
trials for batch sizes from 10 to 5000. The error that comes
out of aver is multiplied by 100 because aver prints the
error in the mean which is proportional to
1/sqrt(number of measurements averaged).
So, we need to multiply by sqrt(10000) to get the variance of a single
measurement.
You can also write an awk script to print the absolute value of the
error for each trial. Here is the awk commaand:
{ err=3.1415926-$2; if(err<0) err= (-err); print $1,err}
Now you many apply this command to your file before sending it to
aver and then plot the error vs size. Use logarithmic scale for
the x and y axes. Can you verify that the error falls like
1/sqrt(size) ?
Testing Trapeziod, Simpson and Romberg Methods
We got a very brief start on testing these methods with the
function cos(x). In our next class, we will go over the
code in some detail.
*