Monte Carlo Algorithms

Benjamin Kusin
benjaminkusin@gmail.com
713 829 7616

This file investigates the behavior of the Monte Carlo technique and shows how it can be used to solve very different kinds of problems. See the write-up for explanations.

Example One

Plot[(0.9^x),{x,0,70}] (*what happens to error rate when multiple trials are done when the error rate at the first trial is 90%*)

f[x_]:=.9^x (*the function in the above graph*)

Plot[f'[x],{x,0,70},PlotRange->Automatic]  (*The derivatve of the above graph. This is the rate of change of the error percentage. The derivative's equation is Ln(.9)(.9)^k)*)

x/.Solve[f'[x]==-0.01,x]

{22.349955711333205`} (*the error percentage improves by less than one per iteration after 23 trials. Need to round up because trials are discrete*)

f'[23] (*check*)

x/.Solve[f[x]==.01,x]

(*the error rate reaches less than one after 44 trials*)

f[44] (*check*)

z[b_,x_]:=b^x

Manipulate[Plot[z[b,x],{x,1,70}],{{b,.1,"Starting Error"},.1,.9}] (* interactive graph of f[x], improvement in error for number of trials between 1 and 70 for various starting errors*)

zP:=Derivative[0,1][z]

Manipulate[Plot[zP[b,x],{x,1,70}],{{b,.1,"Starting Error"},.1,.9}] (*interactive graph of the derivative of f[x], showing the rate of change of the error percentage for different starting error percentages and 70 trials.*)

Manipulate[Plot[{zP[b,x],z[b,x]},{x,1,70}],{{b,.1,"Starting Error"},.1,.9}] (*both the above graphs on one graph*)

Example Two

pie[n_]:=Module[{x,y,ct=0}, (*computes Pi by taking n random points and testing whwther they are within bounds of a circle graph. The graph is a quarter circle so four times the ratio of "in" dots to all dots gives Pi*)
Do[x=Random[];y=Random[];
If[x^2+y^2<1,ct=ct+1],{n}];
N[4 ct/n]]

QuadrantIRandom[n_]:= Module[{x,y,u={}}, (*scatters points throughout the quaadrant*)
Do[x=Random[];y=Random[];
If[x *y<1,u=Append[u, {x,y}]],{n}];u]

ScatterQuad[n_]:=ListPlot[QuadrantIRandom[n]]

CircleLine =ParametricPlot[{Cos[x],Sin[x]},{x,0,Pi}, PlotRange->{0,1}];

Manipulate[Show[CircleLine,ScatterQuad[n]],{{n,1,"Random Points"},1,10000}] (*a demonstration of the random method for finding Pi. 4 times the ratio of "in" dots to "out" dots yields an approximation to Pi that gets better as the number of sample points increases*)

Manipulate[ListPlot[Table[pie[n],{i,100}],PlotRange->{3,3.4}],{{n,1,"Random Points"},1,10000}] (*This plots the pie function 100 times for arbitrary values of n (random points). As the number of sample points increases, the values of the function appreoach Pi*)

Manipulate[Histogram[Table[pie[n],{i,100}]],{{n,100,"Random Points"},100,10000}]
(*A Histogram of the above graph. More random samples yields a greater number of results close to Pi*)

Manipulate[ListPlot[Table[pie[100],{i,n}],PlotRange->{3,3.4}],{{n,100,"Iterations"},100,10000}]  (* This time I took arbitrary repititions of the function for a fixed value of 100 random sample points. This does not appear to improve the approximation to Pi *)

Manipulate[Histogram[Table[pie[1000],{i,n}]],{{n,100,"Iterations"},100,10000}] (*this is the histogram of the above plot. Running it multiple times at the same value, for successively larger values, shows that the distribution of numbers close to Pi does not improve  *)