Category Archives: Proof

The Buffon’s Needle Problem

Attached is a short write-up on the very interesting geometric probability problem commonly referred to as the Buffon’s Needle problem.  The solution gives a general outline for a Monte Carlo method of approximating pi. neato!Buffons Needle\

An R implementation of the monte carlo simulation is:

#Enter the desired number of trials as n

Buffon_Needle<-function(n){
	L=2;D=L;

	thetas<-c(rep(0,n))
	for(i in 1:n){thetas[i]=runif(1,0,pi/2)}

	X<-c(rep(0,n))
	for(i in 1:n){X[i]=runif(1,0,L/2)	}

	COS<-c(rep(0,n)); COS=cos(thetas)
	Compare<-c(rep(0,n))
	Compare=(X/(2/L))
	Crossover<-c(rep(0,n))
for(i in 1:n){
if(COS[i]>=Compare[i]){Crossover[i]=1}
if(COS[i]<Compare[i]){Crossover[i]=0}
	}
Total=sum(Crossover)
Pi_Est=(2*n)/Total

cat("For ",n," trials the estimate of pi is: ",Pi_Est)
}
########################################

Buffon_Needle(100)

A SAS implementation of the monte carlo simulation is:

%macro Buffon_Needle(n=);
%let D=2; %let L=2;
 
data BN;
do i=1 to &n;
     angle=rand("Uniform",0,3.14159/2);
     X=rand("Uniform",0,&D/2);
     COS=cos(angle);
     L=&L;
output;
end;
 
data BN; set BN;
if(COS >=(X/(2/L))) then Cross = 1;
else Cross = 0;
 
proc sql;
create table Results as
select (sum(t1.Cross)) as Total_Crosses
from work.BN t1;
quit;
 
data Results; set Results;
n=&n;
pi_est = (2*&n)/Total_Crosses;
 
run;
 
%mend;
 
%Buffon_Needle(n=1000000);
Advertisement

Recurrence Of Simple Symmetric Random Walks

Description of the simple symmetric random walk on Z often utilizes the imagery of a drunken man attempting to walk home. The idea is that the man starts at some initial location, call it 0, and then randomly moves forward or backwards; moving one step in either direction per time period.  So the man starts at location 0 and moves either to −1 or 1 in the first time period with equal probability of 1/2 (this equal probability of moving forward or backwards is what is meant by ”symmetric”).  Then, from this new location (for descriptions sake, say he moved to position 1 during the first time period) he moves to either 0 or 2, again with equal probability. Likewise from this new position (for descriptions sake, say he moved to position 2 during the second time period) he then moves to position 1 or 3 with equal probability in the third time period, and so on… The descriptive ’simple’ is meant to indicate that from any point in Z, the probability of moving forward and backwards is exactly the same as at any other point in Z.

Linked,  I show that given an infinite amount of time, the drunken man will not essentially go anywhere. That is, he will cross the origin, 0, an infinite number of times. It turns out that this is also the case in Z2, where the simple forward and backward motion of the Z case is augmented to the 2-dimensional situation of being able to move in 4 directions from any point each with equal probability of 1/4. However, interestingly the scenario in 3-dimensions (Z3) is different. In three dimensions, our drunken man may move any of 6 directions from any point (up, down, left, right, forward, backwards), each with equal probability of 1/6. Here, what we’ll show is that the man does indeed ’get somewhere’. That is, given an infinite amount of time, the man will cross the origin point only a finite number of times, which is to say that he’ll eventually wander off in a direction and never again return to his starting position.

Recurrence Of Simple Symmetric Random Walk

The Optional Stopping/Sampling Theorem

The OST says that given a finite amount of money and a finite time horizon, any betting sequence/strategy cannot improve the expected earnings from a sequence of fair gambles.  More to the point, the theorem is proof that you can’t expect to make money playing a fair game (a martingale) and you can’t bet in such a way that you can expect to beat an unfair game (a supermartingale).  Attached, I’ve written a rundown of the result along with a nice short proof.

The Optional Stopping/Sampling Theorem

Stochastic Process, Optional Stopping Theorem, Expected Value, Conditional Expectation, Martingale

Riemann Zeta (2)

Linked is a proof written on the value of the Riemann Zeta function at 2 (aka the Basel Problem). My solution utilizes the Fourier transform and the strong form of L’Hopital’s rule, as well as hyperbolic trig identities, etc… While it is indeed a correct derivation, there are simpler solutions to the problem. This solution is interesting though. …i think.

Riemann Zeta (2)

Basel Problem, Poisson Summation Formula, Fourier Transform, L’Hopital’s rule, Taylor Series