November 13, 2007 --- Class 22--- Testing the Hit or Miss Method, Aver

Activities:

	Testing Hit-or-Miss Method

	Program ~sg/src/pi3.c implements the hit-or-miss method using a
	feedback shift register random number generator.
	You have to tell the program how many "darts 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 create datafiles 
	with 100 batches of various trial sizes: 10 20 40 80 160.  
	I did not use a shell script, and used
	a interactive foreach command instead.  I then used another foreach
	loop to make histograms from each datafile.  We need to find the
	average of the values in the data files.  Aver is a very useful
	code you may copy from ~sg/src/misc for this purpose.

	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 darts 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 followed up on the suggestion by Jason that 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 = <i>, we can
	apply the operator p X partial derivative w.r.t. p
	We can also get <i^2> by applying that operator twice.  After applying
	the differential operators, we can set p+q = 1

	We find <i> = N p and <i^2> = N p + N(N-1) p^2 . So the variance
	<i^2> - <i>^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(N p (1-p) )

	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) ?