Monte Carlo Verfahren – Buffon’s needle

Dies ist das klassische Buffon’s needle Problem http://en.wikipedia.org/wiki/Buffon%27s_needle.

Es fällt in die Kategorie der Monte Carlo Verfahren zur Approximation von $latex \pi$.

Auf eine Plane mit äquidistanten (Abstand t), vertikalen Linien lässt man nacheinander Nadeln der Länge $latex l$ fallen.

Offensichtlich können wir 2 Zufallskomponenten rausfiltern.

  1. Der Winkel $latex \theta$ auf dem die Nadel, relativ zu den vertikalen Linien, liegenbleibt.
  2. Die Position $latex x$ zwischen 2 Linien, auf der die Nadelmitte auftrifft.

Wir haben also 2 Zufallsvariablen $latex X$, und $latex \Theta$. Wir gehen davon aus, dass die ZV gleichverteilt sind.

die jeweiligen Dichtefunktionen betragen somit:

$latex f_{X}(x)=\frac{1}{0-\frac{t}{2}}=\frac{2}{t} \quad , t \neq 0$

$latex f_{\Theta}(\theta)=\frac{1}{0-\frac{\pi}{2}}=\frac{2}{\pi}$

Wir betrachten hier nur die Fälle $latex  0 \leq x \leq \frac{t}{2}$ und $latex 0 \leq \theta \leq \frac{\pi}{2}$, da sich die anderen Fälle symmetrisch daraus ableiten lassen.

Als nächstes berechnen wir die bivariate Dichtefunktion $latex f_{X,\Theta}(x,\theta)$. Diese können wir in diesem Fall leicht berechnen,

da beide ZV hier unabhängig sind und sich somit

$latex f_{X , \Theta}(x , \theta) = f_{X}(x)*f_{\Theta}(\theta) = \frac{4}{t \pi}$

ergibt. Die Nadel kreuzt eine Linie, wenn: $latex x \leq \frac{l}{2}\sin(\theta)$. (siehe nächste Abbildung für $latex l = 1 , t =1$)

Bei einer Annahme von $latex l \leq t$, also Nadellänge kleiner, oder gleich Liniendistanz, gilt: Die Wahrscheinlichkeit $latex P$, dass eine Nadel eine Linie kreuzt beträgt:

$latex P = \int_{\theta =0}^{\frac{\pi}{2}}\int_{x=0}^{\frac{l}{2}\sin(\theta)}\frac{4}{t \pi}dxd\theta = \frac{2 l}{t \pi}$

Also ist ein Abschätzung für $latex \pi$ gegeben durch:

$latex \pi \approx \frac{2 l}{t P}$

Der Code ist eine relativ primitive Implementierung des Problems.

package montecarlo;

import java.util.Random;

public class BuffonsNeedle {

 // l <= t
 static double l = 3.0;
 static double t = 9.0;

 public static void main(String[] args) {
 pi(10000000);
 }

 static void pi(int loopcount) {
 Random generator = new Random();
 double P = 0.0;
 double a = 0.0;

 for (int i = 1; i <= loopcount; i++) {
 if (generator.nextDouble()*t/2.0 <= l/2.0*Math.sin(generator.nextDouble()*Math.PI/2.0)) {
 ++a;
 }
 P = a/(double)i;
 System.out.println(i + ") " + "Pi is approx.: " + 2.0*l/(t*P));
 }
 }

}
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s